Toprotecttherightsoftheauthor(s)andpublisherweinformyouthatthisPDFisanuncorrectedproofforinternalbusinessuseonlybytheauthor(s),editor(s),reviewer(s),Elsevier andtypesetterdiacriTech.Itisnotallowedtopublishthisproofonlineorinprint.Thisproofcopyisthecopyrightpropertyofthepublisherandisconfidentialuntilformalpublication. A.M.Turing 2013/3/12 10:13 Page xxiii #11 Toprotecttherightsoftheauthor(s)andpublisherweinformyouthatthisPDFisanuncorrectedproofforinternalbusinessuseonlybytheauthor(s),editor(s),reviewer(s),Elsevier andtypesetterdiacriTech.Itisnotallowedtopublishthisproofonlineorinprint.Thisproofcopyisthecopyrightpropertyofthepublisherandisconfidentialuntilformalpublication. A.M.Turing 2013/3/12 10:19 Page i #1 Alan Turing HISWORKANDIMPACT Toprotecttherightsoftheauthor(s)andpublisherweinformyouthatthisPDFisanuncorrectedproofforinternalbusinessuseonlybytheauthor(s),editor(s),reviewer(s),Elsevier andtypesetterdiacriTech.Itisnotallowedtopublishthisproofonlineorinprint.Thisproofcopyisthecopyrightpropertyofthepublisherandisconfidentialuntilformalpublication. A.M.Turing 2013/3/12 10:13 Page xxiii #11 Thispageintentionallyleftblank Toprotecttherightsoftheauthor(s)andpublisherweinformyouthatthisPDFisanuncorrectedproofforinternalbusinessuseonlybytheauthor(s),editor(s),reviewer(s),Elsevier andtypesetterdiacriTech.Itisnotallowedtopublishthisproofonlineorinprint.Thisproofcopyisthecopyrightpropertyofthepublisherandisconfidentialuntilformalpublication. A.M.Turing 2013/3/8 15:34 Page iii #3 Alan Turing HIS WORK AND IMPACT Editedby S.BARRYCOOPER UniversityofLeeds,UK and JANVANLEEUWEN UtrechtUniversity,TheNetherlands AMSTERDAM•BOSTON•HEIDELBERG•LONDON NEWYORK•OXFORD•PARIS•SANDIEGO SANFRANCISCO•SINGAPORE•SYDNEY•TOKYO Toprotecttherightsoftheauthor(s)andpublisherweinformyouthatthisPDFisanuncorrectedproofforinternalbusinessuseonlybytheauthor(s),editor(s),reviewer(s),Elsevier andtypesetterdiacriTech.Itisnotallowedtopublishthisproofonlineorinprint.Thisproofcopyisthecopyrightpropertyofthepublisherandisconfidentialuntilformalpublication. A.M.Turing 2013/3/12 10:19 Page iv #4 Elsevier 225WymanStreet,Waltham,MA02451,USA TheBoulevard,LangfordLane,Kidlington,OxfordOX51GB,UK Radarweg29,POBox211,1000AEAmsterdam,TheNetherlands Copyright(cid:13)c 2013ElsevierInc.Allrightsreserved Nopartofthispublicationmaybereproduced,storedinaretrievalsystemortransmittedinanyformorby anymeanselectronic,mechanical,photocopying,recordingorotherwisewithoutthepriorwrittenpermission ofthepublisherPermissionsmaybesoughtdirectlyfromElsevier’sScience&TechnologyRights DepartmentinOxford,UK:phone(+44)(0)1865843830;fax(+44)(0)1865853333;email: permissions@elsevier.com.AlternativelyyoucansubmityourrequestonlinebyvisitingtheElsevierwebsite athttp://elsevier.com/locate/permissions,andselectingObtainingpermissiontouseElseviermaterial Notice Noresponsibilityisassumedbythepublisherforanyinjuryand/ordamagetopersonsorpropertyasamatter ofproductsliability,negligenceorotherwise,orfromanyuseoroperationofanymethods,products, instructionsorideascontainedinthematerialherein.Becauseofrapidadvancesinthemedicalsciences,in particular,independentverificationofdiagnosesanddrugdosagesshouldbemade LibraryofCongressCataloging-in-PublicationData AcatalogrecordforthisbookisavailablefromtheLibraryofCongress BritishLibraryCataloguinginPublicationData AcataloguerecordforthisbookisavailablefromtheBritishLibrary ForinformationonallElsevierpublications visitourwebsiteatelsevierdirect.com PrintedandboundinUSA 12 13 14 15 10 9 8 7 6 5 4 3 2 1 ISBN:978-0-12-386980-7 (cid:13)c MatthewOldfieldPhotography,TuringStatueatBletchleyPark,NationalCodesCentre.Createdby StephenKettleandcommissionedbytheSidneyEFrankFoundation. Toprotecttherightsoftheauthor(s)andpublisherweinformyouthatthisPDFisanuncorrectedproofforinternalbusinessuseonlybytheauthor(s),editor(s),reviewer(s),Elsevier andtypesetterdiacriTech.Itisnotallowedtopublishthisproofonlineorinprint.Thisproofcopyisthecopyrightpropertyofthepublisherandisconfidentialuntilformalpublication. A.M.Turing 2013/3/8 16:29 Page v #1 List of Contributors AlastairAbbott DepartmentofComputerScience,TheUniversityofAuckland,Auckland,NewZealand SamsonAbramsky DepartmentofComputerScience,OxfordUniversity,Oxford,UK HenkBarendregt Institute for Computing and Information Sciences, Faculty of Science, Radboud University, Nijmegen,TheNetherlands CraigBauer DepartmentofPhysicalSciences,YorkCollegeofPennsylvania,York,PA,USA AnthonyBeavers Philosophy&CognitiveScience,TheUniversityofEvansville,Evansville,IN,USA Vero´nicaBecher DepartamentodeComputacio´n,FacultaddeCienciasExactasyNaturales,UniversidaddeBuenos AiresandCONICET,CiudadUniversitaria,BuenosAires,Argentina NelsonH.F.Beebe DepartmentofMathematics,UniversityofUtah,SaltLakeCity,UT,USA HenriBerestycki UniversityofChicago,andL’E´coledeshautese´tudesensciencessociales(EHESS),Paris,France MeurigBeynon DepartmentofComputerScience,UniversityofWarwick,Coventry,UK MarkBishop DepartmentofComputing,Goldsmiths,UniversityofLondon,NewCross,London,UK LenoreBlum SchoolofComputerScience,CarnegieMellonUniversity,Pittsburgh,PA,USA RodneyBrooks Emeritus Professor of Robotics, Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge,USA CristianCalude DepartmentofComputerScience,TheUniversityofAuckland,Auckland,NewZealand GregoryChaitin ProfessorofMathematics,FederalUniversityofRiodeJaneiro(UFRJ),RiodeJaneiro,Argentina JackCopeland SchoolofSocialandPoliticalSciences,UniversityofCanterbury,Christchurch,NewZealand v Toprotecttherightsoftheauthor(s)andpublisherweinformyouthatthisPDFisanuncorrectedproofforinternalbusinessuseonlybytheauthor(s),editor(s),reviewer(s),Elsevier andtypesetterdiacriTech.Itisnotallowedtopublishthisproofonlineorinprint.Thisproofcopyisthecopyrightpropertyofthepublisherandisconfidentialuntilformalpublication. A.M.Turing 2013/3/8 16:29 Page vi #2 vi ListofContributors MartinDavis DepartmentofMathematics,UniversityofCalifornia,Berkeley,CA,USA DanielDennett CenterforCognitiveStudies,TuftsUniversity,Medford,MA,USA ArturEkert MathematicalInstitute,UniversityofOxford,Oxford,UKandCentreforQuantumTechnologies, NationalUniversityofSingapore,Singapore SolomonFeferman DepartmentofMathematics,StanfordUniversity,Stanford,CA,USA LucianoFloridi School of Humanities, University of Hertfordshire, Hertfordshire, and Department of Computer Science,UniversityofOxford,Oxford,UK JulietFloyd PhilosophyDepartment,BostonUniversity,Boston,MA,USA LanceFortnow SchoolofComputerScience,GeorgiaInstituteofTechnology,Atlanta,USA EinarFredriksson IOSPress,Amsterdam,TheNetherlands NicholasGessler InformationScience&InformationStudies,DukeUniversity,Durham,NC,USA RainerGlaschick Paderborn,Germany DavidHarel Department of Computer Science and Applied Mathematics, The Weizmann Institute of Science, Rehovot,Israel JohnHarper Retired,HonoraryFellowoftheBritishComputerSociety DennisHejhal SchoolofMathematics,UniversityofMinnesota,Minneapolis,MN,USA AndrewHodges WadhamCollege,OxfordUniversity,Oxford,UK DouglasHofstadter CollegeofArtsandSciences,CenterforResearchonConceptsandCognition,IndianaUniversity, Bloomington,IN,USA TobyHoward SchoolofComputerScience,TheUniversityofManchester,Manchester,UK Toprotecttherightsoftheauthor(s)andpublisherweinformyouthatthisPDFisanuncorrectedproofforinternalbusinessuseonlybytheauthor(s),editor(s),reviewer(s),Elsevier andtypesetterdiacriTech.Itisnotallowedtopublishthisproofonlineorinprint.Thisproofcopyisthecopyrightpropertyofthepublisherandisconfidentialuntilformalpublication. A.M.Turing 2013/3/8 16:29 Page vii #3 ListofContributors vii CliffJones SchoolofComputingScience,NewcastleUniversity,Newcastle,UK RichardJozsa DAMTP,CentreforMathematicalSciences,UniversityofCambridge,Cambridge,UK JanvanLeeuwen DepartmentofInformationandComputingSciences,UtrechtUniversity,Utrecht,TheNetherlands DavidLevy IntelligentToysLtd,London,UK PhilipMaini CentreforMathematicalBiology,MathematicalInstitute,OxfordUniversity,Oxford,UK GiulioManzonetto LIPN-InstitutGalile´e,Universite´ Paris-Nord,Villetaneuse,France HansMeinhardt Max-Planck-Institutfu¨rEntwicklungsbiologie,Tu¨bingen,Germany PeterMillican FacultyofPhilosophy, OxfordUniversity,Oxford,UK JamesD.Murray ProfessorEmeritus,MathematicalInstitute,UniversityofOxford,Oxford,UK AndrewOdlyzko SchoolofMathematics,UniversityofMinnesota,Minneapolis,MN,USA ChristosPapadimitriou EECSDepartment,UniversityofCalifornia,Berkeley,CA,USA RinusPlasmeijer Institute for Computing and Information Sciences, Faculty of Science, Radboud University, Nijmegen,TheNetherlands AntoninoRaffone DepartmentofPsychology,SapienzaUniversityofRome,Rome,Italy MichaelRathjen SchoolofMathematics,UniversityofLeeds,Leeds,UK BernardRichards EmeritusProfessorofMedicalInformatics,UniversityofManchester,Manchester,UK AnthonyEdgar“Tony”Sale,FBCS(30January1931–28August2011) FoundermemberBletchleyParkTrust,leaderColossusrebuildproject PeterT.Saunders DepartmentofMathematics,King’sCollege,Strand,London,UK Toprotecttherightsoftheauthor(s)andpublisherweinformyouthatthisPDFisanuncorrectedproofforinternalbusinessuseonlybytheauthor(s),editor(s),reviewer(s),Elsevier andtypesetterdiacriTech.Itisnotallowedtopublishthisproofonlineorinprint.Thisproofcopyisthecopyrightpropertyofthepublisherandisconfidentialuntilformalpublication. A.M.Turing 2013/3/8 16:29 Page viii #4 viii ListofContributors KlausSchmeh Gelsenkirchen,Germany HumaShah SchoolofSystemsEngineering,UniversityofReading,Reading,UK WilfriedSieg DepartmentofPhilosophy,CarnegieMellonUniversity,Pittsburgh,PA,USA AaronSloman SchoolofComputerScience,UniversityofBirmingham,Birmingham,UK AlanSlomson SchoolofMathematics,UniversityofLeeds,Leeds,UK PaulSmolensky DepartmentofCognitiveScience,TheJohnsHopkinsUniversity,Baltimore,MD,USA RobertI.Soare DepartmentofMathematics,TheUniversityofChicago,Chicago,IL,USA LudwigStaiger Institutfu¨rInformatik,Martin-Luther-Universita¨t,Halle,Germany MichaelStay Google Inc., CA, USA, and Department of Computer Science, The University of Auckland, Auckland,NewZealand KarlSvozil Institutfu¨rTheoretischePhysik,TechnischeUniversita¨tWien,Vienna,Austria JonathanSwinton Physiomicsplc,OxfordSciencePark,Oxford,UK ChristofTeuscher ECEDepartment,PortlandStateUniversity,Portland,OR,USA K.VelaVelupillai DepartmentofEconomics,UniversityofTrento,Trento,Italy TomVickers Retired, Manager computing service that developed and used the Pilot ACE, at National Physical Laboratory(NPL),Teddington,London,UK PaulVita´nyi CWI,Amsterdam,TheNetherlands KevinWarwick SchoolofSystemsEngineering,UniversityofReading,Reading,UK FrodeWeierud LePreVert,Prevessin-Moens,France Toprotecttherightsoftheauthor(s)andpublisherweinformyouthatthisPDFisanuncorrectedproofforinternalbusinessuseonlybytheauthor(s),editor(s),reviewer(s),Elsevier andtypesetterdiacriTech.Itisnotallowedtopublishthisproofonlineorinprint.Thisproofcopyisthecopyrightpropertyofthepublisherandisconfidentialuntilformalpublication. A.M.Turing 2013/3/8 16:29 Page ix #5 ListofContributors ix PhilipWelch SchoolofMathematics,UniversityofBristol,Bristol,UK Jirˇ´ıWiedermann InstituteofComputerScience,AcademyofSciencesoftheCzechRepublic,Prague, CzechRepublic StephenWolfram WolframResearch,Champaign,IL,USA MikeYates EmeritusProfessorofMathematics,UniversityofManchester,Manchester,UK SandyL.Zabell DepartmentofMathematics,NorthwesternUniversity,Evanston,IL,USA