 |
|
 |
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.
As an undergraduate, his main supervisor was the group theorist Philip Hall. His closest friends were fellow mathematics students David Champernowne and James Atkins — who became his first continuing boyfriend. He went rowing, running, joined the Anti-War movement in 1933, and made visits to Germany. He was elected a Fellow in 1935.
|
...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.
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 by Ivor Grattan-Guinness.
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 Computability 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
|
Computer prophet and profit
In this passage Alan Turing founded modern computer science.
Economic motivations played no part. |
Estimated price at Christies, 2005: $15000-$20000.
|
| Money could not buy it: Election to Fellowship of the Royal Society, fifteen years later. | Money could not buy it: creation of the A. M. Turing Award by the Association for Computing Machinery, thirty years later. |
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.
|
Visualising Turing Machines
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.
 |
Go to the Book Update area for
There are three applications ready to run on-line.
|
|
Turing Machines since 1936
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. When Turing came in 1945 to design a computer, he knew well that data storage and the logical control would have to be implemented in a completely different way.
Turing himself did remarkably little to promote his own formalism as a basis for the emergent theory of computer science, or even within the field of mathematical logic. Martin Davis's 1958 text Computability and Unsolvability brought Turing machines back into the mainstream of logic. Marvin Minsky's textbook Computation: Finite and Infinite Machines (1967) brought them into the mainstream of computer science, but probably the most important development was that of
complexity theory in the 1970s. Turing machines give a platform-independent way of measuring the complexity of a computational problem.
Turing machines also provided the model in the 1980s for the new theory of quantum computing.
|
The Uncomputable
Whilst Turing did not see all the possible applications of his theory of the computable, he did know from the start that his definition of computability entailed the fact that uncomputable numbers and functions can also be defined explicitly. Indeed, this was the principal mathematical result of his 1936 work.
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.
|
Computability and the Philosophy of Mind
By making this definition of computability, Turing went outside pure mathematics. To justify his claim that his definition would encompass anything that could reasonably be called computation, 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 is notable for substantial quotation from Turing's original 1936 paper on
this page.
|
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, 1936 |
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... |
|
|
|
