Customer Reviews

Computability : Computable Functions Logic and the Foundations of Math (Wadsworth&Brooks/Cole Mathematics Series)

5 star:		(1)
4 star:		(1)
3 star:		(1)
2 star:		(0)
1 star:		(0)

 

 

This book is half mathematics and half discussion. Parts 2 & 3 cover the material for an integrated, introductory course in computability theory and logic (the primitive recursive functions, mu-recursive functions and Turing machines and their equivalence, first-order logic, some formal number theory, and Godel's first and second incompleteness theorems). Parts 1 & 4 are given to philosophical discussion and (to a lesser extent) historical background. The longest chapters are one examining Church's thesis and one on intuitionist/constructivist views of mathematics. Overall the book is clearly written and well organized, and it contains interesting selections from the writings of prominent figures in the foundations of mathematics throughout.

Adjoined to the end is a 25 page timeline, surveying 1834-1970. This is quite neat, but I wish it had been longer. The book should be useful both to people new to computability & logic, as well as those with some previous background, but the target audience is probably those with an interest in philosophy of mathematics.

1)Beginners- Its helpful to learn computability theory and logic together. But that's a lot of ground for a single volume to cover, and since this one is particularly short (parts 2&3 run only 157 pages), some of the material is only loosely sketched. I'd recommend a more thorough, grind-the-gory-details book as a central text and that you use Epstein & Carnielli as a supplement, providing a clean overview of whats going on. The philosophical material will either illuminate the motivation for the mathematical constructions, or will just muddy the waters for you, depending on your temperment. This can be skipped or skimmed if you want, but that would defeat the unity and aesthetic of the book. Be warned some of the historical writings will be hard for a beginner, especially as E&C dont take enough time to set the stage for them.

2)More experienced readers will enjoy the selections from Hilbert, Godel, Turing, Post, Brouwer and others. These arent the complete papers (see Davis or van Heijenoort for those), just choice passages. I enjoyed the amount of philosophical material included- more than your usual math book, but short enough to keep from getting tedious or slipping into general philosophy. Parts 2&3 form a succinct review of the basics if you need to brush up.

My five star review is relative to the chapters on primitive recursion and the Grzegorczyk Hierarchy. I haven't read the other sections.

Grzegorczyk's Hierarchy is an early result in complexity theory, which defines classes of functions based on the primitive recursive functions. This class is smaller than the class of functions computable by a Turing Machine and hence is theoretically less interesting to most complexity theorists. It's not easy to find these results described in detail.

I advocate making the details available for a number reasons. 1. Despite the sparseness of this class of functions, most programming tasks will wind up here. 2. A wide assortment of everyday mathematical functions can be defined recursively -- e.g. deduction -- so the pr functions are not theoretically vapid. 3. G's hierarchy describes the very nice structure of this versatile, but limited, class of functions, which can aid problem solving where applicable. 4. Some useful programming languages restrict themselves to the expressive power of the pr functions. 5. The machinery of pr functions looks very similar to Kleene's class (a historical successor of pr functions), which is equivalent to Turing's characterization. 6. Proof theory.

Most texts unjustly don't even mention this class, much less give the full details, so I was very happy to see that it was covered in this introductory text. But the coverage is striking in it's clarity. The pr functions are a very intuitive class of functions and this book treats them as such. I love the pace of this text, which is explicit, but not long winded. The exercises too build the reader's knowledge in an even fashion, with the obvious goal of giving a clear picture. Hand waving is avoided around Ackermann's function -- so rare to see! This book is a hidden gem with respect to the obscure topic of pr complexity.

this book takes you into the world of basic pure math. it covers the basic elemects of math such as sets, functions, and proofs. but what is really making this book great and far apart from other similiar books is its elaboration of recursive function and computability, and i find it interesting.