Function that is not Space Constructible

Question

I'm reading Sipser's Introduction to the Theory of Computation, and I'm reading about space-constructible functions. He gives the following definition:

A function $f: \mathbb{N} \to \mathbb{N}$ is space constructible if the function that maps the string $1^n$ to the binary representation of $f(n)$ is computable in space $O(f(n))$.

He follows up by saying,

All commonly occurring functions that are at least $O(\log n)$ are space constructible, including the functions $\log_2 n$, $n \log_2 n$, and $n^2$.

My question: What is an example of a function that is $\Omega(\log n)$ that is not space constructible?

Answer 1

Usually such examples are specifically "tailored", using hard problems. Perhaps the easiest way is to take the halting problem: $$HALT=\{\langle M\rangle: M\text{ is a TM that halts on }\epsilon\}$$ and consider the encodings of TMs as numbers, in such a way that no two numbers are encoded to the same TM (e.g. by leading 0s). This can be achieved using unary encoding, for example.

Now, consider the function $f:\mathbb{N}\to \mathbb{N}$ defined as follows: $f(n)=2n$ if $n$ represents a TM in HALT, and $f(n)=2n+1$ otherwise.

This function is $\theta(n)$, but clearly it is not space constructible, since constructing it would enable you to solve the halting problem.

A similar example can be constructed from a problem which is harder than PSPACE (e.g. a problem complete in EXPSPACE).

However, these example are somewhat "ugly". A more elegant example is the busy beaver function, which is non-computable simply because it "grows too fast".

Answer 2

Most functions are not space constructible. For example, let $A$ be a non-computable set, and define $$ f(n) = \begin{cases} 2n & \text{if } n \in A, \\ 2n+1 & \text{if } n \notin A. \end{cases} $$ This is a monotone increasing function which is $\Theta(n)$ but isn't space constructible.

Here is a more interesting example. Instead of taking $A$ to be non-computable, take a language which is in $\mathrm{SPACE}(n^2) \setminus \mathrm{SPACE}(n)$. Such a language exists by the space hierarchy theorem. Again $f(n)$ is a monotone $\Theta(n)$ function, which is computable in space $O(n^2)$ but not in space $O(n)$.