On proving time constructibility of functions
The paper contains two theorems about sufficient conditions for time constructibility of functions. The theorems are in fact a formalization of the essence of some proofs dealing with time constructibility known from the literature. Two cases are treated separately. The first theorem covers the case of functions for which the condition \[ (\exists \epsilon >0)[f(n)\geq (1+\epsilon)n,\quad for\quad almost\quad all\quad n] \] holds. The second theorem applies to functions f with f(n)\(\geq n\) but not meeting the above condition. Using the theorem, time constructibility of functions like \(\lfloor n^ p\rfloor (p\geq 1),n!,2^ n,2^{2^ n},...,n\lfloor \lfloor \log n\rfloor^ p\rfloor,...,n\lfloor (\log^*n)^ p\rfloor\), \(n_ 1\cdot n_ 2\), \(n+\lfloor n^ p\rfloor (0<p<1),n+\lfloor \lfloor \log n\rfloor^ p\rfloor,n+\lfloor (\log^*n)^ p\rfloor\), etc. can be proved on a few lines.
- A note on square rooting of time functions of Turing machines
- Deterministic Turing machines in the range between real-time and linear-time.
- scientific article; zbMATH DE number 3860251 (Why is no real title available?)
- scientific article; zbMATH DE number 3958737 (Why is no real title available?)
- Alternating time versus deterministic time: A separation
- scientific article; zbMATH DE number 1390074 (Why is no real title available?)
This page was built for publication: On proving time constructibility of functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1059393)
