Constructible function

In complexity theory, a timeconstructible 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.
Contents
Time Constructible Definitions
There are two different definitions of a timeconstructible function. In the first definition, a function f is called timeconstructible if there exists a positive integer n_{0} and Turing machine M which, given a string 1^{n} consisting of n ones, stops after exactly f(n) steps for all n ≥ n_{0}. In the second definition, a function f is called timeconstructible if there exists a Turing machine M which, given a string 1^{n}, 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 timeconstructible function. A function f is called fully timeconstructible if there exists a Turing machine M which, given a string 1^{n} 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 spaceconstructible if there exists a positive integer n_{0} and a Turing machine M which, given a string 1^{n} consisting of n ones, halts after using exactly f(n) cells for all n ≥ n_{0}. Equivalently, a function f is spaceconstructible if there exists a Turing machine M which, given a string 1^{n} 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 spaceconstructible if there exists a Turing machine M which, given a string 1^{n} consisting of n ones, halts after using exactly f(n) cells.
Examples
All the commonly used functions f(n) (such as n, n^{k}, 2^{n}) are time and spaceconstructible, as long as f(n) is at least cn for a constant c > 0. No function which is o(n) can be timeconstructible unless it is eventually constant, since there is insufficient time to read the entire input. However, log(n) is a spaceconstructible function.
Applications
Timeconstructible 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(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. Timeconstructible functions are often used to provide such definition.
Spaceconstructible functions are used similarly, for example in the space hierarchy theorem.
This article incorporates material from constructible on PlanetMath, which is licensed under the Creative Commons Attribution/ShareAlike License.
Categories: Computational complexity theory
 Types of functions
Wikimedia Foundation. 2010.
Look at other dictionaries:
Constructible universe — Gödel universe redirects here. For Kurt Gödel s cosmological solution to the Einstein field equations, see Gödel metric. In mathematics, the constructible universe (or Gödel s constructible universe), denoted L, is a particular class of sets… … Wikipedia
Constructible polygon — Construction of a regular pentagon In mathematics, a constructible polygon is a regular polygon that can be constructed with compass and straightedge. For example, a regular pentagon is constructible with compass and straightedge while a regular… … Wikipedia
Proper complexity function — A proper complexity function is a function f mapping a natural number to a natural number such that: * f is nondecreasing; * there exists a k string Turing machine M such that on any input of length n , M halts after O( n + f ( n )) steps, uses… … Wikipedia
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 (asymptotically) more space, subject to certain conditions. For… … Wikipedia
Time 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. For example … Wikipedia
List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… … Wikipedia
Список терминов, относящихся к алгоритмам и структурам данных — Это служебный список статей, созданный для координации работ по развитию темы. Данное предупреждение не устанавливается на информационные списки и глоссарии … Википедия
Список терминов — Список терминов, относящихся к алгоритмам и структурам данных Это сл … Википедия
DSPACE — For digital repositories, see DSpace. In computational complexity theory, DSPACE or SPACE is the computational resource describing the resource of memory space for a deterministic Turing machine. It represents the total amount of memory space… … Wikipedia
List of computability and complexity topics — This is a list of computability and complexity topics, by Wikipedia page. Computability theory is the part of the theory of computation that deals with what can be computed, in principle. Computational complexity theory deals with how hard… … Wikipedia