# 6.3.1 Turing machines

This abstract model of a computer was invented by Alan Turing in the
1930s and is known as a *Turing Machine*. Turing’s model is depicted in Figure 6.4. An infinite tape divided into squares
is used as the input, working storage, and output. The tape head can
read the current square on the tape, write a symbol into the current
tape square, and move left or right one position. The tape head keeps
track of its internal state, and follows rules matching the current
state and current tape square to determine what to do next.

Turing’s model is by far the most widely used model for computers today. Turing developed this model in 1936, before anything resembling a modern computer existed. Turing did not develop his model as a model of an automatic computer, but instead as a model for what could be done by a human following mechanical rules. He devised the infinite tape to model the two-dimensional graph paper students use to perform arithmetic. He argued that the number of machine states must be limited by arguing that a human could only keep a limited amount of information in mind at one time.

Turing’s model is equivalent to the model we described earlier, but
instead of using only bits as the symbols on the tape, Turing’s model
uses members of any finite set of symbols, known as the *alphabet* of
the tape. Allowing the tape alphabet to contain any set of symbols
instead of just the two binary digits makes it easier to describe a
Turing Machine that computes a particular function, but does not change
the power of the model. That means, every computation that could be done
with a Turing Machine using any alphabet set, could also be done by some
Turing Machine using only the binary digits.

We could show this by describing an algorithm that takes in a description of a Turing Machine using an arbitrarily large alphabet, and produces a Turing Machine that uses only two symbols to simulate the input Turing Machine. As we saw in Chapter 1, we can map each of the alphabet symbols to a finite sequence of binary digits.

Mapping the rules is more complex: since each original input symbol is
now spread over several squares, we need extra states and rules to read
the equivalent of one original input. For example, suppose our original
machine uses 16 alphabet symbols, and we map each symbol to a 4-bit
sequence. If the original machine used a symbol `X`

, which we map to the
sequence of bits `1011`

, we would need four states for every state in
the original machine that has a rule using `X`

as input. These four
states would read the `1`

, `0`

, `1`

, `1`

from the tape. The last state
now corresponds to the state in the original machine when an `X`

is read
from the tape. To follow the rule, we also need to use four states to
write the bit sequence corresponding to the original write symbol on the
tape. Then, simulating moving one square left or right on the original
Turing Machine, now requires moving four squares, so requires four more
states. Hence, we may need 12 states for each transition rule of the
original machine, but can simulate everything it does using only two
symbols.

The Turing Machine model is a *universal computing machine*. This means
every algorithm can be implemented by some Turing Machine.
Chapter 12 explores more deeply what it means to simulate every
possible Turing Machine and explores the set of problems that can be
solved by a Turing Machine.

Any physical machine has a limited amount of memory. If the machine does not have enough space to store a trillion bits, there is no way it can do a computation whose output would exceed a trillion bits. Nevertheless, the simplicity and robustness of the Turing Machine model make it a useful way to think about computing even if we cannot build a truly universal computing machine.

Turing’s model has proven to be remarkably robust. Despite being
invented before anything resembling a modern computer existed, nearly
every computing machine ever imagined or built can be modeled well using
Turing’s simple model. The important thing about the model is that we
can simulate any computer using a Turing Machine. Any step on any
computer that operates using standard physics and be simulated with a
finite number of steps on a Turing Machine. This means if we know how
many steps it takes to solve some problem on a Turing Machine, the
number of steps it takes on any other machine is at most some multiple
of that number. Hence, if we can reason about the number of steps
required for a Turing Machine to solve a given problem, then we can make
strong and general claims about the number of steps it would take *any*
standard computer to solve the problem. We will show this more
convincingly in Chapter 12, but for now we assert it, and use
it to reason about the cost of executing various procedures in the
following chapter.

We define a Turing Machine that solves the problem of checking
parentheses are well-balanced. For example, in a Scheme expression,
every opening left parenthesis must have a corresponding closing right
parenthesis. For example, `(()(()))()`

is well-balanced, but `(()))(()`

is not. Our goal is to design a Turing Machine that takes as input a
string of parentheses (with a `#`

at the beginning and end to mark the
endpoints) and produces as output a `1`

on the tape if the input string
is well-balanced, and a `0`

otherwise. For this problem, the output is
what is written in the square under the tape head; it doesn’t matter
what is left on the rest of the tape.

Our strategy is to find matching pairs of parentheses and cross them out
by writing an `X`

on the tape in place of the parenthesis. If all the
parentheses are crossed out at the end, the input was well-balanced, so
the machine writes a `1`

as its output and halts. If not, the input was
not well-balanced, and the machine writes a 0 as its output and halts.
The trick to the matching is that a closing parenthesis always matches
the first open parenthesis found moving to the left from the closing
parenthesis. The plan for the machine is to move the tape head to the
right (without changing the input) until a closing parenthesis is found.
Cross out that closing parenthesis by replacing it with an `X`

, and move
to the left until an open parenthesis is found. This matches the closing
parenthesis, so it is replaced with an `X`

. Then, continue to the right
searching for the next closing parenthesis. If the end of the tape
(marked with a `#`

) is found, check the tape has no remaining open
parenthesis.

We need three internal states: *LookForClosing*, in which the machine
continues to the right until it finds a closing parenthesis (this is the
start state); *LookForOpen*, in which the machine continues to the left
until it finds the balancing open parenthesis; and *CheckTape*, in which
the machine checks there are no unbalanced open parentheses on the tape
starting from the right end of the tape and moving towards the left end.
The full rules are shown in Figure 6.5.

State | Read | Next State | Write | Move | |

LookForClosing | ) | LookForOpen | X | $\leftarrow $ | Found closing. |

LookForClosing | ( | LookForClosing | ( | $\rightarrow $ | Keep looking. |

LookForClosing | X | LookForClosing | X | $\rightarrow $ | Keep looking. |

LookForClosing | # | CheckTape | # | $\leftarrow $ | End of tape. |

LookForOpen | ) | - | X | Error | Shouldn’t happen. |

LookForOpen | ( | LookForClosing | X | $\rightarrow $ | Found open. |

LookForOpen | X | LookForOpen | X | $\leftarrow $ | Keep looking. |

LookForOpen | # | - | 0 | Halt | Reached beginning. |

CheckTape | ) | - | 0 | Error | Shouldn’t happen. |

CheckTape | ( | - | 0 | Halt | Unbalanced open. |

CheckTape | X | CheckTape | X | $\leftarrow $ | Keep checking. |

CheckTape | # | - | 1 | Halt | Finished checking. |

**Figure 6.5**: Rules for checking balanced parentheses Turing Machine.

Another way to depict a Turing Machine is to show the states and rules
graphically. Each state is a node in the graph. For each rule, we draw
an edge on the graph between the starting state and the next state, and
label the edge with the read and write tape symbols (separated by a
`/`

), and move direction.

Figure 6.6 shows the same Turing Machine
as a state graph. When reading a symbol in a given state produces an
error (such as when a `)`

is encountered in the *LookForOpen* state), it
is not necessary to draw an edge on the graph. If there is no outgoing
edge for the current read symbol for the current state in the state
graph, execution terminates with an error.

**Exercise 6.10. ** Follow the rules to simulate the checking
parentheses Turing Machine on each input (assume the beginning and end
of the input are marked with a `#`

):

`)`

`()`

*empty input*`(()(()))()`

`(()))(()`

**Exercise 6.11. ** $\left[\star \right]$Design a Turing Machine
for adding two arbitrary-length binary numbers. The input is of the form
$a_{n-1} \ldots a_1 a_0$ `+`

$b_{m-1} \ldots b_1 b_0$ (with
`#`

markers at both ends) where each $a_ k$ and $b_ k$ is either
`0`

or `1`

. The output tape should contain bits that represent the sum
of the two inputs.

David Alan Turing was born in London in 1912, and developed his computing model while at Cambridge in
the 1930s. He developed the model to solve a famous problem posed by
David Hilbert in 1928. The problem, known as the *Entscheidungsproblem*
(German for “decision problem”) asked for an algorithm that could
determine the truth or falsehood of a mathematical statement. To solve
the problem, Turing first needed a formal model of an algorithm. For
this, he invented the Turing Machine model described above, and defined
an algorithm as any Turing Machine that is guaranteed to eventually halt
on any input.

With the model, Turing was able to show that there are some problems
that cannot be solved by *any* algorithm. We return to this in
Chapter 12 and explain Turing’s proof and examples of problems
that cannot be solved.

After publishing his solution to the *Entscheidungsproblem* in 1936, Turing went to Princeton
and studied with Alonzo Church (inventor of the Lambda calculus, on
which Scheme is based). With the start of World War II, Turing joined
the highly secret British effort to break Nazi codes at Bletchley Park.
Turing was instrumental in breaking the Enigma code which was used by
the Nazis to communicate with field units and submarines. Turing
designed an electro-mechanical machine known as a *bombe* for searching
possible keys to decrypt Enigma-encrypted messages.

The machines used logical operations to search the possible rotor settings on the Enigma to find the settings that were most likely to have generated an intercepted encrypted message. Bletchley Park was able to break thousands of Enigma messages during the war. The Allies used the knowledge gained from them to avoid Nazi submarines and gain a tremendous tactical advantage.

After the war, Turing continued to make both practical and theoretical
contributions to computer science. Among other things, he worked on
designing general-purpose computing machines and published a paper
(*Intelligent Machinery*) speculating on the ability of computers to
exhibit intelligence. Turing introduced a test for machine intelligence
(now known as the Turing Test) based on a machines ability to
impersonate a human and speculated that machines would be able to pass
the test within 50 years (that is, by the year 2000). Turing also
studied morphogenesis (how biological systems grow) including why
Fibonacci numbers appear so often in plants.

In 1952, Turing’s house was broken into, and Turing reported the crime to the police. The investigation revealed that Turing was a homosexual, which at the time was considered a crime in Britain. Turing did not attempt to hide his homosexuality, and was convicted and given a choice between serving time in prison and taking hormone treatments. He accepted the treatments, and has his security clearance revoked. In 1954, at the age of 41, Turing was found dead in an apparent suicide, with a cyanide-laced partially-eaten apple next to him. The codebreaking effort at Bletchley Park was kept secret for many years after the war (Turing’s report on Enigma was not declassified until 1996), so Turing never received public recognition for his contributions to the war effort. In September 2009, instigated by an on-line petition, British Prime Minister Gordon Brown issued an apology for how the British government treated Alan Turing.Brown, Gordon