Question

Construct a Turing machine that computes the function \({\bf{f(n) = n - 3}}\) if \({\bf{n}} \ge {\bf{3}}\) and \({\bf{f}}\left( {\bf{n}} \right){\bf{ = 0}}\) for \({\bf{n = 0,1,2}}\) for all non-negative integers \({\bf{n}}\).

Short answer

The constructed Turing machine that computes the function \(f{\rm{(}}n{\rm{)}} = n - 3\) if \(n \ge 3\) and \(f\left( n \right) = 0\) for \(n = 0,1,2\)for all non-negative integers n is

\(\begin{array}{c}{\bf{T = }}\left( {{\bf{S,I,f,}}{{\bf{s}}_{\bf{0}}}} \right)\\{\bf{S = }}\left\{ {{{\bf{s}}_{\bf{0}}}{\bf{,}}{{\bf{s}}_{\bf{1}}}{\bf{,}}{{\bf{s}}_{\bf{2}}}{\bf{,}}{{\bf{s}}_{\bf{3}}}{\bf{,}}{{\bf{s}}_{\bf{4}}}} \right\}\\{\bf{I = \{ 0,1,B\} }}\\\left( {{{\bf{s}}_{\bf{0}}}{\bf{,1,}}{{\bf{s}}_{\bf{1}}}{\bf{,B,R}}} \right)\\\left( {{{\bf{s}}_{\bf{1}}}{\bf{,1,}}{{\bf{s}}_{\bf{2}}}{\bf{,B,R}}} \right)\\\left( {{{\bf{s}}_{\bf{1}}}{\bf{,B,}}{{\bf{s}}_{\bf{4}}}{\bf{,1,R}}} \right)\\\left( {{{\bf{s}}_{\bf{2}}}{\bf{,1,}}{{\bf{s}}_{\bf{3}}}{\bf{,B,R}}} \right)\\\left( {{{\bf{s}}_{\bf{2}}}{\bf{,B,}}{{\bf{s}}_{\bf{4}}}{\bf{,1,R}}} \right)\\\left( {{{\bf{s}}_{\bf{3}}}{\bf{,1,}}{{\bf{s}}_{\bf{4}}}{\bf{,1,R}}} \right)\\\left( {{{\bf{s}}_{\bf{3}}}{\bf{,B,}}{{\bf{s}}_{\bf{4}}}{\bf{,1,R}}} \right)\end{array}\)

Step-by-step solution

Step \({\bf{1}}\):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 {\rm{\{ }}R,L{\rm{\} }}\), and a starting state \({s_0}\).

Given:

\(f(n) = n - 3\)if \(n \ge 3\) and \(f\left( n \right) = 0\) if \(n = 0,1,2\)

n is represented by \(n + 1\) ones.

The Turing machine computes the function by subtracting 3 when it removes the three leading 1’s at the beginning of the number.

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

Form of constructing machine

You will require 5 states \({s_0},{s_1},{s_2},{s_3}\) and \({s_4}\left( {{s_0}} \right)\) is the start state, \({s_1}\) will be the state that is used to remove the second1,\({s_2}\) is the state that will be used to remove the third 1, \({s_3}\) will be used to check if the input is 2 or not, and \({s_4}\) will be the final state), which will be contained in the set S.

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

The alphabet I needs to contain the tape symbols. The tape symbols are given as 0,1 and B.

\(I = {\rm{\{ }}0,1,B{\rm{\} }}\)

Construction of Turing machine

Next, you will define the partial function as five tuples.

You remove the first leading one by replacing the first 1 in the string by B.

You then move to state \({s_1}\) (where you will remove the second 1) and move one position to the right.

\(\left( {{{\bf{s}}_{\bf{0}}}{\bf{,1,}}{{\bf{s}}_{\bf{1}}}{\bf{,B,R}}} \right)\)

Once you are at state \({s_1}\), you know that a 1 was removed at the beginning of the string. If the input is a 1, then you can remove the second 1 by replacing the 1 by B. You then also move to the state \({s_2}\) (where you will remove the third 1).

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

Construction of Turing machine

However, if the second element was a blank B instead, then the input was 0 and thus you then need to return 0 (while the string at this point will contain only B’s). This then means that it is sufficient to then move the machine to the final state \({s_4}\) while changing one of the B’s to 1.

\(\left( {{s_1},B,{s_4},1,R} \right)\)

Once you are at state \({s_2}\), you know that two 1’swere removed at the beginning of the string. If the input is a 1, then you can remove the third 1 by replacing the 1 by B. You then also move to the state \({s_3}\) (as the three leading 1’swere removed).

\(\left( {{s_2},1,{s_3},B,R} \right)\)

Construction of Turing machine

However, if the third element was a blank B instead, then the input was 1 and thus you then need to return 0 (while the string at this point will contain only B’s). This then means that it is sufficient to then move the machine to the final state \({s_4}\) while changing one of the B’s to 1.

\(\left( {{s_2},B,{s_4},1,R} \right)\)

Once you are at state \({s_3}\), you know that three1’swere removed at the beginning of the string. If the input is a 1, then you can leave the 1 untouched and simply move to the final state \({s_4}\).

\(\left( {{s_3},1,{s_4},1,R} \right)\)

Construction of Turing machine

If the first input is a blank B, then the input was a 2 was thus you then need to return 0 (while the string at this point will contain onlyB’s). This then means that it is sufficient to then move the machine to the final state \({s_4}\) while changing one of the B’sto 1.

\(\left( {{s_3},B,{s_4},1,R} \right)\)

Finally, you add no five-tuples that have \({s_3}\) as its first element such that the machine always halts when you arrive at state \({s_3}\). Note that the machine will halt in the final state \({s_3}\) when the string has the three leading 1’s removed (if they exist).

Therefore, the constructed Turing machine that computes the function \(f{\rm{(}}n{\rm{)}} = n - 3\) if \(n \ge 3\) and \(f\left( n \right) = 0\) for \(n = 0,1,2\)for all non-negative integers n is

\(\begin{array}{c}\left( {{{\bf{s}}_{\bf{0}}}{\bf{,1,}}{{\bf{s}}_{\bf{1}}}{\bf{,B,R}}} \right)\\\left( {{{\bf{s}}_{\bf{1}}}{\bf{,1,}}{{\bf{s}}_{\bf{2}}}{\bf{,B,R}}} \right)\\\left( {{{\bf{s}}_{\bf{1}}}{\bf{,B,}}{{\bf{s}}_{\bf{4}}}{\bf{,1,R}}} \right)\\\left( {{{\bf{s}}_{\bf{2}}}{\bf{,1,}}{{\bf{s}}_{\bf{3}}}{\bf{,B,R}}} \right)\\\left( {{{\bf{s}}_{\bf{2}}}{\bf{,B,}}{{\bf{s}}_{\bf{4}}}{\bf{,1,R}}} \right)\\\left( {{{\bf{s}}_{\bf{3}}}{\bf{,1,}}{{\bf{s}}_{\bf{4}}}{\bf{,1,R}}} \right)\\\left( {{{\bf{s}}_{\bf{3}}}{\bf{,B,}}{{\bf{s}}_{\bf{4}}}{\bf{,1,R}}} \right)\end{array}\)