New book on Computability

Computability: Turing, Gödel, Church, and Beyond (eds. Jack Copeland, Carl Posy, Oron Shagrir) recently published with MIT (2013).

***

Computability and Brains have a shared history. Computability was initiated with a conference held in Jerusalem and Tel Aviv in 2006. The conference was organized by the editors of Computability, and included some of the founders of AI, computability and complexity theory (John McCarthy, Michael Rabin, Martin Davis, and others). Some of the conference presentations were turned into chapters. Well, it took seven years to complete the project. Gualtiero Piccinini reported from the conference in Brains, that was launched only few months before. [Ed. note: Those posts are from June 2006. — JS]

The volume includes eleven articles from a group of very interesting philosophers and computer scientists. There is the beautiful chapter by Saul Kripke, arguing that the Church-Turing thesis is a corollary of Gödel’s completeness theorem. Another outstanding paper on the thesis is by Stewart Shapiro who argues that the meaning of human (algorithmic) computability, like those of many scientific terms, is an evolving phenomenon. In the case of human computability, the extension of the predicate has become sharper with developments in computability and recursion theory.

Several chapters are historical in perspectives. Robert Soare describes the legacy of Turing and Post in modern interactive and online computing. His interesting claim is that Turing’s 1939 paper is far more central to the development of current methods of interactive and online computing than his seminal 1936 paper. Hilary Putnam discusses the impact of Gödel’s work on modern mathematical logic and recursion theory. Martin Davis discusses the fascinating history of the negative solution of Hilbert’s tenth problem (both Putnam and Davis played a central role in the solution of the problem).

The volume covers other ground as well. Both Solomon Feferman and Carl Posy discuss developments in the theory of computability over the real numbers. Feferman draws a comparison between the different theories of computation on reals from a conceptual basis. Posy discusses the relationship between computability and constructivity in mathematics. Copeland and Shagrir, and Wilfried Sieg address the relationship between computability and the mind. They discuss the issue of whether Turing-computability places an upper bound on the powers of the human mind. Though disagreeing over other issues, they reach the same surprising conclusion that Turing consistently held that human mathematical thinking has non-computable elements (see also Piccinini’s 2003 article on the mathematical objection).

The book closes with two exciting chapters on complexity theory, which is the next generation in the philosophy of computing. Scott Aaronson argues that complexity theory is very relevant to many philosophical issues. Among the various aspects he discusses, Aaronson raises the question whether the mind is limited to solving problems whose solutions are obtainable in polynomial time. Another and related issue is whether mathematical proofs should be limited to those obtainable in polynomial time. Dorit Aharonov and Umesh Vazirani ask how the natural world can be studied at all, if quantum mechanics exhibits exponential complexity. They describe a foundation for experimental science that is based on the mathematical concept of interactive proof.