Question

Suppose that and \({T_2}\) are Turing machines with disjoint sets of states \({S_1}\) and \({S_2}\)and with transition functions \({f_1}\) and \({f_2}\), respectively. We can define the Turing machine \({{\bf{T}}_{\bf{1}}}{{\bf{T}}_2}\), the composite of \({{\bf{T}}_{\bf{1}}}\) and \({{\bf{T}}_2}\), as follows. The set of states of \({T_1}{T_2}\) is \({S_1} \cup {S_2}\) . \({T_1}{T_2}\) begins in the start state of \({{\bf{T}}_{\bf{1}}}\). It first executes the transitions of \({{\bf{T}}_{\bf{1}}}\) using \({f_1}\) up to, but not including, the step at which \({{\bf{T}}_{\bf{1}}}\) would halt. Then, for all moves for which \({{\bf{T}}_{\bf{1}}}\) halts, it executes the same transitions of \({{\bf{T}}_{\bf{1}}}\) except that it moves to the start state of \({{\bf{T}}_2}\). From this point on, the moves of \({{\bf{T}}_{\bf{1}}}{{\bf{T}}_2}\) are the same as the moves of \({{\bf{T}}_2}\).

By finding the composite of the Turing machines you constructed in Exercises \(18\) and \(22\), construct a Turing machine that computes the function \(f\left( n \right) = 2 n + 2\).

Short answer

The constructed Turing machine that computes the function \(f\left( n \right) = 2 n + 2\) is

\(\begin{aligned}T = \left( {S,I,f,{s_0}} \right),S = \left\{ {{s_0},{s_1},{s_2},{s_3},{s_4},{s_5}{s_6},s_0',s_1',s_2'} \right\},I = \{ 0,1,B\} ,\\\left( {{s_0},1,{s_0},1,R} \right),\left( {{s_0},B{s_1},B,L} \right),\left( {{s_1},1,{s_2},0,L} \right),\left( {{s_2},0,{s_2},0,L}\right),\\\left( {{s_2},1,{s_3},0,R} \right),\left( {{s_2},B,{s_5},B,R} \right),\left( {{s_3},0,{s_3},0,R} \right),\left( {{s_3},1,{s_3},1,R} \right),\\\left( {{s_3},B,{s_4},1,L}\right),\left( {{s_4},0,{s_2},0,L} \right),\left( {{s_4},1,{s_4},1,L} \right),\left( {{s_5},0,{s_5},1,R} \right),\\\left( {{s_5},1,s_0',1,R} \right),\left( {{s_5},B,s_0',B,R}\right),\left( {s_0',0,s_0',0,L} \right),\left({s_0',0,s_0',1,L} \right), \\\left({s_0',B,s_1',1,L} \right),\left( {s_1',B,s_2',1,L} \right)\end{aligned}\)

Step-by-step solution

Definition

A Turing machine \(T = \left( {S,I,f,{s_0}} \right)\) consists of a finite setSof states, an alphabet \(I\) containing the blank symbol \(B\), a partial function \(f\) from \(S \times I\) to \(S \times I \times \{ R,L\} \), and a starting state \({s_0}\).

Given:

\(f\left( n \right) = 2 n + 2\)for all nonnegative integers \(n\)

Note: The partial function \(f\) is often represented as \(5{\bf{ - }}\)tuples.

Turing machine for \(f\left( n \right) = 2 n\)

Turing machine for \(f\left( n \right) = 2 n\) (which was determined in a previous exercise):

\(\begin{aligned}{T_1} = \left( {{S_1},I,f,{s_0}} \right),{S_1} = \left\{ {{s_0},{s_1},{s_2},{s_3},{s_4},{s_5},{s_6}} \right\},I = \{ 0,1,B\} ,\\\left( {{s_0},1,{s_0},1,R} \right),\left( {{s_0},B,{s_1},B,L} \right),\left( {{s_1},1,{s_2},0,L} \right),\left( {{s_2},0,{s_2},0,L} \right),\\\left( {{s_2},1,{s_3},0,R} \right),\left( {{s_2},B,{s_5},B,R} \right),\left( {{s_3},0,{s_3},0,R} \right),\left( {{s_3},1,{s_3},1,R} \right),\\\left( {{s_3},B,{s_4},1,L} \right),\left( {{s_4},0,{s_2},0,L} \right),\left( {{s_4},1,{s_4},1,L} \right),\left( {{s_5},0,{s_5},1,R} \right),\\\left( {{s_5},1,{s_6},1,R} \right),\left( {{s_5},B,{s_6},B,R} \right)\end{aligned}\)

Turing machine for \(f\left( n \right) = n + 2\)

Turing machine for \(f\left( n \right) = n + 2\)(which was determined in a previous exercise):

\(\begin{array}{c}{T_2} = \left( {{S_2},I,f,{s_0}} \right),{S_2} = \left\{ {{s_0},{s_1},{s_2}} \right\},I = \{ 0,1,B\} ,\\\left( {{s_0},0,{s_0},0,L} \right),\left( {{s_0},0,{s_0},1,L} \right),\left( {{s_0},B,{s_1},1,L} \right),\left( {{s_1},B,{s_2},1,L} \right)\end{array}\)

Turing machine for \(f\)

Turing machine for \(f\left( n \right) = 2 n + 2\)

Obtain a Turing machine for \(f\left( n \right) = 2 n + 2\) by finding the composite of \({T_1}\) and \({T_2}\)

Let us add an accent \('\) to all states of one of the Turing machines (such that you are able to differentiate between the states of the two Turing machines).

The Turing machine \(T\) that is the composite of \({T_1}\) and \({T_2}\) then has the same starting state of \({T_1}\) (while the final state is the final state of \({T_2}\)), while the set \({\bf{S}}\) of states contains all states in \({S_1}\) and \({S_2}\), and \(I\) remains unchanged.

\(T = \left( {S,I,f,{s_0}} \right),S = {S_1} \cup {S_2} = \left\{ {{s_0},{s_1},{s_2},{s_3},{s_4},{s_5},s_0',s_1',s_2'} \right\},I = \{ 0,1,B\} \)

Defining \(f\)by all five-tuples

The relation \(f\) is then defined by all five-tuples in \({T_1}\) and \({T_2}\) where the final state \({s_6}\) in \({T_1}\) is replaced by the starting state \(s_0'\) in \({T_2}\)

Hence, the constructed Turing machine that computes the function \(f\left( n \right) = 2 n + 2\) is

\(\begin{aligned}\left( {{{\bf{s}}_{\bf{0}}}{\bf{,1,}}{{\bf{s}}_{\bf{0}}}{\bf{,1,R}}} \right),\left( {{{\bf{s}}_{\bf{0}}}{\bf{,B,}}{{\bf{s}}_{\bf{1}}}{\bf{,B,L}}} \right),\left( {{{\bf{s}}_{\bf{1}}}{\bf{,1,}}{{\bf{s}}_{\bf{2}}}{\bf{,0,L}}} \right),\left( {{{\bf{s}}_{\bf{2}}}{\bf{,0,}}{{\bf{s}}_{\bf{2}}}{\bf{,0,L}}} \right),\\\left( {{{\bf{s}}_{\bf{2}}}{\bf{,1,}}{{\bf{s}}_{\bf{3}}}{\bf{,0,R}}} \right),\left( {{{\bf{s}}_{\bf{2}}}{\bf{,B,}}{{\bf{s}}_{\bf{5}}}{\bf{,B,R}}} \right),\left( {{{\bf{s}}_{\bf{3}}}{\bf{,0,}}{{\bf{s}}_{\bf{3}}}{\bf{,0,R}}} \right),\left( {{{\bf{s}}_{\bf{3}}}{\bf{,1,}}{{\bf{s}}_{\bf{3}}}{\bf{,1,R}}} \right),\\\left( {{{\bf{s}}_{\bf{3}}}{\bf{,B,}}{{\bf{s}}_{\bf{4}}}{\bf{,1,L}}} \right),\left( {{{\bf{s}}_{\bf{4}}}{\bf{,0,}}{{\bf{s}}_{\bf{2}}}{\bf{,0,L}}} \right),\left( {{{\bf{s}}_{\bf{4}}}{\bf{,1,}}{{\bf{s}}_{\bf{4}}}{\bf{,1,L}}} \right),\left( {{{\bf{s}}_{\bf{5}}}{\bf{,0,}}{{\bf{s}}_{\bf{5}}}{\bf{,1,R}}} \right),\\\left( {{{\bf{s}}_{\bf{5}}}{\bf{,1,s}}_{\bf{0}}^{}{\bf{',1,R}}} \right),\left( {{{\bf{s}}_{\bf{5}}}{\bf{,B,s}}_{\bf{0}}^{}{\bf{',B,R}}} \right),\left( {{\bf{s}}_{\bf{0}}^{}{\bf{',0,s}}_{\bf{0}}^{}{\bf{',0,L}}} \right),\left( {{\bf{s}}_{\bf{0}}^{}{\bf{',0,s}}_{\bf{0}}^{}{\bf{',1,L}}} \right),\\\left( {{\bf{s}}_{\bf{0}}^{}{\bf{',B,s}}_{\bf{1}}^{}{\bf{',1,L}}} \right),\left( {{\bf{s}}_1^{}{\bf{',B,s}}_2^{}{\bf{',1,L}}} \right)\end{aligned}\)