Question

What does the Turing machine described by the five-tuples \(\left( {{s_0},1,{s_1},0,R} \right),\left( {{s_1},1,{s_1},1,R} \right),\left( {{s_1},0,{s_2},0,R} \right),\left( {{s_2},0,{s_3},1,L} \right),\;\left( {{s_2},1,{s_2},1,R} \right),\;\left( {{s_3},1,{s_3},1,L} \right),\)\(\left( {{s_3},0,{s_4},0,L} \right),\left( {{s_4},1,{s_4},1,L} \right)\), and \(\left( {{s_4},0,{s_0},1,R} \right)\) do when given

\(a)\)\(11\)as input\(?\)

\(b)\)a bit string consisting entirely of \(1\)s as input\(?\)

Short answer

\(a)\)Machine halts with \({\bf{01}}\) on the tape, but the input was not accepted.

\(b)\)The first \(1\) (if any) is changed to a \(0\) and the others are left alone.

The input is not accepted.

Step-by-step solution

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

Verifying the given input

(a)

The machine starts in state \({s_0}\) and sees the first \(1\). Therefore, using the first five-tuple, it replaces the \(1\) by a \(0\), moves to the right, and enters state \({s_1}\). Now it sees the second \(1\), so, using the second five-tuple, it replaces the \(1\) by a \(1\) (i.e., leaves it unchanged), moves to the right, and stays in state \({s_1}\). Since there are no five-tuples telling the machine what to do in state \({s_1}\) when reading a blank, it halts.

Therefore, since \({\bf{01}}\) is on the tape, and the input was not accepted, because \({s_1}\) is not a final state; in fact, there are no final states (states that begin no \(5 - \)tuples).

Verifying the given input

(b)

This is same as part \((a)\). The first \(1\) (if any) is changed to a \(0\) and the others are left alone.

Hence, the input is not accepted.