Question

Let \(T\) be the Turing machine defined by the five-tuples: \(\left( {{s_0},0,{s_1},1,R} \right),\left( {{s_0},1,{s_1},0,R} \right),\left( {{s_0},B,{s_1},0,R} \right),\left( {{s_1},0,{s_2},1,L} \right),\left( {{s_1},1,{s_1},0,R} \right)\), and \(\left( {{s_1},B,{s_2},0,L} \right)\). For each of these initial tapes, determine the final tape when \(T\) halts, assuming that \(T\) begins in initial position.

\(a)\)

\(\begin{array}{*{20}{c}} \cdots &B&B&0&0&1&1&B&B& \cdots \end{array}\)

\(b)\)

\(\begin{array}{*{20}{c}} \cdots &B&B&1&0&1&B&B&B& \cdots \end{array}\)

\(c)\)

\(\begin{array}{*{20}{c}} \cdots &B&B&1&1&B&0&1&B& \cdots \end{array}\)

\(d)\)

\(\begin{array}{*{20}{c}} \cdots &B&B&B&B&B&B&B&B& \cdots \end{array}\)

Short answer

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

\((b)\)The final tape when \(T\) halts, assuming that \(T\) begins in initial position is \(011\).

\((c)\)The final tape when \(T\) halts, assuming that \(T\) begins in initial position is \(00001\).

\((d)\) The final tape when \(T\) halts, assuming that \(T\) begins in initial position is \(00\).

Step-by-step solution

Definition

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

\(\begin{array}{l}\left( {{s_0},0,{s_1},1,R} \right)\\\left( {{s_0},1,{s_1},0,R} \right)\\\left( {{s_0},B,{s_1},0,R} \right)\\\left( {{s_1},0,{s_2},1,L} \right)\\\left( {{s_1},1,{s_1},0,R} \right)\\\left( {{s_1},B,{s_2},0,L} \right)\end{array}\)

Determining the final tape

(a)

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

\({\bf{ \ldots BB0011BB \ldots }}\)

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

\({\bf{ \ldots BB1011BB \ldots }}\)

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

\({\bf{ \ldots BB1111BB \ldots }}\)

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

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

Determining the final tape

(b)

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

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

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

\({\bf{ \ldots BB001BBB \ldots }}\)

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

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

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

Therefore, the final tape then contains the string \(011\).

Determining the final tape

(c)

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

\({\bf{ \ldots BB11B01B \ldots }}\)

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

\({\bf{ \ldots BB01B01B \ldots }}\)

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

\({\bf{ \ldots BB00B01B \ldots }}\)

Since you are at state \({s_1}\) while the position on the tape is \(B\), you use the five-tuple \(\left( {{s_1},B,{s_2},0,L} \right)\). This implies that you move to state \({s_2}\), the current position on the tape is changed to \(0\) and you move one position to the left on the tape.

\({\bf{ \ldots BB00001B \ldots }}\)

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

Therefore, the final tape then contains the string \(00001\).

Determining the final tape

(d)

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

\({\bf{ \ldots BBBBBB \ldots }}\)

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

\({\bf{ \ldots BB0BBBBB \ldots }}\)

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

\( \ldots .BB00BBBB \ldots \)

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

Therefore, the final tape then contains the string \(00\).