Function that is not Space Constructible 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?
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".