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

Richard L. Epstein (Author)

Book Description

Publication Date: November 9, 1989 | ISBN-10: 0534103561 | ISBN-13: 978-0534103569 | Edition: 1

This book should be of interest to intermediate mathematics undergraduates; postgraduates in theoretical computer science/philosophy of mathematics.

Editorial Reviews

About the Author

Richard L. Epstein received his B.A. summa cum laude at the University of Pennsylvania and his Ph.D. at the University of California, Berkeley. He held a postdoctoral fellowship in mathematics and philosophy at Victoria University of Wellington, New Zealand, before an extensive career teaching mathematics and philosophy. He has been a Fulbright Scholar to Brazil and a National Academy of Sciences Scholar to Poland. He also owned and managed the Dog & Duck Coffee House. He is the author of the series of research texts THE SEMANTIC FOUNDATIONS OF LOGIC as well as CRITICAL THINKING and FIVE WAYS OF SAYING "THEREFORE". Currently he is head of the Advanced Reasoning Forum in Socorro, New Mexico. --This text refers to the Paperback edition.

Product Details

• Hardcover: 320 pages
• Publisher: Springer; 1 edition (November 9, 1989)
• Language: English
• ISBN-10: 0534103561
• ISBN-13: 978-0534103569
• Product Dimensions: 9.7 x 7.4 x 0.8 inches
• Shipping Weight: 1.6 pounds (View shipping rates and policies)
• Average Customer Review: 4.0 out of 5 stars  See all reviews (3 customer reviews)
• Amazon Best Sellers Rank: #2,241,948 in Books (See Top 100 in Books)

Customer Reviews

Most Helpful Customer Reviews

9 of 9 people found the following review helpful:

3.0 out of 5 stars Worth buying a used copy., June 14, 2005

By 

Jason T (Canada) - See all my reviews

This review is from: Computability: Computable Functions, Logic, and the Foundations of Mathematics, with Computability: A Timeline (Paperback)

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.

5.0 out of 5 stars Invaluable Sections on Primitive Recursive Functions, November 27, 2011

By 

Customer (Baltimore) - See all my reviews

This review is from: Computability : Computable Functions Logic and the Foundations of Math (Wadsworth&Brooks/Cole Mathematics Series) (Hardcover)

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.

2 of 6 people found the following review helpful:

4.0 out of 5 stars when critical thinking, computer and math meet at one, April 14, 2001

By 

tee (ny) - See all my reviews

This review is from: Computability: Computable Functions, Logic, and the Foundations of Mathematics, with Computability: A Timeline (Paperback)

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.