In "Computational Complexity: A modern approach", Arora and Barak proof the following Claim:

Define a single-tape Turing machine to be a TM that has only one read-write tape, that is used a input, work, and output tape. For every $f: \{0,1\}^* \rightarrow \{0,1\}$ and time-constructible $T: \mathbb{N} \rightarrow \mathbb{N}$, if $f$ is computable in time $T(n)$ by a TM $M$ using $k$ tapes, then it is computable in time $5kT(n)^2$ by a single-tape TM $\hat{M}$.

The proof roughly goes like this, from my understanding:

-> We encode the $k$ tapes of $M$ on a single tape, using locations $i,k+i,2k+i$ for the $k$-th tape.

-> For each character $a$ in M's alphabet, we define another character $\hat{a}$ in $\hat{M}$'s alphabet. For each of M's tapes, the $\hat{a}$ character indicates the current position of that respective tape (for $M$) in $M's$ encoding.

-> For each state transition of $M$, $\hat{M}$ then perform two sweeps: One left-to-right, where $\hat{M}$ finds the positions of $M$ at the respective working tapes and one right-to-left where $\hat{M}$ updates its tape encoding according to state transition function of $M$.

Its not clear to me how the first step exactly works. Arora and Barak write: "First it sweeps the tape in the left-to-right direction and records to its register the $k$ symbols that are marked by $\hat{a}$". As far as I understand, registers correspond to states in the TM $M'$. What is exactly is meant by recording the symbols to its register?


1 Answer 1


You can simulate a state machine with set of states $S$ and registers $R_1,\ldots,R_m$ varying over a finite alphabet $\Sigma$ using a vanilla state machine whose set of states is $S \times \Sigma^m$. You "store" a value $x$ in register $R_i$ by transitioning to a state whose $(i+1)$'th element is $x$. You "read" a value from $R_i$ by taking into account in your transition table the $(i+1)$'th element of the current state.

This is the sense in which $\hat{M}$ has registers – their contents are stored in the state of the machine. Here it is crucial that both $k$ and the tape alphabet are fixed and finite.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.