[proofplan] We construct the multi-tape machine by using its first tape as a literal copy of the single tape of $M$, with the first tape head always placed at the simulated head position. The remaining tapes are kept blank and their heads are stationary. The transition function of the simulator reads the first tape symbol, applies the transition function of $M$, writes the resulting symbol on the first tape, moves the first tape head in the same direction, and updates the finite control to the corresponding state of $M$. An induction on the number of simulated transitions proves that the first tape configuration, head position, and control state agree at every time, so halting behavior and running time are preserved exactly. [/proofplan] [step:Construct the multi-tape simulator with one active tape] Fix an integer $k \geq 2$. Define a deterministic $k$-tape Turing machine $N$ with the same input alphabet $\Sigma$, the same tape alphabet $\Gamma$, the same state set $Q$, the same start state $q_0$, and the same halting states $q_{\mathrm{acc}}$ and $q_{\mathrm{rej}}$ as $M$. Define the transition function of $N$ as the map \begin{align*} \delta_N: \bigl(Q \setminus \{q_{\mathrm{acc}},q_{\mathrm{rej}}\}\bigr) \times \Gamma^k \to Q \times \Gamma^k \times \{L,R,S\}^k. \end{align*} For a nonhalting state $q \in Q \setminus \{q_{\mathrm{acc}}, q_{\mathrm{rej}}\}$ and tape symbols $a_1,\dots,a_k \in \Gamma$, define this map as follows. If \begin{align*} \delta_M(q,a_1) = (q',b,D), \end{align*} where $q' \in Q$, $b \in \Gamma$, and $D \in \{L,R,S\}$, then set \begin{align*} \delta_N(q,a_1,\dots,a_k) = (q',b,a_2,\dots,a_k,D,S,\dots,S). \end{align*} Thus $N$ writes only on its first tape, moves only its first tape head, and leaves tapes $2,\dots,k$ unchanged with stationary heads. [guided] The simulator should preserve the single-tape computation without encoding or compression. We therefore use tape $1$ of $N$ as the simulated tape of $M$ and make all other tapes irrelevant. Formally, $N$ has the same state set $Q$ as $M$, so the control state of $N$ directly records the control state of the simulated machine. Its transition function is the map \begin{align*} \delta_N: \bigl(Q \setminus \{q_{\mathrm{acc}},q_{\mathrm{rej}}\}\bigr) \times \Gamma^k \to Q \times \Gamma^k \times \{L,R,S\}^k. \end{align*} When $N$ is in a nonhalting state $q \in Q \setminus \{q_{\mathrm{acc}},q_{\mathrm{rej}}\}$ and reads symbols $a_1,\dots,a_k \in \Gamma$ on its $k$ tapes, only $a_1$ matters because $a_1$ is the symbol scanned by the simulated single-tape head. If \begin{align*} \delta_M(q,a_1) = (q',b,D), \end{align*} then $M$ would enter state $q'$, write $b$, and move its head in direction $D$. We define $N$ to do exactly this on tape $1$ and to do nothing on the other tapes: \begin{align*} \delta_N(q,a_1,\dots,a_k) = (q',b,a_2,\dots,a_k,D,S,\dots,S). \end{align*} This transition is deterministic because $\delta_M$ is deterministic: for each pair $(q,a_1)$ there is exactly one triple $(q',b,D)$, and hence for each tuple $(q,a_1,\dots,a_k)$ there is exactly one transition of $N$. The symbols $a_2,\dots,a_k$ are rewritten unchanged, and the corresponding heads receive the stationary movement $S$, so tapes $2,\dots,k$ remain unused throughout the computation. [/guided] [/step] [step:Initialize the simulator in the same configuration as the simulated machine] On input $w \in \Sigma^*$, the initial configuration of $N$ places $w$ on tape $1$ with the first tape head in the same initial position as the head of $M$. Tapes $2,\dots,k$ are blank, and their heads start in their standard initial positions. The initial state is $q_0$, which is also the initial state of $M$. [/step] [step:Prove by induction that every simulator configuration represents the corresponding single-tape configuration] For each integer $s \geq 0$, let $C_M(s)$ denote the configuration of $M$ after $s$ transitions on input $w$, provided those $s$ transitions exist. Let $C_N(s)$ denote the configuration of $N$ after $s$ transitions on the same input, provided those $s$ transitions exist. We prove by induction on $s$ that, whenever $C_M(s)$ exists, the state of $N$ in $C_N(s)$ equals the state of $M$ in $C_M(s)$, tape $1$ of $N$ equals the tape of $M$, and the head of tape $1$ of $N$ is at the head position of $M$. Tapes $2,\dots,k$ of $N$ remain blank and their heads remain in their initial positions. For $s=0$, this is exactly the initial configuration described above. Assume the assertion holds for some $s \geq 0$, and suppose $M$ has not halted before transition $s+1$. Let $q \in Q \setminus \{q_{\mathrm{acc}},q_{\mathrm{rej}}\}$ be the common state at time $s$, and let $a \in \Gamma$ be the symbol scanned by the head of $M$ at time $s$. By the induction hypothesis, the first head of $N$ also scans $a$ at time $s$. If \begin{align*} \delta_M(q,a) = (q',b,D), \end{align*} then the definition of $\delta_N$ gives \begin{align*} \delta_N(q,a,a_2,\dots,a_k) = (q',b,a_2,\dots,a_k,D,S,\dots,S), \end{align*} where $a_2,\dots,a_k \in \Gamma$ are the symbols scanned on the inactive tapes. Hence both machines enter state $q'$, both write $b$ at the simulated tape square, and both move the simulated head in direction $D$. The inactive tapes are rewritten with their old symbols and their heads remain stationary. Therefore the induction assertion holds for $s+1$. By induction, the simulator represents the single-tape computation at every time for which the computation exists. [/step] [step:Transfer halting behavior and running time] If $M$ reaches $q_{\mathrm{acc}}$ after $t$ transitions, then the induction result shows that $N$ also reaches $q_{\mathrm{acc}}$ after $t$ transitions. The same argument applies to $q_{\mathrm{rej}}$. Conversely, if $N$ reaches either halting state after $t$ transitions, then its state agrees with the state of $M$ after $t$ transitions, so $M$ reaches the same halting state at that time. If $M$ does not halt on $w$, then every finite prefix of its computation exists. The induction result gives a corresponding finite prefix of the computation of $N$ of the same length, so $N$ does not halt either. Thus $M$ and $N$ have identical accept, reject, and divergence behavior on every input $w \in \Sigma^*$. Finally, if $M$ halts on $w$ after $t$ transitions, then $N$ performs exactly one transition for each transition of $M$ and halts after exactly $t$ transitions. Therefore the simulation overhead is linear, with multiplicative constant $1$ and additive constant $0$. In particular, if $M$ runs in time $T(n)$, then $N$ runs in time at most $T(n)$ on inputs of length $n$. [/step]