The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life: Plus The Secrets of Enigma B. Jack Copeland, Editor OXFORD UNIVERSITY PRESS The Essential Turing AlanM.Turing The Essential Turing Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life plus The Secrets of Enigma Edited by B. Jack Copeland CLARENDON PRESS OXFORD (cid:1) Great Clarendon Street,Oxford OX2 6DP Oxford University Press is a department ofthe University ofOxford. Itfurthers the University’s objective ofexcellence in research,scholarship, and education by publishing worldwide in Oxford New York Auckland Cape Town Dar es Salaam Hong Kong Karachi Kuala Lumpur Madrid Melbourne Mexico City Nairobi New Delhi Taipei Toronto Shanghai With offices in Argentina Austria Brazil Chile Czech Republic France Greece Guatemala Hungary Italy Japan South Korea Poland Portugal Singapore Switzerland Thailand Turkey Ukraine Vietnam Published in the United States byOxford University Press Inc.,New York © In this volume the Estate ofAlan Turing 2004 Supplementary Material © the several contributors 2004 The moral rights ofthe author have been asserted Database right Oxford University Press (maker) First published 2004 All rights reserved.No part ofthis publication may be reproduced, stored in a retrieval system,or transmitted,in any form or by any means, without the prior permission in writing ofOxford University Press, or as expressly permitted by law,or under terms agreed with the appropriate reprographics rights organization.Enquiries concerning reproduction outside the scope ofthe above should be sent to the Rights Department, Oxford University Press,at the address above. You must not circulate this book in any other binding or cover and you must impose this same condition on any acquirer. British Library Cataloguing in Publication Data Data available Library ofCongress Cataloging in Publication Data Data available ISBN 0–19–825079–7 ISBN 0–19–825080–0 (pbk.) 10 9 8 7 6 5 4 3 Typeset by Kolam Information Services Pvt.Ltd,Pondicherry,India Printed in Great Britain on acid-free paper by Biddles Ltd.,King’s Lynn,Norfolk Acknowledgements Work on this book began in 2000 at the Dibner Institute for the History of Science and Technology, Massachusetts Institute of Technology, and was com- pletedattheUniversityofCanterbury,NewZealand.Iamgratefultoboththese institutions for aid, and tothe followingfor scholarly assistance:JohnAndreae, Friedrich Bauer, Frank Carter, Alonzo Church Jnr, David Clayden, Bob Doran, Ralph Erskine, Harry Fensom, Jack Good, John Harper, Geoff Hayes, Peter Hilton, Harry Huskey, Eric Jacobson, Elizabeth Mahon, Philip Marks, Elisabeth Norcliffe,RolfNoskwith,GualtieroPiccinini,Andre´sSicard,WilfriedSieg,Frode Weierud, MauriceWilkes,MikeWoodger, andespeciallyDianeProudfoot. This book would not have existed without the support of Turing’s literary executor, P. N. Furbank, and that of Peter Momtchiloffat OxfordUniversity Press. B.J.C. This page intentionally left blank Contents Alan Turing 1912–1954 1 Jack Copeland Computable Numbers: A Guide 5 Jack Copeland 1. On Computable Numbers, with an Application to the Entscheidungsproblem (1936) 58 2. On Computable Numbers: Corrections and Critiques 91 Alan Turing, Emil Post, andDonald W. Davies 3. Systems of Logic Based on Ordinals (1938), including excerpts from Turing’s correspondence, 1936–1938 125 4. Letters on Logic to Max Newman (c.1940) 205 Enigma 217 Jack Copeland 5. History of Hut 8 to December 1941 (1945), featuring an excerpt from Turing’s ‘Treatise on the Enigma’ 265 Patrick Mahon 6. Bombe and Spider (1940) 313 7. Letter to Winston Churchill (1941) 336 8. Memorandum to OP-20-G on Naval Enigma (c.1941) 341 Artificial Intelligence 353 Jack Copeland 9. Lecture on the Automatic Computing Engine (1947) 362 10. Intelligent Machinery (1948) 395 viii | Contents 11. Computing Machinery and Intelligence (1950) 433 12. Intelligent Machinery, A Heretical Theory (c.1951) 465 13. Can Digital Computers Think? (1951) 476 14. Can Automatic Calculating Machines Be Said to Think? (1952) 487 Alan Turing, RichardBraithwaite, Geoffrey Jefferson, and MaxNewman Artificial Life 507 Jack Copeland 15. The Chemical Basis of Morphogenesis (1952) 519 16. Chess (1953) 562 17. Solvable and Unsolvable Problems (1954) 576 Index 597 Alan Turing 1912–1954 Jack Copeland Alan Mathison Turing was born on 23 June 1912 in London1; he died on 7 June 1954 at his home in Wilmslow, Cheshire. Turing contributed to logic, mathematics, biology, philosophy, cryptanalysis, and formatively to the areas later known as computer science, cognitive science, ArtiWcial Intelligence, and ArtiWcialLife. Educated at Sherborne School in Dorset, Turing went up to King’s College, Cambridge,inOctober1931toreadMathematics.Hegraduatedin1934,andin March 1935 was elected a Fellow of King’s, at the age of only 22. In 1936 he publishedhismostimportanttheoreticalwork,‘OnComputableNumbers,with an Application to the Entscheidungsproblem [Decision Problem]’ (Chapter 1, with corrections in Chapter 2). This article described the abstract digital com- puting machine—now referred to simply as the universal Turing machine—on which the modern computer is based. Turing’s fundamental idea of a universal stored-programme computing machine was promoted in the United States by JohnvonNeumannandinEnglandbyMaxNewman.Bytheendof1945several groups,includingTuring’sowninLondon,weredevisingplansforanelectronic stored-programme universaldigitalcomputer—a Turing machine inhardware. In 1936 Turing left Cambridge for the United States in order to continue his research at Princeton University. There in 1938 he completed a Ph.D. entitled ‘Systems of Logic Based on Ordinals’, subsequently published under the same title(Chapter 3,with furtherexpositioninChapter4). Nowaclassic, thiswork addressestheimplicationsofGo¨del’sfamousincompletenessresult.Turinggave anewanalysisofmathematicalreasoning,andcontinuedthestudy,begunin‘On Computable Numbers’, of uncomputable problems—problems that are ‘too hard’to be solvedbya computing machine (evenone with unlimited time and memory). Turing returned to his Fellowship at King’s in the summer of 1938. At the outbreak of war with Germany in September 1939 he moved to Bletchley Park, the wartime headquarters of the Government Code and Cypher School (GC & CS). Turing’s brilliant work at Bletchley Park had far-reaching consequences. 1 At2WarringtonCrescent,LondonW9,wherenowthereisacommemorativeplaque.