6
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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α. $\endgroup$ – rahul May 27 '12 at 18:51
  • $\begingroup$ 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? $\endgroup$ – Sasho Nikolov May 27 '12 at 18:57
  • $\begingroup$ It is defined immediately after Theorem 1.9 which the question asks us to consult. $\endgroup$ – rahul May 27 '12 at 20:22
  • $\begingroup$ 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. $\endgroup$ – rahul May 27 '12 at 20:35
  • $\begingroup$ 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 $\endgroup$ – Sasho Nikolov May 28 '12 at 1:49

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.