# Simulating multi-tape turing machines by single-tape TM

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?

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.