Constructible function
From Wikipedia, the free encyclopedia
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 1n 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 1n, outputs the binary representation of f(n) in O(f(n)) time. 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, nk, 2n) 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. 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 definition.
This article incorporates material from constructible on PlanetMath, which is licensed under the GFDL.
