Turing’s Revolution: The Impact of His Ideas About Computability

Preface (Martin Davis).-I  Introduction (Sommaruga, Strahm).-II Turing and the history of computability theory .- 1. Conceptual Confluence in 1936: Post & Turing, Martin Davis and 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? Jack Copeland and Giovanni Sommaruga.- III Generalizing Turing computability theory.- 1. Theses for Computation and Recursion on Concrete and Abstract Structures, Solomon Feferman.- 2. Generalizing Computability Theory to Abstract Algebras, John V. Tucker and Jeffrey Zucker.- 3. Discrete Transfinite Computation, Philip Welch.- 4. Semantics-to-Syntax Analyses of Algorithms, Yuri Gurevich.- 5. The Information Content of Typical Reals, George Barmpalias and Andy Lewis-Pye.- 6. Proof-theoretic Analysis by Iterated Reflection, Lev Beklemishev.-IV Philosophical reflections.- 1. Alan Turing and the Foundation of Computer Science, Juraj Hromkovic.- 2. Proving Things about the Informal, Stewart Shapiro.- 3. Why Turing’s Thesis is Not a Thesis, Robert Soare.- 4. Incomputability, Emergent, and Higher Type Computation, S. Barry Cooper.

Giovanni Sommaruga studied philosophy and philosophical and mathematical logic at the University of Freiburg (Switzerland), Stanford University and the University of Siena. In 1996 he became assistant professor in logic and philosophy of science at the Albert Ludwig University Freiburg (Germany), and since 2008 he has been a senior scientist in the philosophy of the formal sciences (logic, mathematics, theoretical computer science) at ETH Zurich. His main research interests are in the philosophy and foundations of mathematics, the history of mathematical logic, and more recently the history of computability and information in theoretical computer science, and related philosophical issues.