Question

Construct a Turing machine that computes the function \(f\left( {{n_1},{n_2}} \right) = {n_2} + 2\) for all pairs of nonnegative integers \({n_1}\) and \({n_2}\).

Short answer

The constructed Turing machine that computes the function\(f\left( {{n_1},{n_2}} \right) = {n_2} + 2\) for all pairs of nonnegative integers \({n_1}\) and \({n_2}\) is

\(\begin{array}{c}T = \left( {S,I,f,{s_0}} \right),S = \left\{ {{s_0},{s_1},{s_2}} \right\},I = \{ 0,1,B\} ,\\\left( {{s_0},1,{s_0},B,R} \right),\left( {{s_0},*,{s_1},1,L} \right),\left( {{s_1},B,{s_2},1,L} \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 \(I\) containing the blank symbol \(B\), a partial function \(f\) from \(S \times I\) to \(S \times I \times \left\{ {R,L} \right\}\), and a starting state \({s_0}\).

Given:

\(f\left( {{n_1},{n_2}} \right) = {n_2} + 2\)for all nonnegative integers \({n_1}\) and \({n_2}\)

\(n\)is represented by \(n + 1\) ones, while the two integers \({n_1}\) and \({n_2}\) are separated by \(*\) in the input. You can then obtain \({n_1} + {n_2}\)by removing all \({\bf{1}}\)’s of \({n_1}\) (before the \({\bf{*}}\) ) and adding two \(1's\) at the beginning of \({n_2}\).

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

Form of constructing machine

Require 3 states \({s_0},{s_1}\), and \({s_2}\left( {{s_0}} \right)\) is the start state, and \({s_2}\) will be the final state), which will be contained in the set \(S\).

\(S = \left\{ {{s_0},{s_1},{s_2}} \right\}\)

The alphabet \(I\) needs to contain the tape symbols. The tape symbols are given as \({\bf{0}}\),\({\bf{1}}\) and \(B\).

\(I = \left\{ {0,1,B} \right\}\)

\(\left( {{s_0},1,{s_0},B,R} \right)\)

Defining partial function as five-tuples

Next, define the partial function as five tuples.

First determine the last \({\bf{1}}\) in the string of \({n_1}\), thus move to the right as long as the input is a \({\bf{1}}\) which replace by blanks \(B\) (while remaining at the same state) and move to the next state \({s_1}\) when the input is \({\bf{*}}\) which change to a \({\bf{1}}\) (as this will then be the first added \({\bf{1}}\) to the string of \({n_2}\) ).

\(\begin{array}{l}\left( {{s_0},1,{s_0},B,R} \right){\bf{ }}\\\left( {{s_0},*,{s_1},1,L} \right)\end{array}\)

Construction of Turing machine

Once at state \({s_1}\), know that the input is the first blank preceding the string of \({n_2}\) with an additional \({\bf{1}}\), which change to a 1 and then add two additional \(1's\) to the string. Then also move to the final state \({s_2}\).

\(\left( {{s_1},B,{s_2},1,L} \right)\)

Finally, add no five-tuples that have \({s_2}\) as its first element such that the machine always halts when arrive at state \({s_2}\). Note that the machine will halt in the final state \({{\bf{s}}_{\bf{2}}}\) when the string has 2 additional \(1's\) to the string of \({n_2}\) (with the string of \({n_1}\) removed).

Therefore, the constructed Turing machine that computes the function\(f\left( {{n_1},{n_2}} \right) = {n_2} + 2\)for all pairs of nonnegative integers\({n_1}\)and\({n_2}\)is

\(\left( {{s_0},1,{s_0},B,R} \right),\left( {{s_0},*,{s_1},1,L} \right),\left( {{s_1},B,{s_2},1,L} \right)\)