Here is an essay I wrote on the Turing Machine. I had a lot of fun doing research for this paper and I ended up reading books in many different areas in Computers and Mathematics. I also felt that the first and final paragraph tie together in a very eloquent manner.
In his play
Hamlet, Shakespeare provides an interesting description of humanity:
"What a piece of work is man! How noble in reason, how infinite
in faculties, in form and moving how express and admirable, in action
how like an angel, in apprehension how like a god!”1
An intriguing question that one may ask is where does this leave the
machines we create? Perhaps at the beginning of this century, one would
be able to obtain an almost unanimous affirmation of the superiority
of the human brain over the machine. The very question was ridiculous.
In 1937, a British mathematician named Alan Matison Turing dreamed up
a very simple machine that he contended was in some ways our equal.
This device came to be known as the Turing Machine.
At the 1928 International Congress,
the great mathematician David Hilbert posed three questions. Was mathematics
consistent, complete and decidable? At the time, Hilbert believed that
the answer to all three questions was in the affirmative. Kurt Gödel,
a Czech mathematician, soon stunned the mathematical community by showing
that the answer to Hilbert’s first two questions was in the negative.
In 1935, Turing attended a lecture course given by the distinguished
Cambridge topologist M. H. A. Newman that ended with a treatment of
Gödel’s proof that no system of axioms for arithmetic could be both
consistent and complete. Turing learned that the third question posed
by Hilbert was still unresolved. This was the question of the
Entscheidungsproblem, which is German for “the Decision Problem”. 2
The question concerned the existence, at least in principle, of a definite
method or process by which all mathematical questions could be decided.
In the early summer of 1935,
Turing found a way to answer Hilbert’s third question. He was to say
later that it came to him while lying in a meadow in Grantchester. In
April 1936, Turing wrote up a paper and showed it to an astonished Newman.
Turing’s paper, which was entitled “On computable numbers, with an application
to the Entscheidungsproblem”3, was submitted on 28’th April 1936
and published in 1937 in the Proceedings of the London Mathemtical
Society.4 Thus it was in the context of the
Entscheidungsproblem did Turing introduce the Turing Machine.
Since then, this simple theoretical computation has played a central
role in the theories of computation and computability. The Turing Machine
concept has had major impacts on many fields including Mathematics,
Computer Science, Philosophy and Artificial Intelligence.
At about the same time as Turing,
the American mathematician Alonzo Church answered the
Entscheidungsproblem in a completely different way. This diminished
some of the glory of Turing’s discovery. In the final draft of the paper,
Turing noted Church’s work and provided an appendix that showed that
his notion of “computability” was equivalent to Church’s notion of “effective
calculability”.5 The date noted in the appendix is
August 28, 1936. The relatively short time it took Turing to absorb
Church’s work and come up with the equivalence proof serves as a testament
to his mathematical abilities.
It is interesting to briefly
note the origins of the term “Turing Machine”. In his 1937 paper, Turing
called his conceptual device the "computing machine". In the
same paper, he refers to the more advanced “Universal Turing Machine”
as the "universal computing machine". The words “Turing Machine”
were first put into print in 1937 by Church’s review of Turing’s paper
in the Journal of Symbolic Logic.6
Another interesting detail one can observe from Turing’s paper is that
he defined two non-universal machines. He called the first one an “automatic
machine” or “a-machine”. This is a machine whose actions are completely
defined by its “configuration” or state. He called the second type of
machine a “choice machine” or “c-machine”. The actions of this machine
are only partially determined by its configurations. It thus has some
ambiguous states from which it cannot depart until an “external operator”
makes some arbitrary choice. Turing mentioned that his current paper
was only concerned with the “a-machine”.
The Turing Machine concept
was first introduced in Turing’s 1937 paper as a rigorous means of defining
the concept of a 'definite method' or algorithm. The first and last
sentences of the first paragraph of his paper illustrates his idea:
“The computable numbers may be described briefly as the real numbers
whose statements as a decimal are calculable by finite means. … According
to my definition, a number is computable if its decimal can be written
down by a machine.” Essentially, Turing required a way to capture the
notion of computation by a human. At various points in his paper, he
argued that his notion of computability, as embodied in the Turing Machine,
is equivalent to what is computable by humans. It must be noted that
this idea is not a precise theorem. Rather, it is an assertion. This
assertion is often called the “Church-Turing Thesis”. An alternative
statement of the Church-Turing Thesis is that a function is effectively
computable if and only if it can be computed by a Turing Machine.
The Turing Machine is a simple
theoretical model of a computer. However, it is important to note that
Turing never intended to build an actual Turing Machine. This is because
even though the Turing Machine provides an effective model of computation
it is certainly not an efficient one. In fact, there is no uniform bound
on either the time or space used by a Turing Machine.7
These two critical commodities are allowed to be consumed indefinitely.
Turing’s main intention was to have an extremely simple model of computation
that encompassed the idea of following a definite method. To this end,
he ruthlessly sacrificed notions of speed, efficiency and resource requirements.
For example, the device requires an endless tape. This requirement of
the specification is of course impossible to satisfy in any physical
However, Turing’s hypothetical
machine foreshadowed certain characteristics of the computers that would
follow. These ideas eventually became part of John Von Neumann’s architecture.8
For example, the device incorporates the idea of inputs and outputs.
In many ways, the tape corresponds to random access memory (RAM) in
that the machine can read from, write to and clear it. The control unit
and the tape together perform function similar to the modern day central
processing unit (CPU). The Universal Turing Machine could take “programs”
of other Turing Machines as input and store them onto tape. This was
somewhat similar to the “stored program concept” (generally credited
to Von Neumann) since the program is being treated like data. Thus,
Alan Turing is sometimes credited as being the inventor of the computer.
This is because he had worked out his computational model about a decade
before the first hardware computers made their debut. In fact, some
of these first computers were directly based on his work.
The basic Turing Machine consists
of a tape, a read-write head and a control unit. The tape, which is
assumed to be of infinite length, is divided into squares. Every Turing
Machine has a finite alphabet of symbols. The alphabet must contain
a “blank” symbol and at least one other symbol. The head can read or
write these symbols onto the tape. At any point in time, a Turing Machine
is in exactly one state from among a finite set of states. The control
unit can be thought of as a mathematical function. This function takes
as input the current state of the Turing Machine and symbol on the square
where the head is currently positioned. The output of the function is
the new state of the Turing Machine, the symbol that will be written
to the square where the head is currently located and the new position
of the head. The head can move one square to the right or one square
to the left relative to its current location. An alternative characterization
for the control unit is as an “action table” that stipulates what the
machine will do for each possible combination of symbol and state. Thus
there is an instruction for each possible combination of symbol and
state. This instruction has three parts. The first part specifies what
the machine should write onto the current square. The second part of
the instruction specifies whether the machine stays in the same state
or shifts to another state, which usually has a different set of instructions.
The third part specifies whether the machine should halt or move its
read-write head one position to the right or left.9
At the start of computation,
the tape can have a finite number of squares with nonblank symbols.
The rest of the tape is assumed to be blank. The machine scans the tape,
one square at a time. The scanning usually commences at the leftmost
nonblank square. After it performs its assigned task on a given square,
the machine stops or else moves one cell to the left or right. What
the machine does to a square and which way it moves afterwards depends
on the state of the machine at that instant.
It is interesting to note that
many different descriptions can be provided for what is essentially
the same device. This variety can be observed profusely in the literature
relating to Turing Machines. For example, many descriptions of Turing
Machines include an “erase” operation that enables a square to be made
blank. This operation corresponds to writing the blank symbol onto a
square in the Turing Machine described previously. Another modification,
proposed by Turing himself in the original paper, allows the device
to traverse more than one square at a time. Turing mentions: “If … we
allow the letters L, R (which correspond to moving left or right) to
appear more than once in the operations column we can simplify the table
considerably”10. Thus, differences in the description
of the Turing Machine have existed since its very conception. The main
reason behind these alternatives is that they may be easier to program,
In his 1937 paper, Turing described
his discovery of the concept of unsolvable problems. These are problems
that are well defined with unique answers that can be shown to exist
but it can also be showed that these problems can never be computed
by a Turing Machine. The example that Turing presented was that of the
“Halting Problem”11. This problem asks whether a Turing
Machine exists such that given any arbitrary Turing Machine as input,
we can determine whether the input Turing Machine halts on its own index
(i.e. when it is given itself as input). Clearly, a given Turing machine
either halts or doesn’t halt for any given input. So, the halting problem
is well defined and has an answer. The crux of the idea is that we can
never construct a Turing Machine that can answer the halting problem.
Turing showed this by a “proof by contradiction”. Suppose that such
a Turing Machine exists. We call this machine DOES_HALT. Then there
must also exits a Turing Machine called CONFUSE that implements the
READ INPUT N
If DOES_HALT(N) = NO then
Given that an algorithm for
DOES_HALT exits, we have just given an algorithm for CONFUSE. Consider
the behavior of the CONFUSE algorithm when it is given itself as input.
CONFUSE halts if DOES_HALT(CONFUSE) is NO.
CONFUSE does not halt if DOES_HALT(CONFUSE)
In non-technical terms, this
says that the algorithm CONFUSE halts only if it does not halt and vice
versa. But this is a contradiction. Thus the algorithm CONFUSE cannot
exist. This can only be the case if the DOES_HALT algorithm does not
exist. The halting problem is just one example of an undecidable problem.
The proof method is often called a “diagonal argument”. This is because
the counterexample algorithm CONFUSE is constructed from the behavior
of the algorithm on itself. As a historical note, the German Mathematician
George Cantor (the inventor of set theory) used a similar argument to
show that there are more real numbers than there are natural numbers.
This argument is now sometimes called the “Cantor Diagonalization argument”.
Different authors have extended
Turing’s original model in a variety of ways.12
The variants that we will discuss were proven to be equivalent to the
basic Turing Machine in that they all can compute the same class of
functions. For an alternate model, such a proof can be accomplished
by showing how to simulate the basic Turing Machine on the alternate
model and how to simulate the alternate model on the basic Turing Machine.
The efficiency of the computation
on different variants may differ. There are examples for which the time
taken on the one tape Turing Machine must be the square of the time
taken on the multitape machine. Thus in some cases, the multitape machine
is more efficient than the basic Turing Machine. It turns out that any
variant of the Turing Machine with a bounded number of processors cannot
perform a computation faster than the square root of the time t that
the basic Turing Machine requires.
One of the most important extensions
of the basic Turing Machine idea is that of the Universal Turing Machine.
The Universal Turing Machine was also introduced in Turing’s seminal
1937 paper. The purpose of this device is to read in a description of
any Turing Machine X in a standard format and execute any task that
X was designed to undertake. Thus, the Universal Turing Machine can
simulate any Turing Machine. Since a Turing Machine embodies the notion
of effective computability, the Universal Turing Machine can therefore
carry out any systematic process that humans can devise.
The Turing Machine concept
along with the Church-Turing Thesis has had a major impact on the Philosophy
of Mind. Hilary Putnam proposed the idea of “Turing Machine Functionalism”13.
Turing himself argued that the computational ability of the Turing Machine
was equivalent to what could be achieved by the human brain. As such,
the Turing Machine may serve as a model of the human mind. Putnam has
thus argued that human beings are probabilistic automatons.
Turing’s work has also played
a major role in the theory of Artificial Intelligence (AI). This is
a natural converse to the ideas described above. Indeed, if a human
behaves like a machine then a machine should be able to emulate a human.
Turing himself wrote on this in a 1950 paper that is considered by many
to be the birth of the field of AI. This paper, entitled “Computing
Machinery and Intelligence”, was published in a journal of psychology
and philosophy called Mind. Turing begins his paper by asking,
“Can machines think?” He then proposes a test of intelligence called
“the imitation game”. This test has come to be known as the Turing Test
for intelligence. The basic idea behind the test is that if a machine
can trick a human judge into thinking that it was a human a significant
proportion of the time then the machine was intelligent. It should be
noted that everyone does not accept the validity of this test. An important
point about this paper is that Turing does not propose using one of
his theoretical computing machines in the test. The reason is that they
would be much too slow and programming them would be an extremely tedious
task. Instead, he proposes using a Digital Computer for the test.
Other models of theoretical
computing other than the Turing machine have been proposed. The most
noteworthy are the “Random Access Machine” and the “Iterative Array”.14
Perhaps the main reason why the Turing Machine still survives in the
modern theory of computability is no different from that which led Alan
Turing to formulate it in the first place. The appeal of the Turing
Machine lies it its combination of simplicity and power.
Does there exist an algorithm
for deciding whether or not a specific mathematical assertion does or
does not have a proof? This was Hilbet’s
Entscheidungsproblem. When this question was posed, the famous
mathematician Hardy remarked:
“There is of course no such
theorem, and this is very fortunate, since if there were we should have
a mechanical set of rules for the solution of all mathematical problems,
and our activities as mathematicians would come to an end”.15
On one level, Turing’s negative
answer to the Entscheidungsproblem would relieve Hardy. On the
other hand, the Church-Turing Thesis asserts that our own abilities
are no greater than the abilities of our creation. Then, should we not
say, "What a piece of work is the machine! How noble in reason,
how infinite in faculties, in form and moving how express and admirable,
in action how like an angel, in apprehension how like a man!"16
Anderson, Ross Alan, ed.
Minds and Machines. Englewood Cliffs, New Jersey: Prentice-Hall,
Davis, Martin, ed. The
Undecidable. Hewlett, New York: Raven Press Books, Ltd., 1965.
Dewdney, A.K.. The New
Turing Omnibus: 66 Excursions in Computer Science.
New York: W.H. Freeman and Company, 1993.
Dictionary of Scientific
Biography – various articles. New York: Charles Scribner Sons, 1976.
Edwards, Paul N. The
Closed World: Computers and the Politics of Discourse in Cold War America.
Cambridge, Massachusetts: The Massachusetts Institute of Technology
Encyclopedia of Computer
Science – various articles. New York: Van Nostrand Reinhold.
Herken, Rold, ed.
The Universal Turing Machine: A Half-Century Survey. New York:
Enumerability, Decidability, Computability. New York: Springer-Verlag,
Hodges, Andrew. Alan
Turing: The Enigma. New York: Simon and Schuster, 1983.
Ince, D.C., ed. Mechanical
Intelligence. New York: Elsevier Science Publishing Company Inc.,
Jones, Neil D.
Computability Theory: An Introduction. New York: Academic Press,
Katz, Victor J.
A history of mathematics – An introduction. Don Mills, Ontario:
The Industrialization of Intelligence: Mind and Machine in Modern
Age. London, Great Britain: Unwin Hyman Limited, 1989.
Programming approach to computability. New York: Springer-Verlag,
Luger, George F. and William
A. Stubblefield. Artificial Intelligence and the Design of Expert
System. Reading, Massachusetts: The Benjamin/Cummings Publishing
Company, Inc., 1989.
Millican, P.J.R., and A.
Clark, eds. Machines and Thought: The legacy of Alan Turing.
Oxford: Clarendon Press, 1996.
God and Golem, Inc. Cambridge, Massachusetts: The Massachusetts
Institute of Technology Press, 1964.
I Am A Mathematician: The Later Life of a Prodigy. Cambridge,
Massachusetts: The Massachusetts Institute of Technology Press, 1956.
Shakespeare, William, 1564-1616
. Hamlet, Prince of Denmark
Electronic Text Center, University of Virginia Library <http://etext.virginia.edu/shakespeare/works/>
1 Shakespeare. Hamlet, Prince of Denmark. II ii 304-308.
2 Hodges. Alan Turing: The Enigma. p91-93.
3 I found it very difficult to find an original prints of Turing’s papers. However, I did find reprints of his classic works. The paper “On Computable Numbers…”, the associated appendix and correction are reprinted in The Undecidable (p115). Other works have been reprinted in the book Mechanical Intelligence. This work includes his seminal paper “Computing Machinery and intelligence” (p133). Since I specify when I am presenting ideas from Turing’s original papers, I will use footnotes every time.
4 Herken (ed). The Universal Turing Machine: A Half-Century Survey. p5.
5 Davis (ed). The Undecidable.p149.
6 Herken (ed). The Universal Turing Machine: A Half-Century Survey. p5.
7 Encyclopedia of Computer Science. The article on the “Turing Machine”.
8 Katz. A history of mathematics – An introduction. p844.
9 These descriptions are based on my course work from CSC 364: Computability and Complexity. Some ideas from the book “Programming approach to computability” were used.
10 Davis (ed). The Undecidable.p118.
11 Instead of using the words “halt” and “does not halt” that are generally used today, Turing used the word “circular” and “circle free” in his 1937 paper.
12 Encyclopedia of Computer Science. The article on the “Turing Machine”.
13 Putnam describes this idea in the paper “Minds and Machines”. This was reprinted in the book Minds and Machines (p72).
14 Encyclopedia of Computer Science. The article on the “Turing Machine”.
15 Hodges. Alan Turing: The Enigma. p93.
16 I have taken the liberty to rephrase Hamlet (II ii 304-308). Shakespeare, of course, merits credit!