[Solved]: Function that is not Space Constructible

Problem Detail: 

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?

Asked By : Mark

Answered By : Shaull

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/34039

3.2K people like this

 Download Related Notes/Documents