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

Question

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 $C\cdot 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?

Answer 1

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 $CT\log T$ time steps where $C$ is again some constant independent of $T$ or of the input string.