In complexity theory, a time-constructible function is a function f from natural numbers to natural numbers with the property that f can be constructed from n by a Turing machine in the time of order f. The purpose of such a definition is to exclude functions that do not provide an upper bound on the runtime of some Turing machine.
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 integern0 and Turing machine M which, given a string 1n consisting of nones, stops after exactly fsteps 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 in O 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 steps. This definition is slightly less general than 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 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 binaryrepresentation of f, while using only O 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 cells.
Examples
All the commonly used functions f are time- and space-constructible, as long as f is at least cn for a constant c > 0. No function which is o can be time-constructible unless it is eventually constant, since there is insufficient time to read the entire input. However, is a space-constructible function.
Applications
Time-constructible functions are used in complexity theory results such as the time hierarchy theorem. They are important because the time hierarchy theorem relies on Turing machines that must determine in O time whether an algorithm has taken more than f steps. This is, of course, impossible without being able to calculatef 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.
