1
$\begingroup$

I've searched this and was not able to understand the answer.

What's the idea/intuition behind this? What's the purpose and why is it important?

And considering the wikipedia explaination, specifically this part:

outputs the binary (or unary) representation of f(n), while using only O(f(n)) space

Why does it matter that the binary representation doesn't exceed O(f(n)) space?

And what does it mean to not exceed that space? Why is the function f(n) = c not space constructible?

Sorry if this has been asked before but I didn't find it.

$\endgroup$
1
$\begingroup$

The space used by a Turing machine is the total number of cells that the head (or heads, if a multitape machine) of the Turing machine has ever visited. A function $f(n)$ is space-constructible if there is a Turing machine that on input $1^n$ outputs the binary representation of $f(n)$, and while doing so only visits $O(f(n))$ cells. Note that $O(f(n))$ is an upper bound on the visited cells, not on the length of the representation.

Whether constant functions are space-constructible or not according to this definition depends on the Turing machine model. If the input and output are on the same tape, then a Turing machine space-constructing $c$ should first erase the input $1^n$ and then write the binary representation of $c$. Unfortunately, this takes $n$ space rather than $O(c) = O(1)$ space. If, in contrast, the input is on a special read-only tape and the output is on a special write-only tape (as is the case for log-space machines), then there is absolutely no problem to (fully) space-construct $c$.

$\endgroup$

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.