Constructible Function - Time-constructible Definitions

Time-constructible Definitions

There are two different definitions of a time-constructible function. In the first definition, a function f is called time-constructible if there exists a positive integer n₀ and Turing machine M which, given a string 1n consisting of n ones, stops after exactly f(n) steps for all n ≥ n₀. In the second definition, a function f is called time-constructible if there exists a Turing machine M which, given a string 1n, outputs the binary representation of f(n) in O(f(n)) time (a unary representation may be used instead, since the two can be interconverted in O(f(n)) time).

There is also a notion of a fully time-constructible function. A function f is called fully time-constructible if there exists a Turing machine M which, given a string 1n consisting of n ones, stops after exactly f(n) steps. This definition is slightly less general than the first two but, for most applications, either definition can be used.