Question

Construct a Turing machine with tape symbols \({\bf{0}}\),\({\bf{1}}\), and \({\bf{B}}\) that, given a bit string as input, replaces the first two consecutive \({\bf{1's}}\) on the tape with \({\bf{0 's}}\) and does not change any of the other symbols on the tape.

Short answer

The constructed Turing machine with tape symbols \({\bf{0}}\),\({\bf{1}}\), and \({\bf{B}}\) that, given a bit string as input, replaces the first two consecutive \({\bf{1's}}\) on the tape with \({\bf{0 's}}\) and does not change any of the other symbols on the tape 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}}}} \right\}\\{\bf{I = \{ 0,1,B\} }}\\\left( {{{\bf{s}}_{\bf{0}}}{\bf{,0,}}{{\bf{s}}_{\bf{1}}}{\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{3}}}{\bf{,B,R}}} \right)\\\left( {{{\bf{s}}_{\bf{1}}}{\bf{,1,}}{{\bf{s}}_{\bf{2}}}{\bf{,0,L}}} \right)\\\left( {{{\bf{s}}_{\bf{1}}}{\bf{,0,}}{{\bf{s}}_{\bf{0}}}{\bf{,0,R}}} \right)\\\left( {{{\bf{s}}_{\bf{1}}}{\bf{,B,}}{{\bf{s}}_{\bf{3}}}{\bf{,B,R}}} \right)\\\left( {{{\bf{s}}_{\bf{2}}}{\bf{,1,}}{{\bf{s}}_{\bf{3}}}{\bf{,0,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)\) consists of a finite set \({\bf{S}}\) of states, an alphabet \({\bf{I}}\) containing the blank symbol \({\bf{B}}\), a partial function \({\bf{f}}\) from \({\bf{S \times I}}\) to \({\bf{S \times I \times \{ R,L\} }}\), and a starting state \({{\bf{s}}_{\bf{0}}}\).

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 \({\bf{5}}\) -tuples.

It will require \(4\) states \({{\bf{s}}_{\bf{0}}}{\bf{,}}{{\bf{s}}_{\bf{1}}}{\bf{,}}{{\bf{s}}_{\bf{2}}}\) and \({{\bf{s}}_{\bf{3}}}\left( {{{\bf{s}}_{\bf{0}}}} \right)\) is the start state, \({{\bf{s}}_{\bf{1}}}\) will be the state that indicates that the previous input was a \({\bf{1}}\), \({{\bf{s}}_{\bf{2}}}\) will be used to change the first \({\bf{1}}\) of a pair of consecutive \({\bf{1's}}\) to \({\bf{0 's}}\) and \({{\bf{s}}_{\bf{3}}}\) will be the final state), which will be contained in the set \({\bf{S}}\).

\({\bf{S = }}\left\{ {{{\bf{s}}_{\bf{0}}}{\bf{,}}{{\bf{s}}_{\bf{1}}}{\bf{,}}{{\bf{s}}_{\bf{2}}}{\bf{,}}{{\bf{s}}_{\bf{3}}}} \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\} }}\)

Defining the partial function as five-tuples

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

As long as the input is a \({\bf{0}}\), it will keep the input unchanged and move one position to the right (as it only want to change the \({\bf{1's}}\)).

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

The first time the input is a \({\bf{1}}\), it moves to the state \({{\bf{s}}_{\bf{1}}}\) and keep the \({\bf{1}}\) unchanged. It then moves one position to the right.

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

Once it arrives at the first blank symbol, it will move to the final state \({{\bf{s}}_{\bf{3}}}\) as it reads the entire string.

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

Once itis at state \({{\bf{s}}_{\bf{1}}}\), it knows that the previous input was a \({\bf{1}}\) . If the input is then again, a \({\bf{1}}\), then it needs to change the \({\bf{1}}\) to a \({\bf{0}}\) and move to the state \({{\bf{s}}_{\bf{2}}}\). Then it also needs to move to the left such that it can change the first \({\bf{1}}\) of the pair of consecutive \({\bf{1's}}\).

\(\left( {{{\bf{s}}_{\bf{1}}}{\bf{,1,}}{{\bf{s}}_{\bf{2}}}{\bf{,0,L}}} \right)\)

Step 3:Distinguishing the partial function as five-tuples

If itis at state \({{\bf{s}}_{\bf{1}}}\) and have the input \({\bf{0}}\), then it moves back to state \({{\bf{s}}_{\bf{0}}}\) such that it can look for the first pair of consecutive \({\bf{1's}}\)in the remainder of the string.

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

If itis at state \({{\bf{s}}_{\bf{1}}}\) and come across a blank, then it moves to the final state \({{\bf{s}}_{\bf{3}}}\).

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

If itis at state \({{\bf{s}}_{\bf{2}}}\), then the input needs to be a \({\bf{1}}\) (as you are at the first \({\bf{1}}\) in the pair of consecutive \({\bf{1's}}\)). It will then change this \({\bf{1}}\) to a \({\bf{0}}\) and move to the final state \({{\bf{s}}_{\bf{3}}}\).

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

Once it in the final state \({{\bf{s}}_{\bf{3}}}\), the machine will need to halt as itis either at the end of the string or have change the first pair of consecutive \({\bf{1's}}\) to \({\bf{0 's}}\). This will occur when itdo not add a five-tuple that has \({{\bf{s}}_{\bf{3}}}\) as its first coordinate.

Therefore, the constructed Turing machine with tape symbols\({\bf{0}}\),\({\bf{1}}\), and\({\bf{B}}\)that, given a bit string as input, replaces the first two consecutive\({\bf{1's}}\)on the tape with\({\bf{0 's}}\)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{1}}}{\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{3}}}{\bf{,B,R}}} \right)\\\left( {{{\bf{s}}_{\bf{1}}}{\bf{,1,}}{{\bf{s}}_{\bf{2}}}{\bf{,0,L}}} \right)\\\left( {{{\bf{s}}_{\bf{1}}}{\bf{,0,}}{{\bf{s}}_{\bf{0}}}{\bf{,0,R}}} \right)\\\left( {{{\bf{s}}_{\bf{1}}}{\bf{,B,}}{{\bf{s}}_{\bf{3}}}{\bf{,B,R}}} \right)\\\left( {{{\bf{s}}_{\bf{2}}}{\bf{,1,}}{{\bf{s}}_{\bf{3}}}{\bf{,0,R}}} \right)\end{array}\)