Question

Construct a Turing machine with tape symbols \({\bf{0}}\),\({\bf{1}}\), and \({\bf{B}}\) that, when given a bit string as input, adds a \({\bf{1}}\) to the end of the bit string and does not change any of the other symbols on the tape.

Short answer

The constructed Turing machine 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}}}} \right\}\\{\bf{I = \{ 0,1,B\} }}\\\left( {{{\bf{s}}_{\bf{0}}}{\bf{,0,}}{{\bf{s}}_{\bf{0}}}{\bf{,0,R}}} \right)\\\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{,1,R}}} \right)\end{array}\)

Step-by-step solution

Step \({\bf{1}}\): Definition

A Turing machine \({\bf{T = }}\left( {{\bf{S,I,f,}}{{\bf{s}}_{\bf{0}}}} \right)\) contains a finite set \({\bf{S}}\) of states, an alphabet \({\bf{I}}\) containing the blank symbol \({\bf{B}}\), a starting state \({{\bf{s}}_{\bf{0}}}\) and a partial function from \({\bf{S \times I}}\)to \({\bf{S \times I \times \{ R,L\} }}\). Note: The partial function \({\bf{f}}\) is often represented as \(5\)-tuples.

It will require \(2\) states \({{\bf{s}}_{\bf{0}}}\) and \({{\bf{s}}_{\bf{1}}}\) (how to use these states is explained in the exercise below), which will be contained in the set \({\bf{S}}\).

\({\bf{S = }}\left\{ {{{\bf{s}}_{\bf{0}}}{\bf{,}}{{\bf{s}}_{\bf{1}}}} \right\}\)

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

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

Assuming the partial function into five tuples

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

As long as the input is a \({\bf{0}}\) or a \({\bf{1}}\), it will keep the input unchanged and move one position to the right (as it only want to add a \({\bf{1}}\) at the end of the tape).

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

Once it arrives at the first blank symbol, it will at a \({\bf{1}}\). Note that \({\bf{1}}\) will be added at the end of the bit string. It will then move to the state \({{\bf{s}}_{\bf{1}}}\) and move one position to the right.

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

Add any five-tuples that start from \({{\bf{s}}_{\bf{1}}}\) such that the algorithm ends once it reaches state \({{\bf{s}}_{\bf{1}}}\) (which is considered the final state).

Therefore, the constructed Turing machine with tape symbols\({\bf{0}}\),\({\bf{1}}\), and\({\bf{B}}\)that, when given a bit string as input, adds a\({\bf{1}}\)to the end of the bit string and does not change any of the other symbols on the tape is

\(\begin{array}{c}\left( {{{\bf{s}}_{\bf{0}}}{\bf{,0,}}{{\bf{s}}_{\bf{0}}}{\bf{,0,R}}} \right)\\\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{,1,R}}} \right)\end{array}\)