Recursive functions and metamathematics. Problems of completeness and decidability, Gödel's theorems (Q1125201)

The mathematical developments stemming from Hilbert's program occupy a justifiably central place in mathematical logic in the 20th century. In particular, the brilliant work of Gödel on the completeness and incompleteness theorems in the 30's and the unfolding of the story by Turing, Post, and others, is surely one of the intellectual triumphs of mankind. Therefore, it is particularly apt that Murawski writes a text based on and around Gödel's theorems, concentrating on decidability and undecidability in the computational sense. Muraswki begins with around 50 pages devoted to the analysis of models of computation. He starts with the (total) recursive functions (formulated in a useful but slightly unusual way, as the class generated by successor, zero, dotted minus, substitution, and least number \(\mu(s)[f(x,s)=1]\) applied to only functions \(f(x,s)\) such that \(\forall x\exists s [f(x,s)=1]\)), then proceeds through Markov algorithms and Turing machines. Neither the equivalences are proved, although both are stated. This is also where the partial recursive functions are introduced. A number of examples are proven to be recursive, such as definition by cases and the like. Murawski then turns to an analysis of some of the computation hierarchies. In particular he looks at the arithmetical and Grzegorczyk hierarchies with an analysis of the primitive recursive functions. Various closure properties of these classes are proven, and related results discussed. The relevance of this material on the primitive recursive functions comes later when the author looks at the Paris-Harrington material and other work on mathematical incompletenesses of PA. Finally, the author discusses Church's Thesis. It is worth noting that the discussion of Church's Thesis is significantly more detailed than one would normally find in a mathematical text on computability, and even discusses opposition to the thesis. The second section of the book consists of a very detailed account of Gödel's incompleteness theorems proved by standard arithmetization. The section ends with a short discussion of the Paris-Harrington-Kirby etc. material on indicators, Ramsey type theorems, Goodstein sequences, and the like. No proofs are given here. This section is also around 100 pages. The third section of the book is a somewhat briefer account of three basic methods of proving decidability and undecidability. The methods for decidability discussed are elimination of quantifiers, ``model theoretical methods'', and interpretation in, say, S2S. The example for the first is Presburger arithmetic, with other examples pointed at. The other methods are only sketched. Examples of the second include dense linear orderings without endpoints, and algebraically closed fields via Vaught's theorem. Finally there is a brief discussion of automata and Rabin's theorem. Murawski then turns to analysis of the complexity of the decision procedures. The section finishes with a discussion of Tarski type results on essential undecidability. The final section of the book is devoted to the author's ideas towards philosophical consequences of the material and a ``tour de horizon''. This material includes discussion of whether, and in what sense, Gödel's theorems settle Hilbert's program, what the incarnations of Hilbert's program, such as Reverse Mathematics, have appeared; how undecidability impacts on ``real'' mathematics such as Hilbert's 10th problem, and consequences of Gödel's theorem for computer science. In particular, the author seriously discusses Lucas/Penrose arguments, and thoughts on Gödel's theorem in relation to AI. Each section finishes with Historical Remarks. I found these interesting, if not always, to my limited historical knowledge, accurate or complete. For instance, the theorem that a complete consistent axiomatizable theory is decidable was known to many, not just Janiczak, 1950. (p. 212) Similarly, the fact that there is no algorithm that outputs all true statements of arithmetic and no false ones, is attributed to Boolos, 1989, (p. 155) whereas surely it is due to Post. Even the proof given, which uses the Berry paradox, is really a version of the Kolmogorov complexity proof, which can be traced at least to Chaitin in the 60's. The book is written with author prepared TeX and has the occasional errors such as misspellings, and missing articles, and some slightly suspect grammar, but for the most is well expressed. Certainly I found no part where the meaning was unclear. I think that the book is well organized in its selection of topics. However, I do have trouble visualizing a target audience. Parts of the book are done in extreme detail. For instance, the section on arithmetization is like this. Such detail would suggest perhaps the audience was a new graduate student. One could base a one semester course around the material on models of computation, decidability/undecidabilty and incompleteness, skimming through the other topics. However, I find it difficult to imagine a class of students wanting to pay US\$ 150 for a semester text! Also the parts that are given in detail are more or less standard. There are no exercises. Additionally, large parts seem to be done via sketches suggesting a much more mathematically mature audience. I very much preferred the sections with less notation and details. Finally, although I am unqualified to comment on the validity of the philosophy, I can say that those sections are quite sketchy, so the book is surely not aimed at a philosophy audience. Reviewer's remark: Therefore, I am not sure to whom I would recommend this book, particularly in view of the large price tag. I do not think that it is a text. In my teaching I will use the book as a reference. I believe that it is good to have it in my library. (Acknowledgement: This review was also written for Studia Logica).