Constructible function

Space-constructible

A function ${\displaystyle f}$ is called space-constructible if there exists a Turing machine ${\displaystyle M}$ such that ${\displaystyle M(1^n)}$ halts with value ${\displaystyle |f(n)|}$ (or equivalently ${\displaystyle 1^{f(n)}}$), while using ${\displaystyle O(f(n))}$ space.

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

Properties

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

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

${\displaystyle \ln n}$ is space-constructible even though ${\displaystyle \ln n=o(n)}$.

For every computable function ${\displaystyle f}$, there is a computable function ${\displaystyle g}$ that is time constructible and ${\displaystyle \mathrm{\forall }n,g(n)>f(n)}$.

Applications

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.