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?

  • $\begingroup$ "at least $O(\log n)$" -- this is such an empty statement that I am sad to see it used in a widely adopted textbook. $\endgroup$
    – Raphael
    Dec 9 '14 at 13:17

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".

  • $\begingroup$ Your example with the halting problem really helped clarify this for me. Thanks! $\endgroup$
    – Mark
    Dec 9 '14 at 15:20

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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.