You are previewing The Once and Future Turing.
O'Reilly logo
The Once and Future Turing

Book Description

Alan Turing (1912–1954) made seminal contributions to mathematical logic, computation, computer science, artificial intelligence, cryptography and theoretical biology. In this volume, outstanding scientific thinkers take a fresh look at the great range of Turing's contributions, on how the subjects have developed since his time, and how they might develop still further. The contributors include Martin Davis, J. M. E. Hyland, Andrew R. Booker, Ueli Maurer, Kanti V. Mardia, S. Barry Cooper, Stephen Wolfram, Christof Teuscher, Douglas Richard Hofstadter, Philip K. Maini, Thomas E. Woolley, Eamonn A. Gaffney, Ruth E. Baker, Richard Gordon, Stuart Kauffman, Scott Aaronson, Solomon Feferman, P. D. Welch and Roger Penrose. These specially commissioned essays will provoke and engross the reader who wishes to understand better the lasting significance of one of the twentieth century's deepest thinkers.

Table of Contents

  1. Cover
  2. Half-title page
  3. Title page
  4. Copyright page
  5. Contents
  6. Contributors
  7. Preface
  8. Introduction
  9. Part ONE  Part One: Inside Our Computable World, and the Mathematics of Universality
    1. 1 Algorithms, Equations, and Logic
      1. References
    2. 2 The Forgotten Turing
      1. References
    3. 3 Turing and the Primes
      1. References
    4. 4 Cryptography and Computation after Turing
      1. 4.1 Introduction
      2. 4.2 Cryptography
      3. 4.2.1 Introduction
      4. 4.2.2 The need for secret keys
      5. 4.2.3 Proving security
      6. 4.3 Computation
      7. 4.4 The Diffie–Hellman key-agreement protocol
      8. 4.4.1 Preliminaries
      9. 4.4.2 Efficient exponentiation
      10. 4.4.3 The key-agreement protocol
      11. 4.5 Discrete logarithms and other computational problems on groups
      12. 4.6 Discrete logarithm algorithms
      13. 4.6.1 Introduction
      14. 4.6.2 The baby-step giant-step algorithm
      15. 4.6.3 The Pohlig–Hellman algorithm
      16. 4.7 Abstract models of computation
      17. 4.7.1 Motivation
      18. 4.7.2 The computational model
      19. 4.7.3 Three types of problem
      20. 4.8 Proving security: lower bounds for complexity
      21. 4.8.1 Introduction
      22. 4.8.2 Two Lemmas
      23. 4.8.3 Group actions and the optimality of the baby-step giant-step algorithm
      24. 4.8.4 Discrete logarithms and the optimality of the Pohlig–Hellman algorithm
      25. 4.8.5 Product computation in and the CDH problem
      26. 4.8.6 The DDH problem
      27. 4.8.7 Generic reduction of the DL problem to the CDH problem
      28. 4.9 Conclusions
      29. References
    5. 5 Alan Turing and Enigmatic Statistics
      1. 5.1 Introduction
      2. 5.2 Weight of evidence and empirical Bayes
      3. 5.3 Alignment of letters
      4. 5.3.1 Description of the coding in Enigma
      5. 5.3.2 The significance of alignment of letters
      6. 5.4 Release by GCHQ of two key Turing reports
      7. 5.5 Turing’s statistics in context
      8. 5.5.1 Statistics and levels of abstraction
      9. 5.5.2 Scaling the informational hierarchy
      10. 5.6 Morphogenesis, statistics, and Alan Turing’s AI
      11. References
  10. Part TWO  Part Two: The Computation of Processes, and Not Computing the Brain
    1. 6 What Alan Turing Might Have Discovered
      1. References
    2. 7 Designed versus Intrinsic Computation
      1. 7.1 Top-down versus bottom-up design
      2. 7.2 Intrinsic versus designed computation
      3. 7.3 Turing’s bottom-up computing approach
      4. 7.4 From intrinsic to designed computation
      5. 7.5 Outlook
      6. References
    3. 8 Dull Rigid Human meets Ace Mechanical Translator
  11. Part THREE  Part Three: The Reverse Engineering Road to Computing Life
    1. 9 Turing’s Theory of Developmental Pattern Formation
      1. 9.1 Introduction
      2. 9.2 Some developmental applications
      3. 9.3 Extending Turing
      4. 9.4 Critiquing Turing
      5. 9.5 The impact of Turing
      6. References
    2. 10 Walking the Tightrope: The Dilemma of Hierarchical Instabilities in Turing’s Morphogenesis
      1. References
  12. Part FOUR  Part Four: Biology, Mind, and the Outer Reaches of Quantum Computation
    1. 11 Answering Descartes: Beyond Turing
      1. References
    2. 12 The Ghost in the Quantum Turing Machine
      1. 12.1 Introduction
      2. 12.1.1 ‘Free will’ versus ‘freedom’
      3. 12.1.2 Note on the chapter title
      4. 12.1.3 Level of this essay
      5. 12.2 FAQ
      6. 12.2.1 Narrow scientism
      7. 12.2.2 Bait-and-switch
      8. 12.2.3 Compatibilism
      9. 12.2.4 Quantum flapdoodle
      10. 12.2.5 Brain-uploading: who cares?
      11. 12.2.6 Determinism versus predictability
      12. 12.2.7 Quantum mechanics and hidden variables
      13. 12.2.8 The consequence argument
      14. 12.2.9 Paradoxes of prediction
      15. 12.2.10 Singulatarianism
      16. 12.2.11 The Libet experiments
      17. 12.2.12 Mind and morality
      18. 12.3 Knightian uncertainty and physics
      19. 12.3.1 Knightian uncertainty
      20. 12.3.2 Quantum mechanics and the no-cloning theorem
      21. 12.3.3 The freebit picture
      22. 12.3.4 Amplification and the brain
      23. 12.3.5 Against homunculi
      24. 12.4 Freedom from the inside out
      25. 12.4.1 The harmonization problem
      26. 12.4.2 Microfacts and macrofacts
      27. 12.5 Further objections
      28. 12.5.1 The advertiser objection
      29. 12.5.2 The weather objection
      30. 12.5.3 The gerbil objection
      31. 12.5.4 The initial-state objection
      32. 12.5.5 The Wigner’s-friend objection
      33. 12.6 Comparison with Penrose’s views
      34. 12.7 ‘Application’ to Boltzmann brains
      35. 12.7.1 What happens when we run out of freebits?
      36. 12.8 Indexicality and freebits
      37. 12.9 Is the freebit picture falsifiable?
      38. 12.10 Conclusions
      39. 12.10.1 Reason and mysticism
      40. 12A Appendix: Defining ‘freedom’
      41. 12B Appendix: Prediction and Kolmogorov complexity
      42. 12C Appendix: Knightian quantum states
      43. References
  13. Part FIVE  Part Five: Oracles, Infinitary Computation, and the Physics of the Mind
    1. 13 Turing’s ‘Oracle’: From Absolute to Relative Computability and Backa,a
      1. 13.1 Introduction
      2. 13.2 ‘Absolute’ effective computability
      3. 13.2.1 Machines and recursive functions
      4. 13.2.2 Partial recursive functions
      5. 13.2.3 Effectively unsolvable problems and the method of reduction
      6. 13.3 Relative effective computability over the natural numbers
      7. 13.3.1 Turing’s ‘oracle’ and Turing reducibility
      8. 13.3.2 Recursively enumerable sets, degrees of unsolvability, and Post’s problem
      9. 13.3.3 The solution of Post’s problem and the flowering of degree theory.
      10. 13.4 Uniform relative computability over the natural numbers
      11. 13.4.1 Relative computation procedures and partial recursive functionals
      12. 13.4.2 The recursion theorems
      13. 13.4.3 Partial recursive functionals of finite type over the natural numbers
      14. 13.5 Generalized recursion theory
      15. 13.5.1 Background and Overview
      16. 13.5.2 Computability over sets and ordinals
      17. 13.5.3 Computability over general structures
      18. 13.6 The role of notions of relative computability in actual computation
      19. 13.6.1 Computational practice and the theory of computation
      20. 13.6.2 Built-in functions and black boxes
      21. 13.6.3 Functional aspects of programming
      22. 13.6.4 Abstract data types
      23. 13.6.5 Degrees of complexity
      24. 13.6.6 Conclusion
      25. References
    2. 14 Turing Transcendent: Beyond the Event Horizon
      1. 14.1 The beginning
      2. 14.2 Limit decidable
      3. 14.3 Malament–Hogarth spacetimes
      4. 14.4 Infinite ordinals: beyond arithmetical
      5. 14.5 Returning to MH spacetimes
      6. 14.6 The -mind
      7. 14.7 Infinite-time Turing machines
      8. 14.8 Register machines and other generalisations
      9. 14.9 Conclusions
      10. References
    3. 15 On Attempting to Model the Mathematical Mind
      1. 15.1 Turing’s ordinal logics
      2. 15.2 Mathematical trust
      3. 15.3 Physical processes underlying mathematical understanding?
      4. 15.4 Π-sentences
      5. 15.5 Cautious oracles
      6. 15.6 The operation of cautious-oracle devices
      7. 15.7 A Gödel-type theorem for cautious-oracle devices
      8. 15.8 Physical implications?
      9. References
  14. Afterword