In complexity theory, a time-constructible function is a function f from natural numbers to natural numbers with the property that f(n) can be constructed from n by a Turing machine in the time of order f(n). The purpose of such a definition is to exclude functions that do not provide an upper bound on the runtime of some Turing machine.
Time-constructible
Let the Turing machine be defined in the standard way, with an alphabet that includes the symbols <math>0, 1</math>. It has a standard input tape containing zeros except for an input string. Let <math>1^n</math> denote a string composed of <math>n</math> ones. That is, it's the unary representation of <math>n</math>. Let <math>|n|</math> be the binary representation.
A function <math>f</math> is called time-constructible if there exists a Turing machine <math>M</math> such that the computation <math>M(1^n)</math> halts in <math>O(f(n))</math> steps with value <math>|f(n)|</math>.
This definition may use <math>M(1^n) = 1^{f(n)}</math> instead, since the two can be interconverted in <math>O(f(n))</math> steps. This definition is slightly less general than the first, but for most applications, either definition can be used. The following equivalence theorem shows that these two concepts are equivalent for most functions used in practice:
Theorem.