The Logical Route to the Turing Machine

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 Entscheidungsproblem”, 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.  

About the Speaker

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