3.1.2: Representing Turing Machines

\(\def\Assign#1#2{ { #1^{\Struct{#2}} } }\)
\(\def\Atom#1#2{ { \mathord{#1}(#2) } }\)
\(\def\Bin{ {\mathbb{B}} }\)
\(\def\cardeq#1#2{ { #1 \approx #2 } }\)
\(\def\cardle#1#2{ { #1 \preceq #2 } }\)
\(\def\cardless#1#2{ { #1 \prec #2 } }\)
\(\def\cardneq#1#2{ { #1 \not\approx #2 } }\)
\(\def\comp#1#2{ { #2 \circ #1 } }\)
\(\def\concat{ { \;\frown\; } }\)
\(\def\Cut{ { \text{Cut} } }\)
\(\def\Discharge#1#2{ { [#1]^#2 } }\)
\(\def\DischargeRule#1#2{ { \RightLabel{#1}\LeftLabel{\scriptsize{#2} } } }\)
\(\def\dom#1{ {\operatorname{dom}(#1)} }\)
\(\def\Domain#1{ {\left| \Struct{#1} \right|} }\)
\(\def\Elim#1{ { {#1}\mathrm{Elim} } }\)
\(\newcommand{\Entails}{\vDash}\)
\(\newcommand{\EntailsN}{\nvDash}\)
\(\def\eq[#1][#2]{ { #1 = #2 } }\)
\(\def\eqN[#1][#2]{ { #1 \neq #2 } }\)
\(\def\equivclass#1#2{ { #1/_{#2} } }\)
\(\def\equivrep#1#2{ { [#1]_{#2} } }\)
\(\def\Exchange{ { \text{X} } }\)
\(\def\False{ { \mathbb{F} } }\)
\(\def\FalseCl{ { \lfalse_C } }\)
\(\def\FalseInt{ { \lfalse_I } }\)
\(\def\fCenter{ { \,\Sequent\, } }\)
\(\def\fdefined{ { \;\downarrow } }\)
\(\def\fn#1{ { \operatorname{#1} } }\)
\(\def\Frm[#1]{ {\operatorname{Frm}(\Lang #1)} }\)
\(\def\fundefined{ { \;\uparrow } }\)
\(\def\funimage#1#2{ { #1[#2] } }\)
\(\def\funrestrictionto#1#2{ { #1 \restriction_{#2} } }\)
\(\newcommand{\ident}{\equiv}\)
\(\newcommand{\indcase}[2]{#1 \ident #2\text{:}}\)
\(\newcommand{\indcaseA}[2]{#1 \text{ is atomic:}}\)
\(\def\indfrm{ { A } }\)
\(\def\indfrmp{ { A } }\)
\(\def\joinrel{\mathrel{\mkern-3mu}}\)
\(\def\lambd[#1][#2]{\lambda #1 . #2}\)
\(\def\Lang#1{ { \mathcal{#1} } }\)
\(\def\LeftR#1{ { {#1}\mathrm{L} } }\)
\(\def\len#1{ {\operatorname{len}(#1)} }\)
\(\def\lexists#1#2{ { \exists #1\, #2 } }\)
\(\def\lfalse{ {\bot} }\)
\(\def\lforall#1#2{ { \forall#1\, #2 } }\)
\(\newcommand{\lif}{\rightarrow}\)
\(\newcommand{\liff}{\leftrightarrow}\)
\(\def\Log#1{ { \mathbf{#1} } }\)
\(\def\ltrue{ {\top} }\)
\(\def\Id#1{ {\operatorname{Id}_#1} }\)
\(\def\Int{ {\mathbb{Z}} }\)
\(\def\Intro#1{ { {#1}\mathrm{Intro} } }\)
\(\def\mModel#1{ { \mathfrak{#1} } }\)
\(\newcommand{\mSat}[3][{}]{\mModel{#2}{#1}\Vdash{#3}}\)
\(\newcommand{\mSatN}[3][{}]{\mModel{#2}{#1}\nVdash{#3}}\)
\(\def\Nat{ {\mathbb{N}} }\)
\(\def\nicefrac#1#2{ {{}^#1/_#2} }\)
\(\def\num#1{ { \overline{#1} } }\)

\(\def\ran#1{ {\operatorname{ran}(#1)} }\)
\(\newcommand{\Obj}[1]{\mathsf{#1}}\)
\(\def\Rat{ {\mathbb{Q}} }\)
\(\def\Real{ {\mathbb{R}} }\)
\(\def\RightR#1{ { {#1}\mathrm{R} } }\)
\(\def\Part#1#2{ { \Atom{\Obj P}{#1, #2} } }\)
\(\def\pto{ { \hspace{0.1 cm}\to\hspace{-0.44 cm}\vcenter{\tiny{\hbox{|}}}\hspace{0.35 cm} } }\)
\(\def\PosInt{ {\mathbb{Z}^+} }\)
\(\def\Pow#1{ {\wp(#1)} }\)
\(\newcommand{\Proves}{\vdash}\)
\(\newcommand{\ProvesN}{\nvdash}\)
\(\def\Relbar{\mathrel{=}}\)
\(\newcommand{\Sat}[3][{}]{\Struct{#2}{#1}\vDash{#3}}\)
\(\newcommand{\SatN}[3][{}]{\Struct{#2}{#1}\nvDash{#3}}\)
\(\newcommand{\Sequent}{\Rightarrow}\)
\(\def\Setabs#1#2{ { \{#1:#2\} } }\)
\(\newcommand{\sFmla}[2]{#1\,#2}\)
\(\def\Struct#1{ {#1} }\)
\(\def\subst#1#2{ { #1/#2 } }\)
\(\def\Subst#1#2#3{ { #1[\subst{#2}{#3}] } }\)
\(\def\TMblank{ { 0 } }\)
\(\newcommand{\TMendtape}{\triangleright}\)
\(\def\TMleft{ { L } }\)
\(\def\TMright{ { R } }\)
\(\def\TMstay{ { N } }\)
\(\def\TMstroke{ { 1 } }\)
\(\def\TMtrans#1#2#3{ { #1,#2,#3 } }\)
\(\def\Trm[#1]{ {\operatorname{Trm}(\Lang #1)} }\)
\(\def\True{ { \mathbb{T} } }\)
\(\newcommand{\TRule}[2]{#2#1}\)
\(\def\tuple#1{ {\langle #1 \rangle} }\)
\(\newcommand{\Value}[3][\,]{\mathrm{Val}_{#1}^{#3}(#2)}\)
\(\def\Var{ { \mathrm{Var} } }\)
\(\newcommand{\varAssign}[3]{#1 \sim_{#3} #2}\)
\(\def\Weakening{ { \text{W} } }\)

Turing machines can be represented visually by state diagrams. The diagrams are composed of state cells connected by arrows. Unsurprisingly, each state cell represents a state of the machine. Each arrow represents an instruction that can be carried out from that state, with the specifics of the instruction written above or below the appropriate arrow. Consider the following machine, which has only two internal states, \(q_0\) and \(q_1\), and one instruction:

Recall that the Turing machine has a read/write head and a tape with the input written on it. The instruction can be read as if reading a \(\TMblank\) in state \(q_0\), write a \(\TMstroke\), move right, and move to state \(q_1\). This is equivalent to the transition function mapping \(\tuple{q_0, \TMblank}\) to \(\tuple{q_1, \TMstroke, \TMright}\).

Example \(\PageIndex{1}\)

Even Machine: The following Turing machine halts if, and only if, there are an even number of \(\TMstroke\)’s on the tape (under the assumption that all \(\TMstroke\)’s come before the first \(\TMblank\) on the tape).

The state diagram corresponds to the following transition function:

\[\begin{aligned} \delta(q_0, \TMstroke) & = \tuple{q_1, \TMstroke, \TMright},\\ \delta(q_1, \TMstroke) & = \tuple{q_0, \TMstroke, \TMright},\\ \delta(q_1, \TMblank) & = \tuple{q_1, \TMblank, \TMright}\end{aligned}\]

The above machine halts only when the input is an even number of strokes. Otherwise, the machine (theoretically) continues to operate indefinitely. For any machine and input, it is possible to trace through the configurations of the machine in order to determine the output. We will give a formal definition of configurations later. For now, we can intuitively think of configurations as a series of diagrams showing the state of the machine at any point in time during operation. Configurations show the content of the tape, the state of the machine and the location of the read/write head.

Let us trace through the configurations of the even machine if it is started with an input of four \(\TMstroke\)’s. In this case, we expect that the machine will halt. We will then run the machine on an input of three \(\TMstroke\)’s, where the machine will run forever.

The machine starts in state \(q_0\), scanning the leftmost \(\TMstroke\). We can represent the initial state of the machine as follows: \[\TMendtape \TMstroke_0 \TMstroke \TMstroke \TMstroke \TMblank \ldots\nonumber\] The above configuration is straightforward. As can be seen, the machine starts in state one, scanning the leftmost \(\TMstroke\). This is represented by a subscript of the state name on the first \(\TMstroke\). The applicable instruction at this point is \(\delta(q_0, \TMstroke) = \tuple{q_1, \TMstroke, \TMright}\), and so the machine moves right on the tape and changes to state \(q_1\). \[\TMendtape \TMstroke \TMstroke_1 \TMstroke \TMstroke \TMblank \ldots\nonumber\] Since the machine is now in state \(q_1\) scanning a \(\TMstroke\), we have to “follow” the instruction \(\delta(q_1, \TMstroke) = \tuple{q_0, \TMstroke, \TMright}\). This results in the configuration \[\TMendtape \TMstroke \TMstroke \TMstroke_0 \TMstroke \TMblank \ldots\nonumber\] As the machine continues, the rules are applied again in the same order, resulting in the following two configurations: \[\TMendtape \TMstroke \TMstroke \TMstroke \TMstroke_1 \TMblank \ldots\nonumber\] \[\TMendtape \TMstroke \TMstroke \TMstroke \TMstroke \TMblank_0 \ldots\nonumber\] The machine is now in state \(q_0\) scanning a \(\TMblank\). Based on the transition diagram, we can easily see that there is no instruction to be carried out, and thus the machine has halted. This means that the input has been accepted.

Suppose next we start the machine with an input of three \(\TMstroke\)’s. The first few configurations are similar, as the same instructions are carried out, with only a small difference of the tape input: \[\TMendtape \TMstroke_0 \TMstroke \TMstroke \TMblank \ldots\nonumber\] \[\TMendtape \TMstroke \TMstroke_1 \TMstroke \TMblank \ldots\nonumber\] \[\TMendtape \TMstroke \TMstroke \TMstroke_0 \TMblank \ldots\nonumber\] \[\TMendtape \TMstroke \TMstroke \TMstroke \TMblank_1 \ldots\nonumber\] The machine has now traversed past all the \(\TMstroke\)’s, and is reading a \(\TMblank\) in state \(q_1\). As shown in the diagram, there is an instruction of the form \(\delta(q_1, \TMblank) =\tuple{q_1, \TMblank, \TMright}\). Since the tape is filled with \(\TMblank\) indefinitely to the right, the machine will continue to execute this instruction forever, staying in state \(q_1\) and moving ever further to the right. The machine will never halt, and does not accept the input.

It is important to note that not all machines will halt. If halting means that the machine runs out of instructions to execute, then we can create a machine that never halts simply by ensuring that there is an outgoing arrow for each symbol at each state. The even machine can be modified to run indefinitely by adding an instruction for scanning a \(\TMblank\) at \(q_0\).

Example \(\PageIndex{2}\)

Machine tables are another way of representing Turing machines. Machine tables have the tape alphabet displayed on the \(x\)-axis, and the set of machine states across the \(y\)-axis. Inside the table, at the intersection of each state and symbol, is written the rest of the instruction—the new state, new symbol, and direction of movement. Machine tables make it easy to determine in what state, and for what symbol, the machine halts. Whenever there is a gap in the table is a possible point for the machine to halt. Unlike state diagrams and instruction sets, where the points at which the machine halts are not always immediately obvious, any halting points are quickly identified by finding the gaps in the machine table.

Example \(\PageIndex{3}\)

The machine table for the even machine is:

\[\begin{array}{|c|c|c|c|}
\hline
&\TMblank &\TMstroke & \TMendtape \\ \hline
q_0 & & \TMtrans{\TMstroke}{q_1}{\TMright} &
\phantom{\TMtrans{\TMstroke}{q_1}{\TMright}} \\ \hline
q_1 & \TMtrans{\TMblank}{q_1}{\TMright}
& \TMtrans{\TMstroke}{q_0}{\TMright} &
\phantom{\TMtrans{\TMstroke}{q_1}{\TMright}} \\ \hline
\end{array}\nonumber\]

As we can see, the machine halts when scanning a blank in state \(q_0\).

So far we have only considered machines that read and accept input. However, Turing machines have the capacity to both read and write. An example of such a machine (although there are many, many examples) is a doubler. A doubler, when started with a block of \(n\) \(\TMstroke\)’s on the tape, outputs a block of \(2n\) \(\TMstroke\)’s.

Example \(\PageIndex{4}\)

Before building a doubler machine, it is important to come up with a strategy for solving the problem. Since the machine (as we have formulated it) cannot remember how many \(\TMstroke\)’s it has read, we need to come up with a way to keep track of all the \(\TMstroke\)’s on the tape. One such way is to separate the output from the input with a \(\TMblank\). The machine can then erase the first \(\TMstroke\) from the input, traverse over the rest of the input, leave a \(\TMblank\), and write two new \(\TMstroke\)’s. The machine will then go back and find the second \(\TMstroke\) in the input, and double that one as well. For each one \(\TMstroke\) of input, it will write two \(\TMstroke\)’s of output. By erasing the input as the machine goes, we can guarantee that no \(\TMstroke\) is missed or doubled twice. When the entire input is erased, there will be \(2n\) \(\TMstroke\)’s left on the tape. The state diagram of the resulting Turing machine is depicted in Figure \(\PageIndex{1}\).

Figure \(\PageIndex{1}\): A doubler machine

Problem \(\PageIndex{1}\)

Choose an arbitary input and trace through the configurations of the doubler machine in Example \(\PageIndex{4}\).

Problem \(\PageIndex{2}\)

The double machine in Example \(\PageIndex{4}\) writes its output to the right of the input. Come up with a new method for solving the doubler problem which generates its output immediately to the right of the end-of-tape marker. Build a machine that executes your method. Check that your machine works by tracing through the configurations.

Problem \(\PageIndex{3}\)

Design a Turing-machine with alphabet \(\{\TMendtape,\TMblank, A, B\}\) that accepts, i.e., halts on, any string of \(A\)’s and \(B\)’s where the number of \(A\)’s is the same as the number of \(B\)’s and all the \(A\)’s precede all the \(B\)’s, and rejects, i.e., does not halt on, any string where the number of \(A\)’s is not equal to the number of \(B\)’s or the \(A\)’s do not precede all the \(B\)’s. (E.g., the machine should accept \(AABB\), and \(AAABBB\), but reject both \(AAB\) and \(AABBAABB\).)

Problem \(\PageIndex{4}\)

Design a Turing-machine with alphabet \(\{\TMendtape,\TMblank, A, B\}\) that takes as input any string \(\alpha\) of \(A\)’s and \(B\)’s and duplicates them to produce an output of the form \(\alpha\alpha\). (E.g. input \(ABBA\) should result in output \(ABBAABBA\)).

Problem \(\PageIndex{5}\)

Alphabetical?: Design a Turing-machine with alphabet \(\{\TMendtape,\TMblank, A, B\}\) that when given as input a finite sequence of \(A\)’s and \(B\)’s checks to see if all the \(A\)’s appear to the left of all the \(B\)’s or not. The machine should leave the input string on the tape, and either halt if the string is “alphabetical”, or loop forever if the string is not.

Problem \(\PageIndex{6}\)

Alphabetizer: Design a Turing-machine with alphabet \(\{\TMendtape,\TMblank, A, B\}\) that takes as input a finite sequence of \(A\)’s and \(B\)’s rearranges them so that all the \(A\)’s are to the left of all the \(B\)’s. (e.g., the sequence \(BABAA\) should become the sequence \(AAABB\), and the sequence \(ABBABB\) should become the sequence \(AABBBB\)).