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?
Function that is not Space Constructible
complexity theory;space complexity
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.