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:
- First it sweeps the tape in the left-to-right direction and records to its register the $k$ symbols that are marked by “$ˆ$”.
- 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?