Constructible function

Let the Turing machine be defined in the standard way, with an alphabet that includes the symbols $0,\; 1$. It has a standard input tape containing zeros except for an input string. Let $1^n$ denote a string composed of $n$ ones. That is, it's the unary representation. Let $|n|$ be the binary representation.

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 Turing machine $M$, such that for all but finitely many $n$, $M(1^n)$ halts in $O(f(n))$ steps.

In the second definition, a function $f$ is called time-constructible if there exists a Turing machine $M$, such that for all but finitely many $n$, $M(1^n)\; =\; |f(n)|$ and halts in $O(f(n))$ steps.

The second definition may use $M(1^n)\; =\; 1^\{f(n)\}$ instead, since the two can be interconverted in $O(f(n))$ steps.

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$, such that for all but finitely many $n$, $M(1^n)$ halts in exactly $f(n)$ steps.{{Cite book |last1=Homer |first1=Steven |title=Computability and Complexity Theory |last2=Selman |first2=Alan L. |publisher=Springer |year=2011 |isbn=978-1-4614-0681-5 |edition=Second}} This definition is slightly less general than the first two but, for most applications, either definition can be used.{{Cite book

|title=Structural Complexity I

|last1=Balcázar

|first1=José Luis

|last2=Díaz

|first2=Josep

|last3=Gabarró

|first3=Joaquim

|isbn=3-540-18622-0

|publisher=Springer-Verlag

|year=1988}} The following equivalence theorem shows that these two concepts are equivalent for most functions used in practice:

Theorem.{{Pg|location=Theorem 2.6}} If $f$ is a function such that there exists $\backslash epsilon\; >\; 0$ such that, for all but finitely many $n$, $f(n)\; \backslash geq\; (1+\; \backslash epsilon)\; n$, then $f$ is time-constructible iff it is fully time-constructible.

More succinctly, the condition states that $f(n)\; -\; n\; =\; \backslash Omega(n)$.

Function $f$ is called space-constructible, if there exists a Turing machine $M$, such that for all but finitely many $n$, $M(1^n)\; =\; |f(n)|$ (or equivalently $1^\{f(n)\}$), while using $O(f(n))$ space.

Equivalently, if there exists a Turing machine $M$, such that for all but finitely many $n$ given $1^n$, halts in a configuration in which exactly $f(n)$ cells are not blank, and no other cell has been written to during its operation.{{Pg|location=Definition 2.4}} This is sometimes called "fully space-constructible". However, the two definitions are equivalent.{{Pg|location=Theorem 2.7}}

All the commonly used functions (such as $n,\; n^2,\; 2^n,\; n!$) are time- and space-constructible, as long as $f(n)\; =\; \backslash Omega(n)$. The construction is straightforward. For example, $n^2$ is constructed by one for-loop, while $n^3$ is constructed by two for-loops, etc.

If $f(n)\; =\; o(n)$ is time-constructible, then it is eventually constant, since otherwise there is insufficient time to read the entire input.

$\backslash ln\; n$ is space-constructible even though $\backslash ln\; n\; =\; o(n)$

.

For every recursive function $f$, there is a recursive function $g$ which is time constructible and $\backslash forall\; n,\; g(n)\; >\; f(n)$.{{Pg|location=Lemma 2.3}}

Time-constructible functions are used in results from complexity theory 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. Time-constructible functions are often used to provide such a definition.

Space-constructible functions are used similarly, for example in the space hierarchy theorem.

{{PlanetMath attribution|id=3461|title=constructible}}

{{Reflist}}

Category:Computational complexity theory

Category:Types of functions