Union of Turing Machines

Theorem

Let $T_1, T_2$ be Turing machines.

Let $\Sigma_1, \Sigma_2$ be the input symbols of $T_1, T_2$, respectively.

Let $L_1, L_2$ be the languages accepted by $T_1, T_2$, respectively.

There exists a Turing machine $T$ such that:

• The input symbols of $T$ are $\Sigma_1 \cup \Sigma_2$.
• The language accepted by $T$ is $L_1 \cup L_2$.
• $T$ halts on some input if and only if it is in the accepted language, or both $T_1$ and $T_2$ halt on it.

Proof

Let:

$T_1 = \tuple {Q_1, \Sigma_1, \Gamma_1, \delta_1, q_1, B, F_1}$

$T_2 = \tuple {Q_2, \Sigma_2, \Gamma_2, \delta_2, q_2, B, F_2}$

As implied by the notation, the blank symbols of the two machines will be identified with each other, and denoted as $B$.

Construct the $2$-tape Turing machine $T' = \tuple{Q, \Sigma, \Gamma, \delta, q_0, B, F}$ as follows:

$Q = \set {q_0, q_L} \cup \paren {Q_1 \cup \set {q_H} } \times \paren {Q_2 \cup \set {q_H} }$

$\Sigma = \Sigma_1 \cup \Sigma_2$

$\Gamma = \Gamma_1 \cup \Gamma_2$

$F = F_1 \times Q_2 \cup Q_1 \times F_2$

$\map \delta {q, s, t} = \begin{cases}

\tuple {q_0, s, s, R, R} & : q = q_0 \land s \ne B \\ \tuple {q_L, B, B, L, L} & : q = q_0 \land s = B \\ \tuple {q_L, s, t, L, L} & : q = q_L \land s \ne B \\ \tuple {\tuple {q_1, q_2}, B, B, R, R} & : q = q_L \land s = B \\ \tuple {\tuple {a', b'}, s', t', d_1, d_2} & : q = \tuple {a, b} \end{cases}$

where $\tuple {a', s', d_1} = \map {\delta_1} {a, s}$ if $\map {\delta_1} {a, s}$ is defined, and $\tuple {a, s, S}$ otherwise; and likewise for $\delta_2$.

The following special cases will apply to $\delta$:

• $\map {\delta} {\tuple {q_H, q_H}, s, t}$ is undefined for any $s, t$
• $\map {\delta} {\tuple {a, b}, s, t}$ is undefined if at least one of $a \in F_1$ or $b \in F_2$ is true.

The state $q_0$ copies the input string from tape $1$ to tape $2$, until it encounters a blank.

State $q_L$ moves both tapes back to the start of the input string.

After this, $T_1$ and $T_2$ are represented on the two tapes of $T'$, in the natural way.

$T'$ will accept and halt when either machine enters one of its accepting states, as required.

When either machine halts, that is when $\map {\delta_1} {a, s}$ is undefined, $T'$ changes the respective state to $q_H$, and does not alter its tape or state after that.

If both machines halt without accepting, $T'$ does the same.

The result follows from Multitape Turing Machine Reduces to Turing Machine.

$\blacksquare$