Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Constructible function
Summary
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.
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 than the first two but, for most applications, either definition can be used.
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.
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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.