Question

Let \({\bf{T}}\) be the Turing machine defined by the five tuples: \(\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{1}}}{\bf{,0,L}}} \right)\),\(\left( {{{\bf{s}}_{\bf{0}}}{\bf{,B,}}{{\bf{s}}_{\bf{1}}}{\bf{,1,R}}} \right)\),\(\left( {{{\bf{s}}_{\bf{1}}}{\bf{,0,}}{{\bf{s}}_{\bf{2}}}{\bf{,1,R}}} \right)\),\(\left( {{{\bf{s}}_{\bf{1}}}{\bf{,1,}}{{\bf{s}}_{\bf{1}}}{\bf{,1,R}}} \right)\),\(\left( {{{\bf{s}}_{\bf{1}}}{\bf{,B,}}{{\bf{s}}_{\bf{2}}}{\bf{,0,R}}} \right)\), and \(\left( {{{\bf{s}}_{\bf{2}}}{\bf{,B,}}{{\bf{s}}_{\bf{3}}}{\bf{,0,R}}} \right)\). For each of these initial tapes, determine the final tape when \({\bf{T}}\) halts, assuming that \({\bf{T}}\) begins in initial position.

a)

... B B 0 1 0 1 B B ...

b)

... B B 1 1 1 B B B ...

c)

... B B 0 0 B 0 0 B ...

d)

.... B B B B B B B B ...

Short answer

\((a)\)The final tape when \(T\) halts, assuming that \(T\) begins in initial position is \({\bf{0111}}\).

\((b)\)The final tape when \(T\) halts, assuming that \(T\) begins in initial position is \({\bf{0011}}\).

\((c)\)The final tape when \(T\) halts, assuming that \(T\) begins in initial position is \({\bf{01000}}\).

\((d)\)The final tape when \(T\) halts, assuming that \(T\) begins in initial position is \({\bf{100}}\).

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{1}}}{\bf{,0,R}}} \right)\)

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

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

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

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

Determining the final tape

(a)

It starts from the initial state \({{\bf{s}}_{\bf{0}}}\) of the Turing machine \({\bf{T}}\). It starts from the first non-blank position on the tape.

\(...{\bf{BB0101BB \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{,0,}}{{\bf{s}}_{\bf{1}}}{\bf{,0,R}}} \right)\). This implies that it moves to state \({{\bf{s}}_{\bf{1}}}\), the current position on the tape remains \({\bf{0}}\) and it moves one position to the right on the tape.

\({\bf{ \ldots BB0101BB \ldots }}\)

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

\({\bf{ \ldots BB0101BB \ldots }}\)

Since itis at state \({{\bf{s}}_{\bf{1}}}\) while the position on the tape is \({\bf{0}}\), it uses the five-tuple \(\left( {{{\bf{s}}_{\bf{1}}}{\bf{,0,}}{{\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 is changed to \({\bf{1}}\) and it moves one position to the right on the tape.

\({\bf{ \ldots BB0111BB \ldots }}\)

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

Hence, the final tape then contains the string \({\bf{0111}}\).

Determining the final tape

(b)

It starts from the initial state \({{\bf{s}}_{\bf{0}}}\) of the Turing machine \({\bf{T}}\). It starts from the first non-blank position on the tape.

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

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

\({\bf{ \ldots BB011BBB \ldots }}\)

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

\({\bf{ \ldots B0011BBB \ldots }}\)

Since itis at state \({{\bf{s}}_{\bf{2}}}\) while the position on the tape is \({\bf{0}}\), the machine halts (as there is no five-tuple that has \({{\bf{s}}_{\bf{2}}}\) as its first coordinate and \({\bf{0}}\) as its second coordinate). Hence, the final tape then contains the string \({\bf{0011}}\).

Step 4:Determining the final tape

(c)

It starts from the initial state \({{\bf{s}}_{\bf{0}}}\) of the Turing machine \({\bf{T}}\). It starts from the first non-blank position on the tape.

\({\bf{ \ldots BB00B00B \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{,0,}}{{\bf{s}}_{\bf{1}}}{\bf{,0,R}}} \right)\). This implies that it moves to state \({{\bf{s}}_{\bf{1}}}\), the current position on the tape remains at \({\bf{0}}\) and it moves one position to the right on the tape.

\({\bf{ \ldots BB00B00B \ldots }}\)

Since itis at state \({{\bf{s}}_{\bf{1}}}\) while the position on the tape is \({\bf{0}}\), it uses the five-tuple \(\left( {{{\bf{s}}_{\bf{1}}}{\bf{,0,}}{{\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 is changed to \({\bf{1}}\) and it moves one position to the right on the tape.

\({\bf{ \ldots BB01B00B \ldots }}\)

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

\({\bf{ \ldots BB01000B \ldots }}\)

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

Hence, the final tape then contains the string \({\bf{01000}}\).

Determining the final tape

(d)

It starts from the initial state \({{\bf{s}}_{\bf{0}}}\) of the Turing machine \({\bf{T}}\). It starts from some blank position on the tape (as there are no non-blank positions).

\({\bf{ \ldots BBBBBBBB \ldots }}\)

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

\({\bf{ \ldots BB1BBBBB \ldots }}\)

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

\({\bf{ \ldots BB10BBBB \ldots }}\)

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

\({\bf{ \ldots BB100BBB \ldots }}\)

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

Hence, the final tape then contains the string \({\bf{100}}\).