Programming Turing machines

Let $n = x + 1$. We show by induction on $j \in \{0, \dots, n\}$ that the machine reaches the configuration in state $q_0$ with tape $X^j 1^{n-j} Y^j$ written from cell $0$ and the head on cell $j$. For $j = 0$ this is the initial configuration. Suppose it holds for some $j < n$. Cell $j$ contains $1$: the machine writes $X$ and enters $q_1$, which moves right across $1^{n-j-1} Y^j$ to the first blank, at cell $n + j$, writes $Y$ there, and enters $q_2$. In state $q_2$ the head moves left across $Y$s and $1$s until it reaches the $X$ on cell $j$, and enters $q_0$ on cell $j + 1$. The tape is now $X^{j+1} 1^{n-j-1} Y^{j+1}$, as required.

For $j = n$, the tape is $X^n Y^n$ and the head scans the first $Y$, on cell $n$, in state $q_0$. The machine writes $1$ and enters $q_3$, which turns the remaining $Y$s into $1$s and reaches the blank on cell $2n$. It then erases cell $2n - 1$, which contains $1$, and enters $q_5$ on cell $2n - 2$. Note that $2n - 2 \geq 0$. State $q_5$ moves left, turning $1$s and $X$s into $1$s, down to cell $-1$, and halts on cell $0$. The final tape is $1^{2n - 1}$ on cells $0, \dots, 2n - 2$, that is $\ulcorner 2x \urcorner$.

The symbol scanned in the translated configuration is $\tau^{+d}(h + d) = \tau(h)$, so the same transition $(q', b, D)$ is applied. The new tape coincides with $\tau^{+d}$ except at $h + d$ where it contains $b$, which is exactly $\tau'^{+d}$, and the new head position is $h' + d$. The second statement follows by induction on the number of steps.

By Exercise 3.4 below, we may assume that every halting computation of $M$ on an input $\ulcorner x \urcorner$ ends in a standard final configuration.

Rename the states of $N$ so that they are disjoint from those of $M$, and take the union of the alphabets. The machine $M ; N$ has the states of both machines, initial state $q_0^M$, halting state $q_h^N$, and the transitions of both machines, except that every transition of $M$ entering $q_h^M$ is redirected to $q_0^N$. The state $q_h^M$ is no longer entered; its transitions, now required since it is not the halting state of $M ; N$, are set arbitrarily. Entries for symbols of one machine absent from the alphabet of the other are set arbitrarily; they are never used, since $M$ only sees its own symbols, and $N$ is started on a tape containing only $\sqcup$ and $1$.

On input $x$, the machine $M ; N$ first behaves like $M$. If $f(x)\diverge$, then $M$ does not halt, and neither does $M ; N$. If $f(x)\converge = y$, then $M ; N$ enters $q_0^N$ with a tape containing exactly $\ulcorner y \urcorner$, starting at the head position $h$. This is the initial configuration of $N$ on input $y$, translated by $h$. By Lemma 3.2, the remaining computation is the translation by $h$ of the computation of $N$ on input $y$. Since translations preserve standard final configurations, $M ; N$ halts in a standard final configuration with output $g(y)$ if $g(y)\converge$, and otherwise it does not. Hence $M ; N$ computes $g \circ f$.

Let $M$ be a $k$-tape machine with alphabet $\Gamma$. The idea is to store the $k$ tapes on $k$ tracks of a single tape. Let the new alphabet be $\Gamma \cup (\Gamma \times \{0, 1\})^k$: a cell of the simulating machine $N$ contains either a symbol of $\Gamma$, or a $k$-tuple of pairs $(a_i, m_i)$ where $a_i$ is the content of the corresponding cell of tape $i$ and $m_i = 1$ indicates that the head of tape $i$ is at this cell. This alphabet is finite.

$N$ first converts cell $0$ into this format: it replaces the symbol $a$ there by $((a, 1), (\sqcup, 1), \dots, (\sqcup, 1))$, since all heads of $M$ start on cell $0$. Then $N$ simulates each step of $M$ as follows. The state of $M$ is stored in the state of $N$. $N$ sweeps over the zone of the tape visited so far, from left to right, and collects in its state the symbols under the $k$ marked heads; there are finitely many possibilities, so they can be stored in the state. Knowing the state of $M$ and the scanned symbols, $N$ determines the transition of $M$. It then sweeps back from right to left, updating the symbol under each marked head and moving each mark by one cell according to the transition. When a mark must move onto a cell containing a plain symbol $a$ of $\Gamma$ — a cell that no head has visited yet — $N$ first replaces it by $((a, 0), (\sqcup, 0), \dots, (\sqcup, 0))$; this is the correct content, since an unvisited cell of tape $1$ still holds its input symbol and an unvisited cell of another tape is blank. Since all heads start on cell $0$ and move by one cell at a time, the converted cells always form an interval containing $0$, bordered by plain symbols, so $N$ recognizes the ends of the zone it must sweep. When $M$ halts, $N$ converts the tape back, keeping only track $1$, moves the head to the position of head $1$, and halts.

By induction on the number of steps, after the simulation of $t$ steps of $M$, the tracks of $N$ contain the tapes of $M$ after $t$ steps, with the heads correctly marked, and the cells outside the converted zone hold the unvisited part of tape $1$. Hence, if $M$ halts, the final tape and head position of $N$ are those of tape $1$ of $M$, so $N$ halts in a standard final configuration exactly when $M$ does, with the same output; and if $M$ does not halt, neither does $N$.