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

ones. That is, it's the unary representation be the binary representation.

is called time-constructible.

steps.

Fully time-constructable

There is also a notion of a fully time-constructible function.

halts in exactly 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. is time-constructible if and only if it is fully time-constructible.

Space-constructible

is called space-constructible space.

halts in a configuration in which exactly cells are not blank, and no other cell has been written to during its operation. This is sometimes called "fully space-constructible". However, the two definitions are equivalent.

Properties

is constructed by two nested for-loops, etc.

is time-constructible, then it is eventually constant, since otherwise there is insufficient time to read the entire input.

.

For every computable function.

Applications

Time-constructible functions are used in results from complexity theory such as the time hierarchy theorem. They are important because the time hierarchy theorem relies on Turing machines that must determine in O(f(n)) time whether an algorithm has taken more than f(n) steps. This is, of course, impossible without being able to calculate f(n) in that time. Such results are typically true for all natural functions f but not necessarily true for artificially constructed f. To formulate them precisely, it is necessary to have a precise definition for a natural function f for which the theorem is true. Time-constructible functions are often used to provide such a definition.

Space-constructible functions are used similarly, for example in the space hierarchy theorem.

References