The Book

Turing Day

Table of Contents

Foreword
Douglas Hofstadter

Part I. Turing's Life and Thoughts

Alan Turing: An Introductory Biography
Andrew Hodges

Alan's Apple: Hacking the Turing Test
Valeria Patera

1. The Author's View
2. Turing and the Apple - By Giulio Giorello
3. The Play

What Would Alan Turing Have Done After 1954?
Andrew Hodges

1. A Survey of Turing's Legacy in 1954
2. Church's Thesis and Copeland's Thesis
3. Computability and Quantum Physics

From Turing to the Information Society
Daniela Cerqui

1. The So-Called "Information Society"
2. An Anthropological Analysis
3. First Tendency: the Disappearing Body?
4. Second Tendency: Reproducing Every Bodily Element
5. Information as the Lowest Common Denominator
6. Turing, Wiener and Cybernetics
7. Intelligence, Rationality and Humankind
8. From Unorganized to Organized Machines
9. Towards a New Human Being?

Part II. Computation and Turing Machines

The Mechanization of Mathematics
Michael J. Beeson

1. Introduction
2. Before Turing
3. Hilbert and the Entscheidungsproblem
4. Turing's Negative Solution of the Entscheidungsproblem
5. Church and Gödel
6. The Possible Loopholes
7. The First Theorem-Provers
8. Kinds of Mathematical Reasoning
9. Computer Algebra
10. Decision Procedures in Algebra and Geometry
11. Equality Reasoning
12. Proofs Involving Computations
13. Searching for Proofs
14. Proofs Involving Sets, Functions, and Numbers
15. Conclusion

Hypercomputational Models
Mike Stannett

1. Introduction
2. A Taxonomy of Hypercomputation
3. Hypercomputer Engineering
4. Hypercomputational Characteristics
5. Conclusion and Summary

Turing's Ideas and Models of Computation
Eugene Eberbach, Dina Goldin, Peter Wegner

1. Introduction: Algorithmic Computation
2. Turing's Contributions to Computer Science
3. Super-Turing Computation
4. Models of Super-Turing Computation
5. Towards a New Kind of Computer Science
6. Rethinking the Theory of Computation
7. Conclusions

The Myth of Hypercomputation
Martin Davis

1. The Impossible as a Challenge
2. Algorithms and Infinity
3. Turing Machines, the Church-Turing Thesis, and Modern Computers
4. Hava Siegelmann Ventures "Beyond the Turing Limit"
5. Turing's O-Machines
6. Computing with Randomness and Quantum Computation
7. Mechanism
8. Algorithms: Universality vs. Complexity

Quantum Computers: the Church-Turing Hypothesis Versus the Turing Principle
Christopher G. Timpson

1. The Advent of Quantum Computers
2. From Bits to Qubits
3. The Turing Principle Versus the Church-Turing Hypothesis
4. The Computational Analogy
5. Deutsch and the Nature of Mathematics
6. Conclusion

Implementation of a Self-Replicating Universal Turing Machine
Hector Fabio Restrepo, Gianluca Tempesti, Daniel Mange

1. Introduction
2. Turing Machines
3. Self-replication of a Universal Turing Machine on a Multicellular Array
4. PICOPASCAL
5. Detailed Implementation of a Universal Turing Machine
6. Conclusion

Cognitive Science and the Turing Machine: an Ecological Perspective
Andrew J. Wells

1. Introduction
2. Turing's Analysis of Computation
3. The Implications of Turing's Analysis for Cognitive Science
4. Broadening the Scope of Turing's Analysis

Part III. Artificial Intelligence and the Turing Test

Can Machines Think?
Daniel C. Dennett

1. Can Machines Think?
2. Postscript [1985]: Eyes, Ears, Hands, and History
3. Postscript [1997]

The Computer, Artificial Intelligence, and the Turing Test
B. Jack Copeland, Diane Proudfoot

1. Turing and the Computer
2. Artificial Intelligence
3. Artificial Life
4. The Turing Test
5. Postscript

Strawberries with Cream, Mistakes, and Other Idiotic Features
Helmut Schnelle

1. Human Thought Capacity
2. Some Details on "Sub-computationality"
3. Some Details on "Con-computationality"

Robots and Rule-Following
Diane Proudfoot

1. Turing and Wittgenstein
2. Rule-Following
3. The Argument from Manufacturing History

The Law of Accelerating Returns
Ray Kurzweil

1. The Intuitive Linear View Versus the Historical Exponential View
2. The Law of Accelerating Returns
3. The Singularity Is Near
4. Wherefrom Moore's Law
5. Moore's Law Was Not the First, but the Fifth Paradigm to Provide for Exponential Growth of Computing
6. DNA Sequencing, Memory, Communications, the Internet, and Miniaturization
7. Notice How Exponential Growth Continued Through Paradigm Shifts from Vacuum Tubes to Discrete Transistors to Integrated Circuits
8. The Law of Accelerating Returns Applied to the Growth of Computation
9. The Software of Intelligence
10. Reverse Engineering the Human Brain
11. Scanning from Inside
12. How to Use Your Brain Scan
13. Downloading the Human Brain
14. Is the Human Brain Different from a Computer?
15. Objective and Subjective
16. The Importance of Having a Body
17. So Just Who Are These People?
18. A Thought Experiment
19. On Tubules and Quantum Computing
20. A Clear and Future Danger
21. Living Forever
22. The Next Step in Evolution and the Purpose of Life
23. Why Intelligence Is More Powerful than Physics

Part IV. The Enigma

The Polish Brains Behind the Enigma Code Breaking Before and During the Second World War
Elisabeth Rakus-Andersson

1. Introduction
2. The Cryptology Course in Poznan
3. The Enigma
4. The International Cooperation
5. The Breaking of the Enigma System
6. The New Devices as a Reaction to Changes in the Enigma Settings
7. French and English Efforts at Breaking Enigma
8. The Bombe as a Response to Further Changes in the Enigma System
9. The Gift to the Allies
10. The Mathematical Solution of Enigma
11. Epilogue

Alan Turing at Bletchley Park in World War II
Tony Sale

1. Alan Turing and the Enigma Machine
2. "Cribs" and Opened Out Enigmas
3. The "E" Rack
4. Adding the Diagonal Board to the Bombe
5. Alan Turing and the German Navy's Use of Enigma
6. Alan Turing and Lorenz
7. Alan Turing leaves Bletchley Park
8. An Appreciation of Alan Turing at Bletchley Park
9. A UK Public Record Office Document HW14/2
10. B Naval Enigma Situation, November 1939

Alan M. Turing's Contributions to Co-operation Between the UK and the US
Lee A. Gladwin

Part V. Almost Forgotten Ideas

Watching the Daisies Grow: Turing and Fibonacci Phyllotaxis
Jonathan Swinton

1. Introduction: Turing's Last, Lost Work
2. Fibonacci Phyllotaxis
3. Where do Spots Come from? The Turing Instability
4. Lattice generation
5. Geometrical Phyllotaxis
6. Dynamic Phyllotaxis
7. Routes to Phyllotaxis
8. Turing and Modern Approaches to Fibonacci Phyllotaxis
9. Conclusion
10. Acknowledgments

Turing's Connectionism
Christof Teuscher

1. Introduction
2. Connectionism and Artificial Neural Networks
3. Turing's Unorganized Machines
4. Organizing Unorganized Machines
5. Conclusion