You are here

Computability:Turing, Gödel, Church, and Beyond

B. Jack Copeland, Carl J. Posy and Oron Shagrir, editors
MIT Press
Publication Date: 
Number of Pages: 
[Reviewed by
Michael Berg
, on

When I was an undergraduate at UCLA, the mathematics and philosophy departments each counted Alonzo Church as a member of their faculty. For a number of those years, back in the 1970s, I was pretty deeply involved in mathematical logic, largely due to the influence of a fabulous and charismatic rookie professor, Telis K. Menas, then a fresh Berkeley PhD under Robert Solovay. (I just learned that Professor Menas passed away only recently, in 2011 — God rest his soul.) As things unfolded, I opted for a minor in philosophy and so, in due course, enrolled in a seminar with Alonzo Church himself. I had some appreciation at the time of the fact that I was being taught by a true pioneer of mathematical logic, but, at the same time, his focus was perhaps more philosophical (for lack of a better word) than what was in vogue in the mathematics department at that time — I guess model theory was in the driver’s seat, as also the behavior of large (and exotic) cardinals. There was a lot of local activity, what with the Berkeley-Caltech-UCLA logic triangle going strong (as it still is today), but I don’t recall Church being a part of it. Indeed, his office was in the philosophy department, many buildings over from the mathematics department, and I only saw him in the latter building once.

Well, the book under review sports photographs of who are probably on every one’s list of the top three 20th century logicians, and there is Church, of course, together with Alan Turing and the capo di tutti capi himself, Kurt Gödel. And the subject of the book, as the title has it, is Computability.

The notion of a computable function is nowadays quickly tied to that of a Turing machine, but it wasn’t always so. Evidently, as this book’s introduction suggests, the idea itself goes back to Gödel, who first presented the notion of a “general recursive function,” working from a suggestion by Jacques Herbrand (an enfant terrible of logic who died at only 23). Gödel’s characterization was later supplanted, as far as accepted usage goes, by one by Stephen Kleene. With Kleene being a student of Church, he, together with Barkley Rosser, became involved in the development of one of the best-known themes in this part of mathematical logic, namely, Church’s lambda calculus. Presently — in fact it all happened at Princeton in 1934, when Gödel was visiting — Church proposed to Gödel that his

concept of “lambda definability” be taken as a precise, formal definition of effective calculability, but Gödel famously rejected Church’s suggestion, calling it “thoroughly unsatisfactory”. (Introduction, p. viii).

But Church pushed on nonetheless, and soon added the proposition that “the intuitive idea of an effectively calculable function could be identified with the concept of a recursive function.” It is in fact the case that these two pronouncements on Church’s part are equivalent: either qualifies as “Church’s thesis,” as the logicians’ jargon has it (pace Gödel). Add Turing’s machine-computability to the list and there is the central theme of the book under review.

Thus, Computability: Turing, Gödel, Church, and Beyond is a collection of eleven essays having to do with the aforementioned theme, and includes a lot of very interesting material indeed, ranging over quite a spectrum. It cannot be otherwise, given the appearance of such authors as Martin Davis (“Computability and Arithmetic”), Solomon Feferman (who hits the reals), and Hilary Putnam (who deals with the “Beyond” in the title, I guess: “After Gödel”).

The essays also include a number of discussions of philosophical interest. For example, Wilfried Sieg’s 8th chapter deals with Gödel’s challenge to Turing, which was actually posed by Gödel to himself (Turing being only an avatar opponent), the goal being a formal demonstration “that the human mind infinitely surpasses any finite machine” (cf. p.183). Scott Aronson’s 10th chapter deals tells us “Why Philosophers Should Care about Computational Complexity.” Finally, i.e. literally finally, in the 11th chapter, Dorit Aharonov and Umesh Vazirani introduce (whoa!) quantum mechanics into the proceedings.

The material, while obviously fascinating, does require a measure of experience with these parts of mathematical logic, and can be pretty sticky in places. But there is an awful lot here that makes for good browsing (at least for some one like me, a dilettante and occasional fellow-traveller). But that is perhaps being unfair to what is ultimately serious scholarship: for the right audience, these essays are proper candidates for dissection and digestion. And, to be sure, although logic is not every mathematician’s cup of tea, the historical (and philosophical) discussions that appear in these essays are already worth the price of admission. 

Michael Berg is Professor of Mathematics at Loyola Marymount University in Los Angeles, CA.


Scott Aaronson, Dorit Aharonov, B. Jack Copeland, Martin Davis, Solomon Feferman, Saul Kripke, Carl J. Posy, Hilary Putnam, Oron Shagrir, Stewart Shapiro, Wilfried Sieg, Robert I. Soare, Umesh V. Vazirani