Constructible function
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). The purpose of such a definition is to exclude functions that do provide an upper bound on the runtime of some Turing machine.
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 then the first two but, for most applications, either definition can be used.
Also, a function f is fully space-constructible if there exists a Turing machine M which, given a string 1n consisting of n ones, halts after using exactly f(n) cells.
. 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.
Space-constructible functions are used similarly, for example in the space hierarchy theorem
.
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, 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
Turing machine
A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
in the time of order f(n). The purpose of such a definition is to exclude functions that do provide an upper bound on the runtime of some Turing machine.
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 n0 and Turing machine M which, given a string 1n consisting of n ones, stops after exactly f(n) steps for all n ≥ n0. 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 then the first two but, for most applications, either definition can be used.
Space Constructible Definitions
Similarly, a function f is space-constructible if there exists a positive integer n0 and a Turing machine M which, given a string 1n consisting of n ones, halts after using exactly f(n) cells for all n ≥ n0. Equivalently, a function f is space-constructible if there exists a Turing machine M which, given a string 1n consisting of n ones, outputs the binary (or unary) representation of f(n), while using only O(f(n)) space.Also, a function f is fully space-constructible if there exists a Turing machine M which, given a string 1n consisting of n ones, halts after using exactly f(n) cells.
Examples
All the commonly used functions f(n) (such as n, nk, 2n) are time- and space-constructible, as long as f(n) is at least cn for a constant c > 0. No function which is o(n) can be time-constructible unless it is eventually constant, since there is insufficient time to read the entire input. However, log(n) is a space-constructible function.Applications
Time-constructible functions are used in complexity theory results such as the time hierarchy theoremTime hierarchy theorem
In computational complexity theory, the time hierarchy theorems are important statements about time-bounded computation on Turing machines. Informally, these theorems say that given more time, a Turing machine can solve more problems...
. 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.
Space-constructible functions are used similarly, for example in the space hierarchy theorem
Space hierarchy theorem
In computational complexity theory, the space hierarchy theorems are separation results that show that both deterministic and nondeterministic machines can solve more problems in more space, subject to certain conditions. For example, a deterministic Turing machine can solve more decision problems...
.