The Alan Turing Internet Scrapbook


Computable Numbers
and the Turing Machine, 1936


Scrapbook Index
Alan Turing Home Page | Site Map | Scrapbook Index | Previous Scrapbook page | Next Scrapbook page
Run a Turing Machine



Boy to Man...

The years from 1932 to 1935 were the foundation of Alan Turing's serious scientific life. The atmosphere at King's College, Cambridge, was highly conducive to free-ranging thought. As an undergraduate there, Alan Turing developed the inspiration he had received from Christopher Morcom, and combined it with the newest ideas in mathematics.

On-line extract from my book on the moral and political ambience at King's College, and Alan Turing's life and thought in 1933.

...Man to Machine


Mathematical Logic

In 1935 a course by the Cambridge mathematician M. H. A. (Max) Newman introduced Alan Turing to the frontier of research in mathematical logic.

The twentieth century dawn

Already in 1933, Turing was familiar with the work of Bertrand Russell on the foundations of mathematics.

Mathematical Logic
History of Set Theory
Text of Russell's The Principles of Mathematics (1903)

What Gödel saw

Kurt Gödel's 1931 incompleteness theorem rewrote the agenda in the foundations of mathematics.

The Gödel home page is extended to an exhibition to mark Gödel's centenary year.

Two vivid lectures and an article by Greg Chaitin describe:

Gödel's 1931 work left open the question of the decidability of mathematical propositions, and this is what Turing set out to answer. The particular technique of Gödel numbering was also influential in Turing's 1936 work. Gödel had shown how to encode theorems about numbers, as numbers. Turing went on to show how to encode operations on numbers, by numbers.

Hilbert and decidability

The famous 1900 speech by the German mathematician David Hilbert did much to set the agenda for twentieth century mathematical research. More comment here.

Hilbert's 1900 Tenth Question about the solubility of Diophantine equations was a precursor to his later question about the 'decidability' of (apparently) more general mathematical assertions, the Entscheidungsproblem  (decision problem) which inspired Turing's work.

Martin Davis's 1958 text Computabilty and Unsolvability  did much to propagate Turing's work and later editions of his book added Davis's beautiful exposition of the resolution of Hilbert's Tenth Problem in 1970, in which his own work had been an important ingredient. Martin Davis's later book The Universal Computer, the road from Leibniz to Turing  gives a fascinating introduction to the development and significance of mathematical logic, culminating in a detailed account of Turing's work.


Normal Numbers and the typescript of On Computable Numbers

Another ingredient for Turing was his knowledge of the classical analysis of the real continuum. In 1933 his undergraduate friend David Champernowne had noticed and published a simple but new result about 'normal numbers'. These are infinite decimals in which the digits are uniformly distributed. Alan Turing took up this topic with some new results, and his manuscript notes were written on the back of the typescript of his 1936 paper On computable numbers... It seems very possible that Turing's interest in the constructive definition of real numbers was stimulated by Champernowne's work.

See six pages from the typescript of Turing's paper in the Turing Digital Archive. One of these is also reproduced in a note by me about this question in the Notices of the American Mathematical Society, November 2006.


Turing Machines and Computability

The question Hilbert raised was whether there could be a general method or process by which one could decide whether a mathematical proposition could be proved. But what exactly was meant by a 'method' or 'process'? People had already used the concept of a 'mechanical' process, and Turing had an idea which made this quite precise: computability.

Turing wrote in his first sentences:

The "computable" numbers may be described briefly as the real numbers whose expressions as a decimal are calculable by finite means... a number is computable if its decimal can be written down by a machine.

The Turing machine concept involves specifying a very restricted set of logical operations, but Turing showed how other more complex mathematical procedures could be built out of these atomic components.

Turing argued that his formalism was sufficiently general to encompass anything that a human being could do when carrying out a definite method.

Turing's famous 1936-7 paper On computable numbers, with an application to the Entscheidungsproblem,  which worked out the theory of Turing machines and the definition of computability, is available as a PDF file on-line

Go to another Scrapbook page for

Turing machines simulated in JavaScript.

There are three applications ready to run on-line.


The Universal Machine

Section 6 of Turing's paper began:
6. The universal computing machine

It is possible to invent a single machine which can be used to compute any computable sequence.

A Universal machine is a Turing machine with the property of being able to read the description of any other Turing machine, and to carry out what that other Turing machine would have done. It is not at all obvious that such a machine, a machine capable of performing any definite method, could exist. Intuitively one might think that more complex tasks would need more complex machines. They do not: it is sufficient to have a specific, limited, degree of complexity. More laborious tasks need only have more storage capacity. Turing gave an exact description of such a Universal machine in his paper (though with a few bugs).

Another one was given by Roger Penrose in his book The Emperor's New Mind,  and you can see this in an artistic form on Roman Verostko's page.

After 1945 Turing was able to embody the idea of the Universal machine in his plan for an electronic computer: this is described on another Scrapbook Page.



In this passage Alan Turing founded modern computer science.

But all this came from pure scientific thought, and not at all from an economic need for computing. Business and profit-making played no part in it.


Estimated price at Christies, 2005:
$15000-$20000.

Turing Machines Today

It is now almost impossible to read Turing's 1936 work without thinking of a Turing machine as a computer program, and the Universal Turing Machine as the computer on which different programs can be run. (If it seems puzzling that a Universal Turing Machine is itself only a particular kind of Turing machine, remember that a computer can be emulated as a program on another computer.)

We are now so familiar with the idea of the computer as a fixed piece of hardware, requiring only fresh software to make it do entirely different things, that it is hard to imagine the world without it.

But Turing imagined the Universal Turing Machine ten years before it could be implemented in electronics.

Now you can use your computer to simulate the working of a Turing machine, and so see on the screen what in 1936 was only possible in Turing's imagination. This is no accident! — the whole point is that the computer embodies the principle of a Universal Turing machine, which can simulate any Turing machine. It was also essential to Turing's 1936 work that a Turing machine could be thought of as data to be read and manipulated by another Turing machine — this is the principle of the modifiable stored program on which all computing now depends.


A new kind of science?

Stephen Wolfram, with homepage and his own Scrapbook, the creator of Mathematica and the MathsWorld resource, is the author of A New Kind of Science (2002).

This cites Alan Turing more than anyone else: see this index page.

In particular, he has conducted a new kind of investigation into the behaviour of Turing machines. This springs from a fundamental principle that algorithms give the right basis for understanding mathematics and physics. The fact that a very simple Turing machine can have very complex behaviour is seen as a crucial idea, key to 'a new kind of science'.

A particular success of this approach has come in finding the simplest possible design for a universal Turing machine, for which Stephen Wolfram made a conjecture and offered a Prize. This problem has been studied from the 1950s onwards, but seems to have reached a conclusion in 2007 with a solution by Alex Smith, who was awarded the prize. (There are, however, considerable subtleties in defining what is counted as an acceptable solution: see this discussion.) See Stephen Wolfram's comment on the 2007 solution. Alex Smith achieved this as a 20-year-old student, something that Alan Turing would have found particularly gratifying.


Turing's World

A full-scale Turing machine simulator, with a mass of documentation, is supplied by Stanford University's Turing's World software.

Java Computability Toolkit

A new Web resource was made available from SUNY Institute of Technology at Rome, NY in 1998. It is a freely downloadable Turing machine simulator in Java. The writers say: 'It is built with collaboration and user-friendliness in mind and will always be free!' Go to the JCT site.

There is an on-line thesis about the JCT and computability.

Other Turing Machine Descriptions and Simulations On-Line

Websites with information on other (downloadable) Turing machine simulators. are maintained by:

A special simulator: built physically, see it working on video.


Turing Machines in DNA?

Alan Turing's definition of a Turing machine was not intended as a blueprint for how one would actually build practical computing machinery. The very primitive actions of reading and writing and moving one step at a time are like atoms of computation, and the atomic level is too time-consuming for what is needed in practice. However it appears that there is one modern field in which this atomic level of simplicity may be just what is needed. This is explored by Ehud Shapiro in a June 1999 paper on using the Turing machine model for a DNA computer. See his page for further information, and a further article.

More recent article (2003).

Turing Machines in Real Life

Paul Rendell has a page on building Turing machines in Conway's Game of Life.

Computability, complexity...

Turing machines, in providing a sort of atomic structure for the concept of computation, have led to new mathematical investigations. One development of the last 30 years, which Turing did not himself foresee, is that of classifying different problems in terms of their complexity. Turing machines give a platform-independent way of measuring this complexity.

Dr A. N. Walker's course on computability and complexity draws attention to how the excellent 1972 textbook of Marvin Minsky, which did much to popularise the use of Turing machines in computer science, is now out of date because it did not treat complexity.

...and quantum computing

Turing machines also provided the model in the 1980s for the new theory of quantum computing.

The Uncomputable

Turing's definition of computability entailed the fact that uncomputable numbers and functions can be defined explicitly. The most famous uncomputable function, closely related to Turing's own 1936 proof, is one that distinguishes between halting and non-halting Turing machines. Turing used his definition of an uncomputable number to answer Hilbert's question in the negative: there can be no one definite method capable of deciding whether or not a given mathematical statement is provable.

A version of the halting problem is given on a page by Mike Yates, which explains Turing's development of Cantor's diagonal method, and gives a proof of the essential result.

Mike Yates has a special connection with this problem. He was the first research student of Robin Gandy, who was in turn Alan Turing's first. Mike Yates was also greatly stimulated by Max Newman's knowledge of mathematical logic, and found him a great encourager just as Alan Turing did. Robin Gandy and Mike Yates were editors of the Mathematical Logic volume of the Turing Collected Works.

Another uncomputable function arises from the Busy Beaver problem, which is fully described with many links to other work on computability on this page by Michael Somos. Further technical information here.


Computability and the Philosophy of Mind

Alan Turing described his concept of the Turing machine in terms of 'states of mind', and his work has important implications for the philosophy of Mind.

This Rutgers University course by Charles F. Schmidt has an extensive discussion of computability and artificial intelligence. It also has an excerpt from Turing's 1936 paper on this page.

There are many difficult and controversial issues involved in these questions. Some of these are addressed in the Philosophy Area on this site.

My text on Alan Turing as a philosopher includes a substantial amount of Turing's original writing, and in particular big chunks of On computable numbers. 

More details and complete on-line version of the text.


Church's Thesis and Turing's Thesis

In April 1936 Turing discovered that Alonzo Church, the American logician at Princeton, had already found the answer to Hilbert's question. To do this, however Church had assumed that the notion of being 'effectively calculable' was correctly captured by the lambda-calculus  of mathematical logic. This assumption became known as Church's Thesis. Turing's definition of effective calculability was much more compelling and it was generally agreed that his approach was both independent and more satisfactory. Turing showed in summer 1936 that this own definition coincided with Church's in its mathematical consequences. The statement that the 'effectively calculable' is equivalent to the scope of Turing machines is now generally known as the Church-Turing thesis. But by bringing a kind of physical action into the picture, the Turing thesis is subtly different from Church's.

There is a discussion of the Church-Turing thesis in my entry in the Stanford Encyclopedia of Philosophy.


Passport photograph from the
Turing Digital Archive

The shape of things to come...

There was much talk in the 1930s of it being an 'age of machines.' H. G. Wells's futuristic fantasy of 1933 became a film in 1936. Little did they know...

...was American.

Alan Turing sailed on the liner Berengaria to New York and arrived at Princeton in September 1936.

He went on to a prolific period of mathematical work, and in particular to investigate what lay beyond  the scope of Turing machines.

Continue to the next Scrapbook page.

but Germany still posed an Entscheidungsproblem...




CONTINUE: Next Page | Previous Page | Run a Turing Machine | Scrapbook Index

Quick Links: book Short Bio scrapbook publications sources
home
Andrew Hodges