Do Turing machines have memory registers?

Question

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?

Answer 1

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'$.

Answer 2

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.