Definition:Time-Constructible Function

From ProofWiki
Jump to navigation Jump to search

Definition

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 $f \left({n}\right)$ in $O \left({f \left({n}\right)}\right)$ time.

Then $f$ is time-constructible.


Also see