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

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?

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.

• The book says that SU(a,t,x) is a construct where the Turing machine SU is bounded by time t. So this was my first question. In your answer, you have said SU(a,t,x) here means that t is space bound. If so, my next question is, why specify a bound in the construction at all? The question could have equivalently stated :- SU(α,x)= Mα(x) and moreover, SU uses at most C⋅t cells where t is the space used by Mα. – rahul May 27 '12 at 18:51
• question 4.1. does not say anywhere that $t$ is a time bound: it's clearly defined as a space bound. can you quote where you are seeing $t$ defined differently? – Sasho Nikolov May 27 '12 at 18:57
• It is defined immediately after Theorem 1.9 which the question asks us to consult. – rahul May 27 '12 at 20:22
• Here is the quote "Universal TM with time bound. It is sometimes useful to consider a variant of the universal TM U that gets a number T as an extra input (in addition to x and α), and outputs Mα (x) if and only if Mα halts on x within T steps (otherwise outputting some special failure symbol)." It is on the same page as Theorem 1.9. On the other hand, a construction such as SU(α,t,x) is not defined any where else. – rahul May 27 '12 at 20:35
• The construction $SU(\alpha, t, x)$ is defined in question 4.1.. You need to prove that it exists. True, the definition is a bit dense, but it is there. The question states that $SU$ is defined analogously to the time-bounded universal TM of Thm 1.9. "Analogously" obviously does not mean that it's the exact same definition. It is a similar definition, only that time bounds have been replaced with space bounds, and the parameters are adjusted slightly – Sasho Nikolov May 28 '12 at 1:49