The Annotated Turing: A Guided Tour Through Alan Turing's Historic Paper on Computability and the Turing Machine

Introduction vii

I Foundations 1

1 This Tomb Holds Diophantus 3

2 The Irrational and the Transcendental 13

3 Centuries of Progress 35

II Computable Numbers 55

4 The Education of Alan Turing 57

5 Machines at Work 79

6 Addition and Multiplication 97

7 Also Known as Subroutines 111

8 Everything Is a Number 127

9 The Universal Machine 143

10 Computers and Computability 163

11 Of Machines and Men 189

III Das Entscheidungsproblem 199

12 Logic and Computability 201

13 Computable Functions 231

14 The Major Proof 259

15 The Lambda Calculus 281

16 Conceiving the Continuum 299

IV And Beyond 323

17 Is Everything a Turing Machine? 325

18 The Long Sleep of Diophantus 351

Selected Bibliography 361

Index 366