Question

What does the Turing machine described by the five-tuples \(\left( {{{\bf{s}}_{\bf{0}}}{\bf{,0,}}{{\bf{s}}_{\bf{0}}}{\bf{,1,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{,B,L}}} \right)\), \(\left( {{{\bf{s}}_{\bf{1}}}{\bf{,1,}}{{\bf{s}}_{\bf{2}}}{\bf{,1,R}}} \right)\)do when given

\({\bf{a)}}\)\({\bf{101}}\)as input\(?\)

\({\bf{b)}}\)an arbitrary bit string as input\(?\)

Short answer

\((a)\)The final tape contains the string \({\bf{1}}11\).

\((b)\) Every input string of length \(n\) is changed to a string consisting of \(n\)\(1{\bf{'s}}\).

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}}}\).

\({\bf{T}}\)is defined by the following five-tuples:

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

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

\(\begin{array}{l}\left( {{{\bf{s}}_{\bf{0}}}{\bf{,B,}}{{\bf{s}}_{\bf{1}}}{\bf{,B,L}}} \right)\\\left( {{{\bf{s}}_{\bf{1}}}{\bf{,1,}}{{\bf{s}}_{\bf{2}}}{\bf{,1,R}}} \right)\end{array}\)

Finding the final tape

(a)

It starts from the initial state \({{\bf{s}}_{\bf{0}}}\) of the Turing machine \({\bf{T}}\). The tape needs to contain \({\bf{1}}\)\({\bf{0}}\)\({\bf{1}}\) and it starts from the first non-blank position on the tape.

\({\bf{ \ldots BB101BBB \ldots }}\)

Since itis at state \({{\bf{s}}_{\bf{0}}}\) while the position on the tape is \({\bf{0}}\), it uses the five-tuple \(\left( {{{\bf{s}}_{\bf{0}}}{\bf{,1,}}{{\bf{s}}_{\bf{0}}}{\bf{,1,R}}} \right)\). This implies that it remains state \({{\bf{s}}_{\bf{0}}}\), the current position on the tape remains \({\bf{1}}\) and it moves one position to the right on the

tape.

\({\bf{ \ldots BB101BBB \ldots }}\)

Since itis at state \({{\bf{s}}_{\bf{0}}}\) while the position on the tape is \({\bf{1}}\), you use the five-tuple \(\left( {{{\bf{s}}_{\bf{0}}}{\bf{,0,}}{{\bf{s}}_{\bf{0}}}{\bf{,1,R}}} \right)\). This implies that it remains at state \({{\bf{s}}_{\bf{0}}}\), the current position on the tape is changed to \({\bf{1}}\) and it moves one position to the right on the tape.

\({\bf{ \ldots BB111BBB \ldots }}\)

Finding the final tape

Since itis at state \({{\bf{s}}_{\bf{0}}}\) while the position on the tape is \({\bf{0}}\), it uses the five-tuple \(\left( {{{\bf{s}}_{\bf{0}}}{\bf{,1,}}{{\bf{s}}_{\bf{0}}}{\bf{,1,R}}} \right)\). This implies that it remains state \({{\bf{s}}_{\bf{0}}}\), the current position on the tape remains \({\bf{1}}\) and it moves one position to the right on the tape.

\({\bf{ \ldots BB111BBB \ldots }}\)

Since itis at state \({{\bf{s}}_{\bf{0}}}\) while the position on the tape is B, it uses the five-tuple \(\left( {{{\bf{s}}_{\bf{0}}}{\bf{,B,}}{{\bf{s}}_{\bf{1}}}{\bf{,B,L}}} \right)\). This implies that it moves to state \({{\bf{s}}_{\bf{1}}}\), the current position on the tape remains \({\bf{B}}\) and it moves one position to the left on the tape.

\({\bf{ \ldots BB111BBB \ldots }}\)

Since it is at state \({{\bf{s}}_{\bf{1}}}\) while the position on the tape is \({\bf{1}}\), it uses the five-tuple \(\left( {{{\bf{s}}_{\bf{1}}}{\bf{,1,}}{{\bf{s}}_{\bf{2}}}{\bf{,1,R}}} \right)\). This implies that it moves to state \({{\bf{s}}_{\bf{2}}}\), the current position on the tape remains \({\bf{1}}\) and it moves one position to the right on the tape.

\({\bf{ \ldots BB111BBB \ldots }}\)

Since itis at state \({{\bf{s}}_{\bf{2}}}\)while the position on the tape is \({\bf{B}}\), the machine halts (as there is no five-tuple that has \({{\bf{s}}_{\bf{2}}}\)as its first coordinate).

Therefore, the final tape then contains the string \({\bf{1}}11\) .

Step 4:Verifying the input

It starts from the state \({{\bf{s}}_{\bf{0}}}\).

Due to the five-tuple \(\left( {{{\bf{s}}_{\bf{0}}}{\bf{,0,}}{{\bf{s}}_{\bf{0}}}{\bf{,1,R}}} \right)\), it changes all \({\bf{0}}\) -digits to \({\bf{1}}\).

Due to the five-tuples \(\left( {{{\bf{s}}_{\bf{0}}}{\bf{,1,}}{{\bf{s}}_{\bf{0}}}{\bf{,1,R}}} \right)\) and \(\left( {{{\bf{s}}_{\bf{1}}}{\bf{,1,}}{{\bf{s}}_{\bf{2}}}{\bf{,1,R}}} \right)\)all \({\bf{1}}\)-digits remain \({\bf{1}}\).

Due to the five-tuple \(\left( {{{\bf{s}}_{\bf{0}}}{\bf{,B,}}{{\bf{s}}_{\bf{1}}}{\bf{,B,L}}} \right)\), the string keeps the same size.

Hence, every input string of length \(n\) is changed to a string consisting of \(n\)\(1{\bf{'s}}\).