Turing’s Revolution

Part I. Turing and the History of Computability Theory

1. Conceptual Confluence in 1936: Post and Turing
Martin Davis, Wilfried Sieg

2. Algorithms: From Al-Khwarizmi to Turing and Beyond
Wolfgang Thomas

3. The Stored-Program Universal Computer: Did Zuse Anticipate Turing and von Neumann?
B. Jack Copeland, Giovanni Sommaruga

Part II. Generalizing Turing Computability Theory

4. Theses for Computation and Recursion on Concrete and Abstract Structures
Solomon Feferman

5. Generalizing Computability Theory to Abstract Algebras
J. V. Tucker, J. I. Zucker

6. Discrete Transfinite Computation
P. D. Welch

7. Semantics-to-Syntax Analyses of Algorithms
Yuri Gurevich

8. The Information Content of Typical Reals
George Barmpalias, Andy Lewis-Pye

9. Proof Theoretic Analysis by Iterated Reflection
L. D. Beklemishev

Part III. Philosophical Reflections

10. Alan Turing and the Foundation of Computer Science
Juraj Hromkovič

11. Proving Things About the Informal
Stewart Shapiro

12. Why Turing’s Thesis Is Not a Thesis
Robert Irving Soare

13. Incomputability Emergent, and Higher Type Computation
S. Barry Cooper

Avainsanat: Mathematics, Mathematical Logic and Foundations, History of Mathematical Sciences, Logic