2
$\begingroup$

In Arora and Barak's Computational Complexity, Claim 1.5 says that if a function $f$ is computable in time $T(n)$ by a Turing machine with alphabet $\Gamma$ then it is computable in at most time $4\log|\Gamma|T(n)$ by a Turing machine with the symbol set $\{0,1,\rhd,\Box\}$ where $\rhd$ is a special symbol that is used to mark the beginning of each tape and $\Box$ is the blank symbol.

It seems to me that we can reduce the bound to $3\log|\Gamma|T(n)$. Am I right in this?

It seems to me that the above can be achieved using the same device as discussed in the book: we represent each alphabet of the original Turing machine by a sequence of $k=\log |\Gamma|$ bits. Let's further decide to represent the blank symbol of the original machine by a sequence of $k$ $\Box$s (this is not mentioned in the book). Our new machine has intermediate states where it reads $k$ bits to identify the symbol that would have been read from the tape of the original machine, then moves $k$ steps backward on each tape writing down the representation of the new symbol that would have been written on the tapes of the original machine, then moves $k$ steps to the left or right on each tape to position the head on the beginning of the symbol that would have been read next by the original machine. So a total of only $3k$ steps seems to be required to simulate each step of the original machine.

To take an example suppose $|\Gamma|=16$ and we are simulating a step of the original machine which required reading the symbol represented by abcd, overwriting it by ABCD and then moving the head to the right. This can be accomplished as follows:

We begin at

efgh|abcd|pqrs
     ^

In 4 steps read all the bits of abcd. In the 4th step we know enough to decide that we have to replace d by D. We do that and move back one step

efgh|abcD|pqrs
       ^

In 3 more steps we have replaced abc by ABC and positioned the head at B

efgh|ABCD|pqrs
      ^

In 3 more steps we have moved the head to p

efgh|ABCD|pqrs
          ^

If the original machine had wanted to move left rather than right we would have positioned the head at h after writing A and then would have moved to e in 3 more steps. So actually we need only $3k-2$ steps.

$\endgroup$
  • 1
    $\begingroup$ I think that your proof is OK. But, you can also do better: there is no need to always jump on the leftmost symbol of the simulated cell. Indeed, we can also keep track if we entered the simulated symbol from the left or the right, and read it from left-to-right or right-to-left. So if a simulated cell is entered from the left, a read-write-right transition requires $3k-2$ steps, but a read-write-left transition requires $2k-1$ steps (and the next cell will be read from right-to-left). $\endgroup$ – Marzio De Biasi Jun 8 '14 at 0:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.