Turing’s Revolution

1. Front Matter

   Pages i-xxiv

   PDF

2. Turing and the History of Computability Theory

   1. Front Matter

      Pages 1-1

      PDF

   2. Conceptual Confluence in 1936: Post and Turing

      • Martin Davis, Wilfried Sieg

      Pages 3-27

   3. Algorithms: From Al-Khwarizmi to Turing and Beyond

      • Wolfgang Thomas

      Pages 29-42

   4. The Stored-Program Universal Computer: Did Zuse Anticipate Turing and von Neumann?

      • B. Jack Copeland, Giovanni Sommaruga

      Pages 43-101Open Access

3. Generalizing Turing Computability Theory

   1. Front Matter

      Pages 103-103

      PDF

   2. Theses for Computation and Recursion on Concrete and Abstract Structures

      • Solomon Feferman

      Pages 105-126

   3. Generalizing Computability Theory to Abstract Algebras

      • J. V. Tucker, J. I. Zucker

      Pages 127-160

   4. Discrete Transfinite Computation

      • P. D. Welch

      Pages 161-185

   5. Semantics-to-Syntax Analyses of Algorithms

      • Yuri Gurevich

      Pages 187-206

   6. The Information Content of Typical Reals

      • George Barmpalias, Andy Lewis-Pye

      Pages 207-224

   7. Proof Theoretic Analysis by Iterated Reflection

      • L. D. Beklemishev

      Pages 225-270

4. Philosophical Reflections

   1. Front Matter

      Pages 271-271

      PDF

   2. Alan Turing and the Foundation of Computer Science

      • Juraj Hromkovič

      Pages 273-281

   3. Proving Things About the Informal

      • Stewart Shapiro

      Pages 283-296

   4. Why Turing’s Thesis Is Not a Thesis

      • Robert Irving Soare

      Pages 297-310

   5. Incomputability Emergent, and Higher Type Computation

      • S. Barry Cooper

      Pages 311-329

5. Correction to: The Stored-Program Universal Computer: Did Zuse Anticipate Turing and von Neumann?

   • B. Jack Copeland, Giovanni Sommaruga

   Pages C1-C1

This book provides an overview of the confluence of ideas in Turing’s era and work and examines the impact of his work on mathematical logic and theoretical computer science. It combines contributions by well-known scientists on the history and philosophy of computability theory as well as on generalised Turing computability. By looking at the roots and at the philosophical and technical influence of Turing’s work, it is possible to gather new perspectives and new research topics which might be considered as a continuation of Turing’s working ideas well into the 21st century.

The Stored-Program Universal Computer: Did Zuse Anticipate Turing and von Neumann?” is available open access under a Creative Commons Attribution 4.0 International License via link.springer.com

• Alonzo Church
• Emil Post
• computer music
• generalised computability
• philosophy of computability

“There is a wide variety of content … in this collection about Turing’s ideas and what they meant for mathematics and computer science. … People of all mathematical and computer science backgrounds will find something of interest in this collection. Educators that would like to go deeper into the meaning of computability and algorithms can find material that will set the stage for discussions and research papers on the meaning and impact of the life and work of Alan Turing.” (Charles Ashbacher, MAA Reviews, maa.org, February, 2016)

• Department of Humanities, Social and Political Sciences, ETH Zurich, Zurich, Switzerland

  Giovanni Sommaruga

• Institute of Computer Science and Applied Mathematics, University of Bern, Bern, Switzerland

  Thomas Strahm

Giovanni Sommaruga is Professor for philosopy of logic and mathematics at ETH Zurich, Switzerland. Thomas Strahm is Professor for mathematical logic and theoretical computer science at the University of Berne, Switzerland.

Policies and ethics