Question

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

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

\(b)\)an arbitrary bit string as input\(?\)

Short answer

\(a)\)Machine halts with\(01\) on the tape, and the input was accepted.

\(b)\) If the machine is given a bit string as input, it scans it from left to right, changing every other occurrence of a \(1\), if any, starting with the first, to a \(0\), and otherwise leaving the string unchanged; it halts (and accepts) when it comes to the end of the string.

Step-by-step solution

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

Five-tuples defined by

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

Describing by the five-tuples

(a)

Note that all motion is from left to right.

The machine starts in state \({s_0}\) and sees the first \(1\). Therefore, using the second 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 fifth five-tuple, it replaces the \(1\) by a \(1\) (i.e., leaves it unchanged), moves to the right, and enters state \({s_0}\). The third five-tuple now tells it to leave the blank it sees alone, move to the right, and enter state \({s_2}\), which is a final (accepting) state (because it is not the first state in any five-tuple). Since there are no five-tuples telling the machine what to do in state \({s_2}\), it halts.

Therefore, since\(01\) is on the tape, and the input was accepted.

Describing by the five-tuples

(b)

When in state \({s_0}\) the machine skips over \(0's\), ignoring them, until it comes to a \(1\). When (and if) this happens, the machine changes this \(1\) to a \(0\) and enters state \({s_1}\). Note also that if the machine hits a blank \((B)\) while in state \({s_0}\) or \({s_1}\), then it enters the final (accepting) state \({s_2}\). Next note that \({s_1}\) plays a role similar to that played by so, causing the machine to skip over \(0's\), but causing it to go back into state \({s_0}\) if and when it encounters a \(1\). In state \({s_1}\), however, the machine does not change the \(1\) it sees to a\({\bf{0}}\). Thus the machine will alternate between states \({s_0}\) and \({s_1}\) as it encounters \(1\)'s in the input string, changing half of these \(1's\)to \(0's\).

Therefore, to summarize, if the machine is given a bit string as input, it scans it from left to right, changing every other occurrence of a \(1\), if any, starting with the first, to a \(0\), and otherwise leaving the string unchanged; it halts (and accepts) when it comes to the end of the string.