The Logical Route to the Turing Machine
Abstract:
Alan Turing's 1936 paper in the Proceedings of the London Mathematical Society presented his classic model of a universal computing machine, thus bringing into being the discipline of theoretical Computer Science - to which his work remains central. But what problem was he attempting to solve when he came up with what we now call a "Turing machine"? This talk aims to answer that question.
The 1936 paper starts from the concept of a computable number, and the Turing machine is widely assumed to be intended as an abstract model of the processes that a human "computer" might employ for calculating a number. The paper ends with "an application to the Entscheidungs problem", David Hilbert's decision problem, and Turing has generally been understood as setting out to give a negative answer to this famous - and then very topical - problem.
However, a neglected reference within Turing's paper points in a different direction, suggesting that his primary inspiration came neither from human computation nor from Hilbert's problem, but instead, from a 1905 paradox about definable numbers which also inspired Gödel and Church. Turing's novel idea was to follow through how the paradoxical logic would work if definability were interpreted as mechanical computability, which then required him to devise a model of a computing machine.
Unlike its rivals, this account makes excellent sense of the sequence and structure of Turing's mathematical argument, explaining how it leads directly to what we now call the halting problem. Turing then recognised that this invited a fairly obvious (albeit tricky) "application" to Hilbert's decision problem, which in turn required addressing the issues of universality and of human computation. But these issues came last in Turing's thinking rather than first, as indeed the ordering of the paper suggests.
Turing later became further intrigued by the comparison between human and machine thinking, presenting the "Turing Test" as the focus of his equally famous (but far less substantial) 1950 paper in Mind. If the interpretation given here is correct, however, the 1936 paper is squarely based on a mathematical and logical problem, rather than on the project of modelling human computation.
Biodata:
Peter Millican is Gilbert Ryle Fellow and Professor of Philosophy at Hertford College and the University of Oxford, where he is also a member of the Faculty of Computer Science, and Head of Education and Outreach at the Institute for Ethics in Artificial Intelligence. Before moving to Oxford in 2005, he lectured in Computing and Philosophy at the University of Leeds for 20 years, teaching Computing courses in mathematics, logic, AI, programming (Pascal, Prolog, Java etc.) and software engineering.
Most of Millican's published research - in books and over 50 papers - has been on the interpretation, analysis, and assessment of classic arguments, deriving especially from the work of David Hume, Alan Turing, and Anselm. He has also published numerous papers on philosophy of language, epistemology, philosophy of science, ethics, and philosophy of religion (www.millican.org/research.htm).
The most distinctive aspect of his career has been on the interface between Computing and Philosophy (see www.philocomp.net), ranging from logical and theoretical issues (as in this talk), to finding insights linking human and machine intelligence, computer models of human behaviour, AI Ethics, and digital humanities (which connects with his philosophical scholarship, e.g. www.davidhume.org). He has been especially active pedagogically, creating joint courses at Leeds and Oxford (notably Computer Science & Philosophy, running at Oxford since 2012). He has also programmed software systems to support outreach in Computing, including the Elizabeth chatbot and the Turtle System at www.turtle.ox.ac.uk.