Constructible function

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).

There are two different definitions of a time-constructible function. In the first definition, a function is called time-constructible if there exists a Turing machine M which, given a string 1ⁿ consisting of n ones, stops after exactly f(n) steps. In the second definition, f is called time-constructible, if there exists a Turing machine M which, given a string 1ⁿ, stops in O(f(n)) steps and outputs a string 1^f(n) consisting of f(n) ones. The second definition is slightly more general but, for most applications, either definition can be used.

Similarly f is space-constructible if there is a Turing machine that halts after using exactly f(n) cells.

All the commonly used functions f(n) (such as n, n^k, 2ⁿ) are time-constructible and space-constructible, as long as f(n) is at least cn for a constant c>0.

Time-constructible functions are used in complexity theory results such time hierarchy theorem. 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 definition.

This article incorporates material from constructible on PlanetMath, which is licensed under the GFDL.