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.

The Turing Machine 

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!”¹ 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”. ² 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”³, was submitted on 28’th April 1936 and published in 1937 in the Proceedings of the London Mathemtical Society.⁴ 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”.⁵ 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.⁶ 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.⁷ 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 environment. 

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.⁸ 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.⁹  

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”¹⁰. 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, describe, etc. 

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”¹¹. 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 following algorithm: 

READ INPUT N

If DOES_HALT(N) = NO then

Halt

Else

Don’t halt

End if 

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) is YES. 

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.¹² 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.  

1. One Ended Tape: The tape can only be extended to the right.
2. Paper Tape: We can write a nonblank symbol onto a blank square. However, a nonblank symbol may not be erased or overwritten.
3. Two Symbol: The alphabet only consists of the blank symbol and 1.
4. Two State: Only two states are allowed. However, the alphabet may have a large number of symbols.
5. Multitape: More than one tape may be attached to the device. Each tape has its own read-write head. The tape movements are independent.

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”¹³. 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”.¹⁴ 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”.¹⁵ 

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!"¹⁶ 

Bibliography 

Altman, Ira. The Concept of Intelligence: A Philosophical Analysis. Cummor Hill, Oxford: University Press of America, 1997. 

Anderson, Ross Alan, ed. Minds and Machines. Englewood Cliffs, New Jersey: Prentice-Hall, INC., 1964. 

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 Press, 1996. 

Encyclopedia of Computer Science – various articles. New York: Van Nostrand Reinhold. 

Herken, Rold, ed. The Universal Turing Machine: A Half-Century Survey. New York: Springer-Verlag, 1995. 

Hermes, Hans. Enumerability, Decidability, Computability. New York: Springer-Verlag, 1965.  

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., 1992. 

Jones, Neil D. Computability Theory: An Introduction. New York: Academic Press, Inc., 1973. 

Katz, Victor J. A history of mathematics – An introduction. Don Mills, Ontario: Addison-Wesley, 1998. 

Kennedy, Noah. The Industrialization of Intelligence: Mind and Machine in Modern Age. London, Great Britain: Unwin Hyman Limited, 1989. 

Kfoury, A.J. Programming approach to computability. New York: Springer-Verlag, 1982. 

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. 

Wiener, Norbert. God and Golem, Inc. Cambridge, Massachusetts: The Massachusetts Institute of Technology Press, 1964. 

Wiener, Norbert. 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/>

¹ Shakespeare. Hamlet, Prince of Denmark. II ii 304-308.

² Hodges. Alan Turing: The Enigma. p91-93.

³ 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.

⁴ Herken (ed). The Universal Turing Machine: A Half-Century Survey. p5.

⁵ Davis (ed). The Undecidable.p149.

⁶ Herken (ed). The Universal Turing Machine: A Half-Century Survey. p5.

⁷ Encyclopedia of Computer Science. The article on the “Turing Machine”.

⁸ Katz. A history of mathematics – An introduction. p844.

⁹ 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.

¹⁰ Davis (ed). The Undecidable.p118.

¹¹ 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.

¹² Encyclopedia of Computer Science. The article on the “Turing Machine”.

¹³ Putnam describes this idea in the paper “Minds and Machines”. This was reprinted in the book Minds and Machines (p72).

¹⁴ Encyclopedia of Computer Science. The article on the “Turing Machine”.

¹⁵ Hodges. Alan Turing: The Enigma. p93.

¹⁶ I have taken the liberty to rephrase Hamlet (II ii 304-308). Shakespeare, of course, merits credit!