[Solved]: Space bounded Turing Machine – clarification on Computational Complexity (book: Arora-Barak ) question 4.1

ignougroup
Problem Detail: I have the following question from Computational Complexity – A modern Approach by Sanjeev Arora and Boaz Barak:

[Q 4.1]
Prove the existence of a universal TM for space bounded computation (analogously to the deterministic universal TM of Theorem 1.9).

That is, prove that there exists a Turing Machine $SU$ such that for every string $alpha$ and input $x$, if the TM $M_alpha$ — the TM represented by $alpha$ — halts on $x$ before using $t$ cells of its work tape, then $SU(alpha, t, x) = M_alpha(x)$ and moreover, $SU$ uses at most $Ccdot t$ cells of its work tape, where $C$ is a constant depending only on $M_alpha$. After checking theorem 1.9 and the universal TM with time bound, I see that the construct $SU(alpha, t, x)$ means that the Turing machine SU stops after $t$ steps. However if this is the case, then it means that we can create a Turing Machine equivalent to $M_alpha$ such that the new Turing Machine stops in $t$ steps where $t$ is the “space” used in the original. However, this seems a dubious interchange of space and time. If on the other hand, $t$ actually meant that the second machine stops within $t$ space, too, then the second part does not make sense any more because it says $SU$ uses $Ct$ cells, which is not $t$. So my question is how do I interpret this? Is the first interpretation really possible?

Asked By : rahul

Answered By : Sasho Nikolov

I do not understand what you are trying to say after “–“, but here is what you need to do: Hopefully you understand the idea of turing machine encoding: i.e. you can assign a unique identifier (i.e. “label”) $alpha$ to each turing machine. So by $M_alpha$ we mean the Turing machine labeled by $alpha$. So you need to design a single turing machine $SU$ which takes three inputs $alpha$, $t$ and $x$ ($alpha$ is a turing machine label, $t$ is a space bound, and $x$ is an input string) and:

  • if $M_alpha$ uses more than $t$ bits of workspace on input $x$ before it halts, then we have no requirement for $SU$
  • if $M_alpha$ uses at most $t$ bits of workspace on input $x$ we have two requirements for $SU$:
    • $SU$ uses at most $Ct$ units of workspace where $C$ is a function of $alpha$ but not $t$ or $x$
    • $SU$ outputs $M_alpha(x)$

The idea is that for any machine and any input, $SU$ can simulate that machine while using only slightly more space than the original machine. Note that $t$ is a bound on the space that $M_alpha$ uses, not the space that $SU$ uses. $SU$ cannot be exactly as space efficient as the original machine because simulation requires some overhead, but the point is that the overhead is small as $C$ is fixed for every $alpha$, no matter how large $x$ is in size. Theorem 1.9. also has some overhead: a machine which stops in $T$ time steps is simulated in $CTlog T$ time steps where $C$ is again some constant independent of $T$ or of the input string.

Best Answer from StackOverflow

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