STUDENT MATHEMATICAL LIBRARY Volume 62 Computability Theory Rebecca Weber Computability Theory STUDENT MATHEMATICAL LIBRARY Volume 62 Computability Theory Rebecca Weber American Mathematical Society Providence, Rhode Island Editorial Board Gerald B. Folland Brad G. Osgood (Chair) Robin Forman John Stillwell 2000 Mathematics Subject Classification. Primary 03Dxx; Secondary 68Qxx. For additional information and updates on this book, visit www.ams.org/bookpages/stml-62 Library of Congress Cataloging-in-Publication Data Weber,Rebecca,1977– Computabilitytheory/RebeccaWeber. p.cm. —(Studentmathematicallibrary;v.62) Includesbibliographicalreferencesandindex. ISBN978-0-8218-7392-2(alk.paper) 1.Recursiontheory. 2.Computablefunctions. I.Title. QA9.6.W43 2012 511.3(cid:2)52—dc23 2011050912 Copying and reprinting. Individual readers of this publication, and nonprofit libraries acting for them, are permitted to make fair use of the material, such as to copy a chapter for use in teaching or research. Permission is granted to quote brief passagesfromthispublicationinreviews,providedthecustomaryacknowledgmentof thesourceisgiven. Republication,systematiccopying,ormultiplereproductionofanymaterialinthis publicationispermittedonlyunderlicensefromtheAmericanMathematicalSociety. Requests for such permission should be addressed to the Acquisitions Department, AmericanMathematicalSociety,201CharlesStreet,Providence,RhodeIsland02904- 2294USA.Requestscanalsobemadebye-mailtoreprint-permission@ams.org. (cid:2)c 2012bytheAmericanMathematicalSociety. Allrightsreserved. TheAmericanMathematicalSocietyretainsallrights exceptthosegrantedtotheUnitedStatesGovernment. PrintedintheUnitedStatesofAmerica. (cid:2)∞ Thepaperusedinthisbookisacid-freeandfallswithintheguidelines establishedtoensurepermanenceanddurability. VisittheAMShomepageathttp://www.ams.org/ 10987654321 171615141312 Contents Chapter 1. Introduction 1 §1.1. Approach 1 §1.2. Some History 4 §1.3. Notes on Use of the Text 6 §1.4. Acknowledgements and References 7 Chapter 2. Background 9 §2.1. First-Order Logic 9 §2.2. Sets 15 §2.3. Relations 21 §2.4. Bijection and Isomorphism 29 §2.5. Recursion and Induction 30 §2.6. Some Notes on Proofs and Abstraction 37 Chapter 3. Defining Computability 41 §3.1. Functions, Sets, and Sequences 41 §3.2. Turing Machines 43 §3.3. Partial Recursive Functions 50 §3.4. Coding and Countability 56 §3.5. A Universal Turing Machine 62 v vi Contents §3.6. The Church-Turing Thesis 65 §3.7. Other Definitions of Computability 66 Chapter 4. Working with Computable Functions 77 §4.1. The Halting Problem 77 §4.2. The “Three Contradictions” 78 §4.3. Parametrization 79 §4.4. The Recursion Theorem 81 §4.5. Unsolvability 85 Chapter 5. Computing and Enumerating Sets 95 §5.1. Dovetailing 95 §5.2. Computing and Enumerating 96 §5.3. Aside: Enumeration and Incompleteness 102 §5.4. Enumerating Noncomputable Sets 105 Chapter 6. Turing Reduction and Post’s Problem 109 §6.1. Reducibility of Sets 109 §6.2. Finite Injury Priority Arguments 115 §6.3. Notes on Approximation 124 Chapter 7. Two Hierarchies of Sets 127 §7.1. Turing Degrees and Relativization 127 §7.2. The Arithmetical Hierarchy 131 §7.3. Index Sets and Arithmetical Completeness 135 Chapter 8. Further Tools and Results 139 §8.1. The Limit Lemma 139 §8.2. The Arslanov Completeness Criterion 142 §8.3. E Modulo Finite Difference 145 Chapter 9. Areas of Research 149 §9.1. Computably Enumerable Sets and Degrees 149 §9.2. Randomness 155 §9.3. Some Model Theory 169 Contents vii §9.4. Computable Model Theory 174 §9.5. Reverse Mathematics 177 Appendix A. Mathematical Asides 189 §A.1. The Greek Alphabet 189 §A.2. Summations 190 §A.3. Cantor’s Cardinality Proofs 190 Bibliography 193 Index 199 Chapter 1 Introduction The bird’s-eye view of computability: what does it mean, how does it work, where did it come from? 1.1. Approach If I can program my computer to execute a function, to take any input and give me the correct output, then that function should cer- tainly be called computable. That set of functions is not very large, though; I am not a particularly skilled programmer and my com- puterisnothingspectacular. Imightexpandmydefinitiontosayifa wizardlyprogrammer canprogramthebestcomputerthereistoexe- cute afunction, thatfunction is computable. However, programming languages and environments improve with time, making it easier to programcomplicatedfunctions,andcomputersincreaseinprocessing speed and amount of working memory. The idea of “computable” as “programmable” provides excellent intuition, but the precise mathematical definition needs to be an ide- alizedversionthatdoesnotchangewithhardwareadvances. Itshould capture all of the functions that may be automated even in theory. To that end, computability theory removes any restriction on timeandmemoryexceptthatasuccessfulcomputationmustuseonly finitely much of each. When that change is made, the rest of the 1