Question

Show at each step the contents of the tape of the Turing machine in Example \(3\) starting with each of these strings.

\(\begin{array}{c}\begin{array}{*{20}{l}}{{\bf{a}}){\rm{ }}{\bf{0011}}}\\{{\bf{b}}){\rm{ }}{\bf{00011}}}\\{{\bf{c}}){\rm{ }}{\bf{101100}}}\end{array}\\{\bf{d}}){\rm{ }}{\bf{000111}}\end{array}\)

Short answer

a) \(0011\)String is recognized.

b) \(00011\)String is not recognized.

c) \(101100\)String is not recognized.

d) \(000111\)String is recognized.

Step-by-step solution

Step \({\bf{1}}\):Definition

A Turing machine \(T = \left( {S,I,f,{s_0}} \right)\) consists of a finite set \(S\) of states, an alphabet \(I\) containing the blank symbol \(B\), a partial function \(f\) from \(S \times I\) to \(S \times I \times {\rm{\{ }}R,L{\rm{\} }}\), and a starting state \({s_0}\).

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

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

\(\begin{array}{l}\left( {{s_1},B,{s_2},B,L} \right)\\\left( {{s_2},1,{s_3},M,L} \right)\\\left( {{s_3},1,{s_3},1,L} \right)\\\left( {{s_3},0,{s_4},0,L} \right)\end{array}\)

\(\begin{array}{l}\left( {{s_3},M,{s_5},M,R} \right)\\\left( {{s_4},0,{s_4},0,L} \right)\\\left( {{s_4},M,{s_0},M,R} \right)\\\left( {{s_5},M,{s_6},M,R} \right)\end{array}\)

(a)Step 2: Check whether the string is recognized or not

It starts from the initial state \({s_0}\) of the Turing machine \(T\). It places the string \(011\) on the tape. it starts from the first non-blank position on the tape. Note: The element labeled in blue represents the position in the tape.

\(...BB0011BB...\)

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

\(...BBM11BB...\)

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

\(...BBM11BB...\)

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

\(...BBM11BB...\)

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

\(...BBM011BB...\)

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

Check whether the string is recognized or not

\(...BBM011BB...\)

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

\(...BBM01MBB...\)

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

\(...BBM01MBB...\)

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

\(...BBM01MBB...\)

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

\(...BBM01MBB...\)

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

\(...BBMMMMB...\)

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

\( \ldots BBMM1MBB \ldots \)

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

Check whether the string is recognized or not

\( \ldots BBMMMBB \ldots \)

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

\( \ldots BBMMMMBB \ldots \)

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

\( \ldots BBMMMMBB \ldots \)

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

\( \ldots BBMMMMBB \ldots \)

Since it is at the final state \({s_6}\) while the position on the tape is M, the machine halts and recognizes the string (as there is no five-tuple that has \({s_6}\) as its first coordinate).

Therefore, the string is recognized.

 (b) Step 5: Check whether the string is recognized or not

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

\( \ldots BB00011BB \ldots \)

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

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

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

\( \ldots BBM0011BB \ldots \)

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

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

\( \ldots BBM011BB \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},B,L} \right)\). This implies that it moves to state \({s_2}\), the current position on the tape remains at B and it moves one position to the left on the tape.

\( \ldots BBM0011BB \ldots \)

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

Check whether the string is recognized or not

\( \ldots BBM001MBB \ldots \)

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

\( \ldots BBM001MBB \ldots \)

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

\( \ldots BBM001MBB \ldots \)

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

\( \ldots BBM01MBB \ldots \)

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

\( \ldots BBM001MBB \ldots \)

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

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

\( \ldots BBMM01MBB \ldots \)

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

Check whether the string is recognized or not

\( \ldots BBM01MBB \ldots \)

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

\( \ldots BBMM0MBB \ldots \)

Since, state \({s_2}\) while the position on the tape is 1, use the five-tuple \(\left( {{s_2},1,{s_3},M,L} \right)\). This implies that move to state \({s_3}\), the current position on the tape is changed to M and move one position to the left on the tape.

\( \ldots BBMM0MMBB \ldots \)

Since, state \({s_3}\) while the position on the tape is 0, use the five-tuple \(\left( {{s_3},0,{s_4},0,L} \right)\). This implies that move to state \({s_4}\), the current position on the tape remains 0 and move one position to the right on the tape.

\( \ldots BBMM0MMBB \ldots \)

Since, state \({s_4}\) while the position on the tape is M, use the five-tuple \(\left( {{s_4},M,{s_0},M,R} \right)\). This implies that move to state \({s_0}\), the current position on the tape remains M and move one position to the right on the tape.

\( \ldots BBMM0MMBB \ldots \)

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

\( \ldots BBMMMMMBB \ldots \)

Since it is at the non-final state \({s_1}\) while the position on the tape is M, the machine halts and does not recognize the string (as there is no five-tuple that contains \({s_1}\) as its first element and M as its second element).

Thus, the string is not recognized.

(c)Step 8: Check whether the string is recognized or not

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

\( \ldots BB101100BB \ldots \)

Since it is at the non-final state \({s_0}\) while the position on the tape is 1, the machine halts and does not recognize the string (as there is no five-tuple that contains \({s_0}\) as its first element and 1 as its second element).

Hence, the string is not recognized.

(d)Step 9: Check whether the string is recognized or not

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

\( \ldots BB000111BB \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},M,R} \right)\). This implies that it moves to state \({s_1}\), the current position on the tape is changed to M and it moves one position to the right on the tape.

\( \ldots BBM00111BB \ldots \)

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

\( \ldots BBM00111BB \ldots \)

Since, state \({s_1}\) while the position on the tape is 0, use the five-tuple \(\left( {{s_1},0,{s_1},0,R} \right)\). This implies that remain at state \({s_1}\), the current position on the tape remains at 0 and move one position the right on the tape.

\( \ldots BBMM0111BB \ldots \)

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

\( \ldots BBM00111BB \ldots \)

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

\( \ldots BBM0111BB \ldots \)

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

Check whether the string is recognized or not

\( \ldots BBM00111BB \ldots \)

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

\( \ldots BBM00111BB \ldots \)

Since, state \({s_2}\) while the position on the tape is 1, use the five-tuple \(\left( {{s_2},1,{s_3},M,L} \right)\). This implies that move to state \({s_3}\), the current position on the tape is changed to M and move one position to the left on the tape.

\( \ldots BBM0011MBB \ldots \)

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

\( \ldots BBM0011MBB \ldots \)

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

\( \ldots BBM0011MBB \ldots \)

Since, state \({s_3}\) while the position on the tape is 0, use the five-tuple \(\left( {{s_3},0,{s_4},0,L} \right)\). This implies that move to state \({s_4}\), the current position on the tape remains 0 and move one position to the left on the tape.

\( \ldots BBM0011MBB \ldots \)

Since, state \({s_3}\) while the position on the tape is 0, use the five-tuple \(\left( {{s_3},0,{s_4},0,L} \right)\). This implies that move to state \({s_4}\), the current position on the tape remains 0 and move one position to the left on the tape.

\( \ldots BBM0011MBB \ldots \)

Since, state \({s_4}\) while the position on the tape is M, use the five-tuple \(\left( {{s_4},M,{s_0},M,R} \right)\). This implies that move to state \({s_0}\), the current position on the tape remains M and move one position to the right on the tape.

Check whether the string is recognized or not

\( \ldots BBM011MBB \ldots \)

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

\( \ldots BBMM011MBB \ldots \)

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

\( \ldots BBMM11MBB \ldots \)

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

\( \ldots BBMM011MBB \ldots \)

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

\( \ldots BBMM011MBB \ldots \)

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

\( \ldots BBMM011MBB \ldots \)

Since, state \({s_2}\) while the position on the tape is 1, use the five-tuple \(\left( {{s_2},1,{s_3},M,L} \right)\). This implies that move to state \({s_3}\), the current position on the tape is changed to M and move one position to the left on the tape.

\( \ldots BBMM01MMBB \ldots \)

Since, state \({s_3}\) while the position on the tape is 1, use the five-tuple \(\left( {{s_3},1,{s_3},1,L} \right)\). This implies that move to state \({s_3}\), the current position on the tape remains 1 and move one position to the left on the tape.

Check whether the string is recognized or not

\( \ldots BBMM01MMBB \ldots \)

Since, state \({s_3}\) while the position on the tape is 0, use the five-tuple \(\left( {{s_3},0,{s_4},0,L} \right)\). This implies that move to state \({s_4}\), the current position on the tape remains 0 and move one position to the right on the tape.

\( \ldots BBMM01MMBB \ldots \)

Since, state \({s_4}\) while the position on the tape is M, use the five-tuple \(\left( {{s_4},M,{s_0},M,R} \right)\). This implies that move to state \({s_0}\), the current position on the tape remains M and move one position to the right on the tape.

\( \ldots BBMM01MMBB \ldots \)

Since, state \({s_0}\) while the position on the tape is 0, use the five-tuple[ss1] \(\left( {{s_0},0,{s_1},M,R} \right)\). This implies that move to state \({s_1}\), the current position on the tape is changed to M and move one position to the right on the tape.

\( \ldots BBMMMBMMBB \ldots \)

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

\( \ldots BBMMM1MMBB \ldots \)

[ss1]Do not use you, we, I in solution correct format

Check whether the string is recognized or not

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

\( \ldots BBMMM1MMBB \ldots \)

Since, state \({s_2}\) while the position on the tape is 1, use the five-tuple \(\left( {{s_2},1,{s_3},M,L} \right)\). This implies that move to state \({s_3}\), the current position on the tape is changed to M and move one position to the left on the tape.

\( \ldots BBMMMMMMBB \ldots \)

Since, state \({s_3}\) while the position on the tape is M, use the five-tuple \(\left( {{s_3},M,{s_5},M,R} \right)\). This implies that move to state \({s_5}\), the current position on the tape remains M and move one position to the right on the tape.

\( \ldots BBMMMMMMBB \ldots \)

Since, state \({s_5}\) while the position on the tape is M, use the five-tuple \(\left( {{s_5},M,{s_6},M,R} \right)\). This implies that move to state \({s_6}\), the current position on the tape remains M and move one position to the right on the tape.

\( \ldots BBMMMMMMBB \ldots \)

Since, at the final state \({s_6}\) while the position on the tape is M, the machine halts and recognizes the string (as there is no five-tuple that has \({s_6}\) as its first coordinate).

Therefore, the string is recognized.