Front Cover -- Alan Turing: His Work and Impact -- Copyright -- List of Contributors -- Introduction -- Table of Contents -- Part I: How Do We Compute? What Can We Prove? -- Alan Mathison Turing by Max Newman -- A Comment on Newman's Biographical Memoir -- Alan Mathison Turing -- Scientific work -- 1. Mathematical logic -- '1. Computing machines -- 2. Three mathematical papers -- 3. Computing machines -- 4. Chemical theory of morphogenesis -- Bibliography -- On Computable Numbers, with an Application to the Entscheidungsproblem -- Alan and I -- On Computable Numbers, with an application to the entscheidungsproblem -- 1. Computing machines -- 2. Definitions -- Automatic machines -- Computing machines -- Circular and circle-free machines -- Computable sequences and numbers -- 3. Examples of computing machines -- 4. Abbreviated tables -- Further examples -- 5. Enumeration of computable sequences -- 6. The universal computing machine -- 7. Detailed description of the universal machine -- Subsidiary skeleton table -- 8. Application of the diagonal process -- 9. The extent of the computable numbers -- 10. Examples of large classes of numbers which are computable -- Computable convergence -- 11. Application to the Entscheidungsproblem -- Appendix -- Computability and effective calculability -- On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction -- Examining the Work and Its Later Impact -- The Importance of Universal Computation -- References -- Three Proofs of the Unsolvability of the Entscheidungsproblem -- The Entscheidungsproblem -- 1. Church's Proof -- 2. Turing's Proof -- 3. The should-have-been Gödel-Kleene Proof -- References -- Two Puzzles About Computation -- 1. Introduction -- 2. Why Do We Compute? -- Problem 1 -- Problem 2 -- 3. What Do We Compute? -- Why Does It Matter? -- References.

Turing Machines and Understanding Computational Complexity -- 1. Introduction -- 2. Formal definition of the Turing machine -- 2.1. Computable functions -- 2.2. Examples of computable functions -- 3. Computability thesis and the universal Turing machine -- 4. Undecidability of the halting problem -- 5. Complexity of computations -- 6. Importance of the Turing machine -- References -- From the Halting Problem to the Halting Probability -- Turing and the Art of Classical Computability -- 1. Mathematics as an art -- 2. Defining the effectively calculable functions -- 3. Why Turing and not Church? -- 4. Why Michelangelo and not Donatello? -- 5. Classical art and classical computability -- 5.1. Human scale -- 5.2. Composition and balance -- 6. Computability and recursion -- 7. The art of exposition -- 8. Conclusion -- References -- Turing Machines in Münster -- 1. Introduction -- 2. The object -- 2.1. Hardware layout -- 2.2. Examples -- 3. The papers -- 3.1. Universal Turing machines and Jones-Matiyasevich-masking -- 3.2. On the early history of register machines -- 4. Conclusion -- 5. State machine -- References -- Reflections on Wittgenstein's Debates with Turing During his Lectures on the Foundations of Mathematics -- References -- The Computational Power of Turing's Non-Terminating Circular a-Machines -- 1. Introduction -- 2. a-Machines and red-green Turing machines -- 2.1. a-Machines -- 2.2. Red-green Turing machines -- 2.3. Relation between a-machines and red-green Turing machines -- 3. Significance of the result -- 4. Conclusion -- Acknowledgements -- References -- Turing's Approach to Modelling States of Mind -- Acknowledgements -- References -- Conscious Cognition as a Discrete, Deterministic and Universal Turing Machine Process -- 1. Systems with states -- 2. The Turing machine: processes and computation -- 3. The neural Turing machine.

4. Conscious cognition: discrete temporal frames -- 5. Conscious cognition: mind states -- 6. Trained phenomenology -- 7. Conclusion -- References -- Virtual Machinery and Evolution of Mind (Part 1) -- 1. Virtual machines and causation -- 2. Virtuality -- 3. Causation and computation -- 4. Causation in RVMs -- 5. Implementable but irreducible -- 6. Implications -- References -- NOT -- References -- Halting and Non-Halting Turing Computations -- 1. Introduction -- 2. Turing machines -- 3. Resources -- 4. Halting time -- 5. Final comments -- Acknowledgements -- References -- Toward the Unknown Region: On Computing Infinite Numbers -- References -- On Computable Numbers, with an Application to the Entscheidungsproblem by A. M. Turing - Review by: Alonzo Church -- Church's Review of Computable Numbers -- Reference -- Computability and λ-Definability -- The Imperative and Functional Programming Paradigm -- 1. Models of computation -- 2. Functional programming -- 2.1. Features from lambda calculus -- 2.2. Features beyond lambda calculus -- 3. Types -- 4. Input/output -- 5. Current research -- 5.1. Parallelism -- 5.2. Certification -- 6. History and perspective -- References -- Computability and λ-Definability -- 1. Definition of λ-K-definability -- 2. Abbreviations -- 3. Mechanical conversion -- 4. Computability of λ-K-definable functions -- 5. Recursiveness of computable functions. -- The p-Function in λ-K Conversion -- Turing's Contributions to Lambda Calculus -- 1. Fixed point combinators in untyped lambda calculus -- 1.1. Lambda terms, reduction, and conversion -- 1.2. Fixed points -- 2. Weak normalisation of simply typed lambda calculus -- 2.1. Simply typed lambda terms and reduction -- 2.2. The proof of weak normalisation -- 2.3. Strong normalisation -- 3. Postscript -- References -- The p-Function in λ-K-Conversion.

Systems of Logic Based on Ordinals -- Turing's Thesis: Ordinal Logics and Oracle Computability -- 1. From Cambridge to Princeton -- 2. Turing in Princeton -- 3. The thesis: ordinal logics -- 4. Ordinal logics redux -- References -- Systems of Logic Based on Ordinals -- 1. The calculus of conversion. Gödel representations. -- 2. Effective calculability. Abbreviation of treatment. -- 3. Number-theoretic theorems. -- 4. A type of problem which is not number-theoretic. -- 5. Syntactical theorems as number-theoretic theorems. -- 6. Logic formulae. -- 7. Ordinals. -- 8. Ordinal logics. -- 9. Completeness questions. -- Definition of completeness of an ordinal logic -- Invariance of ordinal logics -- Incompleteness theorems. -- 10. The continuum hypothesis. A digression. -- 11. The purpose of ordinal logics. -- 12. Gentzen type ordinal logics. -- Index of definitions. -- Bibliography -- Examining the Work and Its Later Impact -- Turing's 'Oracle' in Proof Theory -- 1. Realisability -- 2. Heyting arithmetic in higher types -- 3. Realisability relative to an oracle -- References -- Truth and Turing -- References -- A Quantum Random Oracle -- 1. Turing's oracles -- 2. Value indefiniteness and the Kochen-Specker Theorem -- 3. An example of a quantum random oracle -- 4. A quantum random number generator certified by value indefiniteness -- 5. Hypercomputation via quantum random oracles -- References -- Practical Forms of Type Theory -- Preface -- Practical Forms of Type Theory -- 1. The nested-type system for a finite universe -- 2. Formal account of the nested-type system -- 3. Equivalence with Church's system -- 4. Relaxation of type notation -- The use of Dots as Brackets in Church's System -- Turing's dots -- The Use of Dots as Bracketsin Church's System -- General bracketing theory -- First form of rule -- Second form of rule -- Equivalence theorem.

Jutaxposition and omitted points -- Application to Church's system -- Discussion of the conventions -- Examples -- The Reform of Mathematical Notation and Phraseology -- Computation, Mathematical Notation and Linguistics -- References -- The Reform of Mathematical Notation and Phraseology -- Free and bound variables. Deduction theorem. Constants and parameters -- Theory of types and domains of definition -- Discussion of the system and application to normal mathematics -- Examining the Work and Its Later Impact -- Turing, Wittgenstein and Types: Philosophical Aspects of Turing's 'The Reform of Mathematical Notation and Phraseology' (1944-5) -- References -- Part II: Hiding and Unhiding Information: Cryptology, Complexity and Number Theory -- On the Gaussian error function -- Alan Turing and the Central Limit Theorem -- 1. Introduction -- 2. The central limit theorem -- 3. Turing's fellowship dissertation -- 3.1. Basic structure of the paper -- 3.2. The Quasi-necessary conditions -- 3.3. The sufficient conditions -- 3.4. One counterexample -- 4. Discussion -- References -- Turing's 'Preface' (1935) to 'On the Gaussian error function' -- Some Calculations of the Riemann Zeta function -- Alan Turing and the Riemann Zeta Function -- 1. Introduction -- 2. Recollection of some basics -- 3. On Turing's computations of the zeta function -- 4. On Turing's early work with zeta -- 5. A return to basics -- 6. Turing's skepticism about the RH -- References -- A Few Comments About Turing's Method -- References -- Some Calculations of The Riemann Zeta-Function -- Introduction -- Part I. General -- 1. The Θ notation -- 2. The approximate functional equation -- 3. Principles of the calculations -- 4. Evaluation of N(t) -- Part II. The Computations -- 1. Essentials of the Manchester computer -- 2. Outline of calculation method -- References.

On a Theorem of Littlewood.