9.1.1.1 Schematic Drawing of Turing Machine

Linz Figure 9.1 shows a schematic drawing of a standard Turing machine.

This deviates from the general scheme given in Chapter 1 in that the input file, internal storage, and output mechanism are all represented by a single mechanism, the tape. The input is on the tape at initiation and the output is on that tape at termination.

On each move, the tape’s read-write head reads a symbol from the current tape cell, writes a symbol back to that cell, and moves one cell to the left or right.

9.1.1.2 Definition of Turing Machine

Turing machines were first defined by British mathematician Alan Turing in 1937, while he was a graduate student at Cambridge University.

Linz Definition 9.1 (Turing Machine): A Turing machine $M$ is defined by

$M = (Q, \Sigma, \Gamma, \delta, q_{0}, \Box, F)$

where

1. $Q$ is the set of internal states
2. $\Sigma$ is the input alphabet
3. $\Gamma$ is a finite set of symbols called the tape alphabet
4. $\delta$ is the transition function
5. $\Box \in \Gamma$ is a special symbol called the blank
6. $q_{0} \in Q$ is the initial state
7. $F \subseteq Q$ is the set of final states

We also require

8. $\Sigma \subseteq \Gamma - \{\Box\}$
   

and define

9. $\delta : Q \times \Gamma \rightarrow Q \times \Gamma \times \{L, R\}$.

Requirement 8 means that the blank symbol $\Box$ cannot be either an input or an output of a Turing machine. It is the default content for any cell that has no meaningful content.

From requirement 9, we see that the arguments of the transition function $\delta$ are:

• the current state of the control unit
• the current tape symbol

The result of the transition function $\delta$ gives:

• the new state of the control unit
• the symbol that replaces the current symbol on the tape
• a move symbol $L$ or $R$, denoting a move of the read-write head to the left or the right on the tape

In general, $\delta$ is a partial function. That is, not all configurations have a next move defined.

9.1.1.3 Linz Example 9.1

Consider a Turing machine with a move defined as follows:

$\delta(q_{0}, a) = (q_{1}, d, R)$

Linz Figure 9.2 shows the situation (a) before the move and (b) after the move.

9.1.1.4 A Simple Computer

A Turing machine is a simple computer. It has

• a processing unit that has a finite memory
• a tape that provides unlimited secondary storage capacity
• a limited set of instructions

The Turing machine can

• sense the symbol under the tape’s read-write head
• use the result to decide what to do next
• write a symbol back to the tape
• change the state of the control
• move the read-write head one position to the left or right on the tape

The transition function $\delta$ determines the behavior of the machine, i.e., it is the machine’s program.

The Turing macine starts in initial state $q_{0}$ and then goes through a sequence of moves defined by $\delta$. A cell on the tape may be read and written many times.

Eventually the Turing machine may enter a configuration for which $\delta$ is undefined. When it enters such a state, the machine halts. Hence, this state is called a halt state.

Typically, no transitions are defined on any final state.

9.1.1.5 Linz Example 9.2

Consider the Turing machine defined by

$Q = \{ q_{0}, q_{1} \}$,
$\Sigma = \{ a, b\}$,
$\Gamma = \{a, b, \Box \}$,
$F = \{ q_{1} \}$

where $\delta$ is defined as follows:

1. $\delta(q_{0}, a) = (q_{0}, b, R)$,
   
2. $\delta(q_{0}, b) = (q_{0}, b, R)$,
   
3. $\delta(q_{0}, \Box) = (q_{1}, \Box, L)$.

Linz Figure 9 .3 shows a sequence of moves for this Turing machine:

• It begins in state $q_{0}$ with the input positioned over an $a$.
• When an $a$ is read, transition rule 1 fires, replaces $a$ by $b$ on the tape, moves right, and stays in state $q_{0}$.
• When a $b$ is read, transition rule 2 fires, leaves $b$ on the tape, moves right, and stays in state $q_{0}$.
• It continues moving right, replacing each $a$ by a $b$ and leaving each $b$ unchanged.
• When a blank ($\Box$) is read, transition rule 3 fires, leaves the blank on the tape, moves left, and enters final state $q_{1}$.

9.1.1.6 Transition Graph for Turing Machine

As with finite and pushdown automata, we can use transition graphs to represent Turing machines. We label the edges of the graph with a triple giving (1) the current tape symbol, (2) the symbol that replaces it, and (3) the direction in which the read-write head moves.

Linz Figure 9.4 shows a transition graph for the Turing machine given in Linz Example 9.2.

9.1.1.7 Linz Example 9.3 (Infinite Loop)

Consider the Turing machine defined in Linz Figure 9.5.

Suppose the tape initially contains $a b \ldots$ with the read-write head positioned over the $a$ and in state $q_{0}$. Then the Turing machine executes the following sequence of moves:

1. The machine reads symbol $a$, leaves it unchanged, moves right (now over symbol $b$), and enters state $q_{1}$.

2. The machine reads $b$, leaves it unchanged, moves back left (now over $a$ again), and enters state $q_{0}$ again.

3. The machine then repeats steps 1-3.

Clearly, regardless of the tape configuration, this machine does not halt. It goes into an infinite loop.

9.1.1.8 Standard Turing Machine

Because we can define a Turing machine in several different ways, it is useful to summarize the main features of our model.

A standard Turing machine:

1. has a tape that is unbounded in both directions, allowing any number of left and right moves

2. is deterministic in that $\delta$ defines at most one move for each configuration

3. has no special input or output files. At the initial time, the tape has some specified content, some of which is considered input. Whenever the machine halts, some or all of the contents of the tape is considered output.

These definitions are chosen for convenience in this chapter. Chapter 10 (which we do not cover in this course) examines alternative versions of the Turing machine concept.

9.1.1.9 Instantaneous Description of Turing Machine

As with pushdown automata, we use instantaneous descriptions to examine the configurations in a sequence of moves. The notation (using strings)

$x_{1} q x_{2}$

or (using individual symbols)

$a_{1} a_{2} \cdots a_{k-1} q a_{k} a_{k+1} \cdots a_{n}$

gives the instantaneous description of a Turing machine in state $q$ with the tape as shown in Linz Figure 9.5.

By convention, the read-write head is positioned over the symbol to the right of the state (i.e., $a_{k}$ above).

A tape cell contains $\Box$ if not otherwise defined to have a value.

Example: The diagrams in Linz Figure 9.3 (above) show the instantaneous descriptions $q_{0} a a$, $b q_{0} a$, $b b q_{0} \Box$, and $b q_{1} b$.

As with pushdown automata, we use $\vdash$ to denote a move.

Thus, for transition rule

$\delta(q_{1}, c) = (q_{2}, e, R)$

we can have the move

$a b q_{1} c d \vdash a b e q_{2} d$.

As usual we denote the transitive closure of move (i.e., arbitrary number of moves) using:

$\vdash^*$

We also use subscripts to distinguish among machines:

$\vdash_{M}$

9.1.1.10 Computation of Turing Machine

Now let’s summarize the above discussion with the following definitions.

Linz Definition 9.2 (Computation): Let $M = (Q, \Sigma, \Gamma, \delta, q_{0}, \Box, F)$ be a Turing machine. Then any string $a_{1} \cdots a_{k-1} q_{1} a_{k} a_{k+1} \cdots a_{n}$ with $a_{i} \in \Gamma$ and $q_{1} \in Q$, is an instantaneous description of $M$.

A move

$a_{1} \cdots a_{k-1} q_{1} a_{k} a_{k+1} \cdots a_{n}$ $\vdash$ $a_{1} \cdots a_{k-1} b q_{2} a_{k+1} \cdots a_{n}$

is possible if and only if

$\delta(q_{1}, a_{k}) = (q_{2}, b, R)$.

A move

$a_{1} \cdots a_{k-1} q_{1} a_{k} a_{k+1} \cdots a_{n}$ $\vdash$ $a_{1} \cdots q_{2} a_{k-1} b a_{k+1} \cdots a_{n}$

is possible if and only if

$\delta(q_{1}, a_{k}) = (q_{2}, b, L)$.

$M$ halts starting from some initial configuration $x_{1} q_{i} x_{2}$ if

$x_{1} q_{i} x_{2} \ \vdash^*\ y_{1} q_{j} a y_{2}$

for any $q_{j}$ and $a$, for which $\delta(q_{j}, a)$ is undefined.

The sequence of configurations leading to a halt state is a computation.

If a Turing machine does not halt, we use the following special notation to describe its computation:

$x_{1} q x_{2} \vdash^* \infty$

9.1.2.1 Linz Example 9.6

For $\Sigma = \{ 0, 1 \}$, design a Turing machine that accepts the language denoted by the regular expression $00^{*}$.

We use two internal states $Q = \{ q_{0}, q_{1} \}$, one final state $F = \{ q_{1} \}$, and transition function:

$\delta(q_{0}, 0) = (q_{0}, 0, R)$,
$\delta(q_{0}, \Box) = (q_{1}, \Box, R)$

The transition graph shown below implements this machine.

• While a $0$ appears under the read-write head, the head moves to the right.
• If a blank is read, the machine halts in final state $q_{1}$.
• If a $1$ is read, the machine halts in the nonfinal state $q_{0}$ because $\delta(q_{0}, 1)$ is undefined.

The Turing machine also halts in a final state if started in state $q_{0}$ on a blank. We could interpret this as acceptance of $\lambda$, but for technical reasons the empty string is not included in Linz Definition 9.3.

9.1.2.2 Linz Example 9.7

For $\Sigma = \{ a, b \}$, design a Turing machine that accepts

$L = \{a^{n} b^{n} : n \geq 1 \}$.

We can design a machine that incorporates the following algorithm:

Filling in the details, we get the following Turing machine for which:

$Q = \{ q_{0}, q_{1}, q_{2}, q_{3}, q_{4} \}$
$F = \{q_4\}$
$\Sigma = \{a, b\}$
$\Gamma = \{a, b, x, y, \Box\}$

The transitions can be broken into several sets.

The first set

1. $\delta(q_{0}, a) = (q_{1}, x, R)$
   
2. $\delta(q_{1}, a) = (q_{1}, a, R)$
   
3. $\delta(q_{1}, y) = (q_{1}, y, R)$
   
4. $\delta(q_{1}, b) = (q_{2}, y, L)$

replaces the leftmost $a$ with an $x$, then causes the read-write head to travel right to the first $b$, replacing it with a $y$. The machine then enters a state $q_{2}$, indicating that an $a$ has been successfully paired with a $b$.

The second set

5. $\delta(q_{2}, y) = (q_{2}, y, L)$
   
6. $\delta(q_{2}, a) = (q_{2}, a, L)$
   
7. $\delta(q_{2}, x) = (q_{0}, x, R)$

reverses the direction of movement until an $x$ is encountered, repositions the read-write head over the leftmost $a$, and returns control to the initial state.

The machine is now back in the initial state $q_{0}$, ready to process the next $a$-$b$ pair.

After one pass through this part of the computation, the machine has executed the partial computation:

$q_{0} a a \cdots a b b \cdots b$ $\vdash^{*}$ $x q_{0} a \cdots a y b \cdots b$

So, it has matched a single $a$ with a single $b$.

The machine continues this process until no $a$ is found on leftward movement.

If all $a$’s have been replaced, then state $q_{0}$ detects a $y$ instead of an $a$ and changes to state $q_{3}$. This state must verify that all $b$’s have been processed as well.

8. $\delta(q_{0}, y) = (q_{3}, y, R)$
   
9. $\delta(q_{3}, y) = (q_{3}, y, R)$
   
10. $\delta(q_{3}, \Box) = (q_{4}, \Box, R)$

The input $aabb$ makes the moves shown below. (The bold number in parenthesis gives the rule applied in that step.)

The Turing machine halts in final state $q_{4}$, thus accepting the string $aabb$.

If the input is not in the language, the Turing machine will halt in a nonfinal state.

For example, consider:

• $a^{n} b^{m}$ for $n > m$?
  • halts in nonfinal state $q_{1}$ when $\Box$ found
• $a^{n} b^{m}$ for $0 < n < m$?
  • halts in nonfinal state $q_{3}$ when $b$ found
• $aba$?
  • halts in nonfinal state $q_{3}$ when $a$ found
• $b$?
  • halts in nonfinal state $q_{0}$ when $b$ found

9.1.3.1 Linz Example 9.9

Compute $x + y$ for positive integers $x$ and $y$.

We use unary notation to represent the positive integers, i.e., a positive integer is represented by a sequence of 1’s whose length is equal to the value of the integer. For example:

$1111 \ =\ 4$

The computation is

$q_{0} w(x) 0 w(y)$ $\vdash^{*}$ $q_{f} w(x + y) 0$

where $0$ separates the two numbers at initiation and after the result at termination.

Key idea: Move the separating $0$ to the right end.

To achieve this, we construct $M = (Q, \Sigma, \Gamma, \delta, q_{0}, \Box, F)$ with

$Q = \{ q_{0}, q_{1}, q_{2}, q_{3}, q_{4} \}$
$F = \{ q_{4} \}$
$\delta(q_{0}, 1) = (q_{0}, 1, R)$
$\delta(q_{0}, 0) = (q_{1}, 1, R)$
$\delta(q_{1}, 1) = (q_{1}, 1, R)$
$\delta(q_{1}, \Box) = (q_{2}, \Box, L)$
$\delta(q_{2}, 1) = (q_{3}, 0, L)$
$\delta(q_{3}, 1) = (q_{3}, 1, L)$
$\delta(q_{3}, \Box) = (q_{4}, \Box, R)$

The sequence of instantaneous descriptions for adding 111 to 11 is shown below.

9.1.3.2 Linz Example 9.10

Construct a Turing machine that copies strings of $1$’s. More precisely, find a machine that performs the computation

$q_{0} w \vdash^{*} q_{f} ww$,

for any $w \in \{1\}^{+}$.

To solve the problem, we implement the following procedure:

1. Replace every $1$ by an $x$.
2. Find the rightmost $x$ and replace it with $1$.
3. Travel to the right end of the current nonblank region and create a $1$ there.
4. Repeat steps 2 and 3 until there are no more $x$’s.

A Turing machine transition function for this procedure is as follows:

$\delta(q_{0}, 1) = (q_{0}, x, R)$
$\delta(q_{0}, \Box) = (q_{1} \Box, L)$
$\delta(q_{1}, x) = (q_{2}, 1, R)$
$\delta(q_{2}, 1) = (q_{2}, 1, R$
$\delta(q_{2}, \Box) = (q_{1}, 1, L)$
$\delta(q_{1}, 1) = (q_{1}, 1, L)$
$\delta(q_{1}, \Box) = (q_{3}, \Box, R)$

where $q_{3}$ is the only final state.

Linz Figure 9.7 shows a transition graph for this Turing machine.

This is not easy to follow, so let us trace the program with the string 11. The computation performed is as shown below.

9.1.3.3 Linz Example 9.11

Suppose $x$ and $y$ are positive integers represented in unary notation.

Construct a Turing machine that halts in a final state $q_{y}$ if $x \geq y$ and in a nonfinal state $q_{n}$ if $x < y$.

That is, the machine must perform the computation:

$q_{0} w(x) 0 w(y)$ $\vdash^{*}$ $q_{y} w(x) 0 w(y)$, if $x \geq y$
$q_{0} w(x) 0 w(y)$ $\vdash^{*}$ $q_{n} w(x) 0 w(y)$, if $x < y$

We can adapt the approach from Linz Example 9.7. Instead of matching $a$’s and $b$’s, we match each 1 on the left of the dividing 0 with the 1 on the right. At the end of the matching, we will have on the tape either

$x x \cdots 110xx \cdots x \Box$

or

$x x \cdots xx0xx \cdots x11 \Box$,

depending on whether $x > y$ or $y > x$.

A transition graph for machine is shown below.

9.2.2.1 Linz Example 9.12

Design a Turing machine that computes the following function:

$f(x, y) = x + y$, if $x \geq y$,
$f(x, y) = 0$, if $x < y$.

For simplicity, we assume $x$ and $y$ are positive integers in unary representation and the value zero is represented by 0, with the rest of the tape blank.

Linz Figure 9.8 shows a high-level block diagram of this computation. This computation consists of a network of three simpler machines:

• a Comparer $C$ to determine whether or not $x \geq y$
• an Adder $A$ that computes $x + y$
• an Eraser $E$ that changes every $1$ to a blank

We use such high-level diagrams in subsequent discussions of large computations. How can we justify that practice?

We can implement:

• the Comparer program $C$ as suggested in Linz Example 9.11, using a Turing machine having states indexed with $C$

• the Adder program $A$ as suggested in Linz Example 9.9, with states indexed with $A$

• the Eraser program $E$ by constructing a Turing machine having states indexed with $E$

Comparer $C$ carries out the computations

$q_{C,0} w(x) 0 w(y) \vdash^{*} q_{A,0} w(x) 0 w(y)$, if $x \geq y$,

and

$q_{C,0} w(x) 0 w(y) \vdash^{*} q_{E,0} w(x) 0 w(y)$, if $x < y$.

If $q_{A,0}$ and $q_{E, 0}$ are the initial states of computations $A$ and $E$, respectively, then $C$ starts either $A$ or $E$.

Adder $A$ carries out the computation

$q_{A,0} w(x) 0 w(y) \vdash^{*} q_{A,f} w(x + y) 0$.

And, Eraser $E$ carries out the computation

$q_{E,0} w(x) 0 w(y) \vdash^{*} q_{E,f} 0$.

The outer diagram in Linz Figure 9.8 thus represents a single Turing machine that combines the actions of machines $C$, $A$, and $E$ as shown.

9.2.3.1 Macroinstructions

A simple kind of pseudocode is the macroinstruction. A macroinstruction is a single statement shorthand for a sequence of lower-level statements.

We first define the macroinstructions in terms of the lower-level language. Then we compose macroinstructions into a larger program, assuming the relevant substitutions will be done.

9.2.3.2 Linz Example 9.13

For this example, consider the macroinstruction

if $a$ then $q_{j}$ else $q_{k}$.

This means:

• If the Turing machine reads an $a$, then it, regardless of its current state, transitions into state $q_{j}$ without changing the tape content or moving the read-write head.

• If the symbol read is not an $a$, then it transitions into state $q_{k}$ without changing anything.

We can implement this macroinstruction with several steps of a Turing machine:

$\delta(q_{i}, a) = (q_{j0}, a, R)$ for all $q_{i} \in Q$
$\delta(q_{j0},c) = (q_{j}, c, L)$ for all $c \in \Gamma$

$\delta(q_{i}, b) = (q_{k0}, b, R)$ for all $q_{i} \in Q$ and all $b \in \Gamma - \{a\}$
$\delta(q_{k0},c) = (q_{k}, c, L)$ for all $c \in \Gamma$

States $q_{j0}$ and $q_{k0}$ just back up Turing machine tape position one place.

Macroinstructions are expanded at each occurrence.

9.2.3.3 Subprograms

While each occurrence of a macroinstruction is expanded into actual code, a subprogram is a single piece of code that is invoked repeatedly.

As in higher-level language programs, we must be able to call a subprogram and then, after execution, return to the calling point and resume execution without any unwanted effects.

How can we do this with Turing machines?

We must be able to:

• preserve information about the calling program’s configuration (state, read-write head position, tape contents), so that it can be restored on return from the subprogram

• pass information from the calling program to the called subprogram and vice versa

We can do this by partitioning the tape into several regions. Linz Figure 9.9 illustrates this technique for a program $A$ (a Turing machine) that calls a subprogram $B$ (another Turing machine).

1. $A$ executes in its own workspace.
2. Before transferring control to $B$, $A$ writes information about its configuration and inputs for $B$ into some separate region $T$.
3. After transfer, $B$ finds its input in $T$.
4. $B$ executes in its own separate workspace.
5. When $B$ completes, it writes relevant results into $T$.
6. $B$ transfers control back to $A$, which resumes and gets the needed results from $T$.

Note: This is similar to what happens in an actual computer for a subprogram (function, procedure) call. The region $T$ is normally a segment pushed onto the program’s runtime stack or dynamically allocated from the heap memory.

9.2.3.4 Linz Example 9.14

Design a Turing machine that multiplies $x$ and $y$, positive integers represented in unary notation.

Assume the initial and final tape configurations are as shown in Linz Figure 9.10.

We can multiply $x$ by $y$ by adding $y$ to itself $x$ times as described in the algorithm below.

Although the above description of the pseudocode approach is imprecise, the idea is sufficiently simple that it is clear we can implement it.

We have not proved that the block diagram, macroinstruction, or subprogram approaches will work in all cases. But the discussion in this section shows that it is plausible to use Turing machines to express complex computations.