Question

Construct a Turing machine with tape symbols \({\bf{0}}\),\({\bf{1}}\) and \({\bf{B}}\) that, given a bit string as input, replaces all \({\bf{0 's}}\) on the tape with \({\bf{1's}}\) and does not change any of the \({\bf{1's}}\) 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 all\({\bf{0 's}}\)on the tape with\({\bf{1's}}\)and does not change any of the\({\bf{1's}}\)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}}}} \right\}\\{\bf{I = \{ 0,1,B\} }}\\\left( {{{\bf{s}}_{\bf{0}}}{\bf{,0,}}{{\bf{s}}_0}{\bf{,}}0{\bf{,R}}} \right)\\\left( {{{\bf{s}}_{\bf{0}}}{\bf{,1,}}{{\bf{s}}_{\bf{0}}}{\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 \({\bf{1}}\) state \({{\bf{s}}_{\bf{0}}}\) ( \({{\bf{s}}_{\bf{0}}}\) is the start state and the final state), which will be contained in the set \({\bf{S}}\).

\({\bf{S = }}\left\{ {{{\bf{s}}_{\bf{0}}}} \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{1}}\), it will keep the input unchanged and move one position to the right (as you only want to change the \({\bf{0 's}}\)).

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

Every time the input is a \({\bf{0}}\), the \({\bf{0}}\) is changed to a \({\bf{1}}\) (as it wants to change all \({\bf{0 's}}\) to \({\bf{1's}}\)) and move one position to the right.

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

Once it arrives at the first blank symbol (while not having read any \({\bf{0 's}}\)), the machine needs to halt. The machine will halt if you do not add any five-tuples that have \({\bf{B}}\) is its second coordinate.

Therefore, the constructed Turing machine with tape symbols\({\bf{0}}\),\({\bf{1}}\)and\({\bf{B}}\)that, given a bit string as input, replaces all\({\bf{0 's}}\)on the tape with\({\bf{1's}}\)and does not change any of the\({\bf{1's}}\)on the tape is

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