# Importance of Constructible functions

A function $f$ is called fully time-constructible if there exists a Turing machine $M$ which, given a string $1^n$ consisting of $n$ ones, stops after exactly $f(n)$ steps. Analogously, we can call a function $f$ fully space-constructible if there exists a Turing machine $M$ which, given a string $1^n$ consisting of $n$ ones, halts after using exactly $f(n)$ cells. Consider this function: \begin{equation*} f(n) = \begin{cases} n^3, & \text{if}\ n = 3k \ for \ k \in \mathbb{N} \ and \ 2^n, & \text{otherwise} \end{cases} \end{equation*}

Is $f(n)$ time-constructible and/or space constructible? Also, what is the intuition behind considering time/space constructible functions in complexity theory? Will things be any different if we include non-constructible time/space functions?

-

f(n) is both time- and space-constructable. $M$ converts the input to binary, performs the necessary computations, and then spins for the appropriate number of steps.

Constructable functions are primarily considered in order to simplify technical issues in proofs. For example, consider the Time Hierarchy Theorem, which essentially says that having more time allows you to solve more stuff.

The formal statement is: Given a time-constructable function $f(n)$ and a function $g(n)=\omega(f(n)\log f(n))$, there exists a language decidable in $TIME(g(n))$ but not in $TIME(f(n))$.

The proof is by diagonalization. Construct a machine $M$ which, on input $x$, simulates machine $x$ on input $x$ for $f(n)$ steps. If $x(x)$ halts within that time bound, $M$ outputs the opposite. If $x(x)$ hasn't halted, $M$ rejects (arbitrarily). The simulation can be done using $\log f(n)$ overhead, and the theorem follows.

In order for the proof to work, $M$ needs to be able to count $f(n)$ steps, and it needs to do so efficiently. Otherwise, the running time of $M$ won't be bounded by $g(n)$. Time-constructability is exactly the criteria needed to allow the proof to work.

Since basically every function of interest is time-constructable, there isn't much point in removing the technicality. Actually, in the case of the time hierarchy theorem, removing the constructability requirement makes the theorem spectacularly false. The Blum Gap Theorem says that given any function $r(n)$, such as $2^n$, there exists a function $f(n)$ such that $TIME(f(n))=TIME(f(r(n)))$. Obviously, this $f$ is not time-constructable.

-
Thanks! that was a great answer! – Nikhil Mar 31 '11 at 14:48