Table of Contents
Acknowledgments ix
Introduction xi
1 Background 1
Mathematical Certainty 2
Boole's Logic 4
Mathematical Logic 5
Securing the Foundations of Mathematics 7
Hilbert's Approach 8
Gödel's Results 10
Turing's Results 11
2 Some Undecidable Decision Problems 15
Emil Post 16
Post's Correspondence Problem 17
Hilbert's Tenth Problem 22
The Halting Problem 24
Back to Turing at Cambridge 24
3 Finite Automata 25
Introduction 25
Finite Automata 27
Our First Machine 27
Alphabets and Languages 29
Finite Automata and Answering Questions 31
Omitting Traps from Diagrams 33
Some Basic Facts 35
Regular Expressions 37
Limitations of Finite Automata 41
Tapes and Configurations 43
Connection to the Correspondence Problem 44
4 Turing Machines 47
Examples of Turing Machines 52
Computable Functions and Calculations 59
Church-Turing Thesis 61
Computational Power 63
Machines That Don't Halt 67
5 Other Systems for Computation 69
The Lambda Calculus 72
Tag Systems 79
One-Dimensional Cellular Automata 82
6 Encodings and the Universal Machine 87
A Method of Encoding Finite Automata 88
Universal Machines 91
Construction of Universal Machines 93
Modern Computers Are Universal Machines 95
Von Neumann Architecture 97
Random Access Machines 98
RAMs Can Be Emulated by Turing Machines 101
Other Universal Machines 103
What Happens When We Input (M) into M? 104
7 Undecidable Problems 107
Proof by Contradiction 108
Russell's Barber 111
Finite Automata That Do Not Accept Their Encodings 113
Turing Machines That Do Not Accept Their Encodings 114
Does a Turing Machine Diverge on Its Encoding? Is Undecidable 116
The Acceptance, Hafting, and Blank Tape Problems 117
An Uncomputable Function 119
Turing's Approach 120
8 Cantor's Diagonalization Arguments 123
Georg Cantor 1845-1918 123
Cardinality 124
Subsets of the Rationals That Have the Same Cardinality 126
Hilbert's Hotel 129
Subtraction Is Not Well-Defined 131
General Diagonal Argument 131
The Cardinality of the Real Numbers 135
The Diagonal Argument 138
The Continuum Hypothesis 139
The Cardinality of Computations 140
Computable Numbers 141
A Non-Computable Number 142
There Is a Countable Number of Computable Numbers 143
Computable Numbers Are Not Effectively Enumerable 143
9 Turing's Legacy 147
Turing at Princeton 148
Second World War 150
Development of Computers in the 1940s 153
The Turing Test 157
Downfall 159
Apology and Pardon 161
Further Reading 163
Notes 167
Bibliography 183
Index 187