Category:Time-Constructible Functions
Jump to navigation
Jump to search
This category contains results about Time-Constructible Functions.
Definitions specific to this category can be found in Definitions/Time-Constructible Functions.
Definition 1
Let $f$ be a function.
Let there exist a positive integer $n_0$ and a Turing machine $M$ such that:
- Given a string $1^n$ consisting of $n$ instances of $1$, $M$ stops after exactly $f \left({n}\right)$ steps for all $n \ge n_0$.
Then $f$ is time-constructible.
Definition 2
Let $f$ be a function.
Let there exist a positive integer $n_0$ and a Turing machine $M$ such that:
- Given a string $1^n$ consisting of $n$ instances of $1$, $M$ outputs the binary representation of $\map f n$ in $\map \OO {\map f n}$ time.
Then $f$ is time-constructible.
This category currently contains no pages or media.