3
$\begingroup$

I am working on chapter one of the textbook Computational Complexity: a modern approach by Arora, S., & Barak, B. They begin by defining a turing machine (TM) and then prove equivalence between variations of TMs. They make the following claim.

Claim 1.6 Define a single-tape Turing machine to be a TM that has only one read-write tape, that is used as input, work, and output tape. For every $f : \{0, 1\}^∗ → \{0, 1\}$ and time-constructible $T : \mathbb{N} → \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 $M'$.

I understand how to "compress" the $k$ tapes $M$ has into $M'$ single-tape. However, when they describe how to simulate one step of $M$ on $M'$ I get confused. More specifically, they describe it as follows:

  1. First it sweeps the tape in the left-to-right direction and records to its register the $k$ symbols that are marked by “$ˆ$”.
  2. Then $M'$ uses $M$’s transition function to determine the new state, symbols, and head movements and sweeps the tape back in the right-to-left direction to update the encoding accordingly.

How can a TM have a register? I thought it was a finite automata with a tape and head only. They also mention TMs having a state register.

How much data can a register hold? In the proof, they imply the register can hold $k$ symbols. Are the registers typically stored on some separate tape or somewhere else?

$\endgroup$

2 Answers 2

8
$\begingroup$

Yes a TM also has states. Formally, one can define TMs as $(Q, \Sigma, \Gamma, \square, \delta, q_0, \bar{q})$ with states $Q$, input alphabet $\Sigma$ not including the blank symbol $\square$, tape alphabet $\Gamma$, transition function $\delta$, initial state $q_0$ and terminal state $\bar{q}$. It might be differently defined but essentially it is all the same (what is of course the whole point of the chapter you are reading right now).

The following explanations are definitely handwavy but I hope the message is still clear.

The positions marked with ^ in 1-tape $M'$ store the current head positions in the $k$-tape TM $M$ which is in some state $q$. By sweeping once through the whole tape on $M'$, $M'$ stores the symbols on each tape marked with ^ in some state that depends on $q$ that "somewhat" looks like $q' = (q, a_1, \ldots, a_k)$, where $a_i \in \Gamma$ is the symbol under the head of tape $i$. The actual state is a bit more involved (e.g. $M'$ needs to store whether it is still in the sweeping process or is already updating the tape according to the transition function, which is tedious but straight-forward) but this is essentially the information you want for $M'$. As the state set, number of tapes, and the set of tape symbols are all finite, this information contained in $q'$ can be stored in a finite state set $Q'$ for $M'$.

$\endgroup$
2
  • $\begingroup$ OK this makes perfect sense. The states are used as storage. Do all states need to have the same form, i.e could you have states $Q=\{q_1, q_2, (q_3, a_1, a_2, ..., a_k)\}$? $\endgroup$
    – Tom Finet
    Sep 28, 2021 at 14:12
  • 1
    $\begingroup$ The implementation details are somewhat arbitrary, so you could use a "non-tuple-$q$" for example at the beginning of the step-simulation, where you haven't figured out any $a_i$ and hence, have the remainder of the storage empty. Your state set could indeed look like this but it doesn't have to. $\endgroup$
    – ttnick
    Sep 28, 2021 at 15:04
19
$\begingroup$

A TM does not have a register, but a register has a fixed capacity.

Any amount of fixed capacity storage can be emulated by multiplying your states: your new states become $ \langle q, v \rangle$ where $q$ is an old state and $v$ a value stored in the register.

So a "TM with a register" is not a TM, but trivially equivalent to a normal TM, and I would expect your course notes to have this spelled out at some point.

$\endgroup$
1
  • 4
    $\begingroup$ To add to this, this is also why we do those other "useless" proofs: states with multiple transitions (NFA's) can be simulated using extra states with single transitions (DFA's); and multiple tapes can be simulated using one tape; and alphabets past 0/1 can be simulated using larger "words". For proofs we can then pick and not pick features we need, but there's still one set of rules in common since we know they all convert to a no-frills TM. $\endgroup$ Sep 28, 2021 at 23:26

Your Answer

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

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