Question

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

Short answer

The constructed Turing machine that computes the function \(f\left( n \right) = 3\left( {n + 2} \right) = {\bf{ }}3{\bf{ }}n + 6\) is

\(\begin{array}{l}T = \left( {S,I,f,{s_0}} \right),S = \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_0^{}',1,L} \right)\\\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_6^{}',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^{}',B,s_1^{}',1,L} \right),\left( {s_5^{}',0,s_2^{}',0,L} \right),\left( {s_5^{}',1,s_5^{}',1,L} \right)\\\left( {s_6^{}',0,s_6^{}',1,R} \right),\left( {s_6^{}',1,s_7^{}',1,R} \right),\left( {s_6^{}',B,s_7^{}',B,R} \right)\end{array}\)

Step-by-step solution

Definition

A Turing machine \(T = \left( {S,I,f,{s_0}} \right)\) consists of a finite set \(S\) of states, an alphabet \({\bf{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) = 3\left( {n + 2} \right) = 3{\bf{ }}n + 6\) for all nonnegative integers \(n\)

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

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

\(\begin{array}{l}{T_1} = \left( {{S_1},I,f,{s_0}} \right),{S_1} = \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(n) = 3n\)

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

\(\begin{array}{l}{T_2} = \left( {{S_2},I,f,{s_0}} \right),{S_2} = \left\{ {{s_0},{s_1},{s_2},{s_3},{s_4},{s_5},{s_6},{s_7}} \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_6},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},B,{s_1},1,L} \right),\left( {{s_5},0,{s_2},0,L} \right),\left( {{s_5},1,{s_5},1,L} \right)\\\left( {{s_6},0,{s_6},1,R} \right),\left( {{s_6},1,{s_7},1,R} \right),\left( {{s_6},B,{s_7},B,R} \right)\end{array}\)

Turing machine for \(f(n) = 3(n + 2)\)

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

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

Let us add an accent \({\bf{'}}\) 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 \({\bf{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 \({\bf{l}}\) remains unchanged.

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

Constructing of Turing machine

The relation \(f\) is then defined by all five-tuples in \({T_1}\) and \({T_2}\) where the final state \({S_2}\) 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) = 3\left( {n + 2} \right) = {\bf{ }}3{\bf{ }}n + 6\)is

\(\)\(\begin{array}{l}\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_0^{}',1,L} \right)\\\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_6^{}',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^{}',B,s_1^{}',1,L} \right),\left( {s_5^{}',0,s_2^{}',0,L} \right),\left( {s_5^{}',1,s_5^{}',1,L} \right)\\\left( {s_6^{}',0,s_6^{}',1,R} \right),\left( {s_6^{}',1,s_7^{}',1,R} \right),\left( {s_6^{}',B,s_7^{}',B,R} \right)\end{array}\)