Alert Me

Want us to e-mail you when this item becomes available?

Sorry, this item is not available in
Image not available for
Colour:
Image not available

 
Tell the Publisher!
Id like to read this book on Kindle

Don't have a Kindle? Get your Kindle here, or download a FREE Kindle Reading App.

Computability Theory, Second Edition (Chapman Hall/CRC Mathematics Series) [Hardcover]

S. Barry Cooper
5.0 out of 5 stars  See all reviews (1 customer review)

Sign up to be notified when this item becomes available.


Formats

Amazon Price New from Used from
Hardcover 60.79  
Hardcover, 5 Jan 2016 --  

Book Description

5 Jan 2016 1439838437 978-1439838433 2

Designed for advanced undergraduate or beginning graduate students, this book provides a complete introduction to computability theory. This second edition includes new material on hyperarithmetical and Borel sets as well as more material on computability of structures, Pi-0-1 classes, and computability in science. It features an expanded treatment of complexity of computations and updated future directions in computability. In addition, the section on randomness is now a separate chapter. The author also discusses advanced topics in greater depth, including Post’s problem, forcing and category, applications of determinacy, and the computability of theories.


Customers Who Viewed This Item Also Viewed


Product details

  • Hardcover: 506 pages
  • Publisher: Chapman and Hall/CRC; 2 edition (5 Jan 2016)
  • Language: English
  • ISBN-10: 1439838437
  • ISBN-13: 978-1439838433
  • Average Customer Review: 5.0 out of 5 stars  See all reviews (1 customer review)
  • Amazon Bestsellers Rank: 3,264,776 in Books (See Top 100 in Books)
  • See Complete Table of Contents

More About the Authors

Discover books, learn about writers, and more.

Product Description

Review

"A very nice volume indeed. Although primarily a textbook, it lives up to the author's aim to have 'plenty here to interest and inform everyone, from the beginner to the expert.' Cooper writes in an informal style, emphasizing the ideas underlying the techniques. All the standard topics and classic results are here. Students will find useful pointers to the literature and an abundance of exercises woven into the text." - Zentralblatt MATH, 1041 "[It] provides not only a reference repository of well-crafted proofs or proof-outlines for a large number of basic and beyond-basic facts in several areas of computability theory, but can also serve well as the textual basis for a course on the subject" - Mathematical Reviews, 2005h --This text refers to an alternate Hardcover edition.

About the Author

S. Barry Cooper is a professor in the Department of Pure Mathematics at the University of Leeds, UK.


Inside This Book (Learn More)
Browse and search another edition of this book.
First Sentence
It is only in the last century that computability became both a driving force in our daily lives and a concept one could talk about with any sort of precision. Read the first page
Explore More
Concordance
Browse Sample Pages
Front Cover | Copyright | Table of Contents | Excerpt | Index | Back Cover
Search inside this book:

Sell a Digital Version of This Book in the Kindle Store

If you are a publisher or author and hold the digital rights to a book, you can sell a digital version of it in our Kindle Store. Learn more

Customer Reviews

4 star
0
3 star
0
2 star
0
1 star
0
5.0 out of 5 stars
5.0 out of 5 stars
This item has not been released yet and is not eligible to be reviewed. Reviews shown are from other formats of this item.
Most Helpful Customer Reviews
10 of 10 people found the following review helpful
Format:Hardcover
This book is an introduction to computability theory. It is organized in three parts, starting with basic computability theory and moving up to advanced topics, some of which cannot be found in textbooks today.
In the first part the reader is introduced to basic concepts and results of computability like models of computation, coding, universal machines, enumerability, fixed point theorem. The author also discusses the historical context in which various notions appeared (not only in this part but throughout the book) like Hilbert's programme and makes connections with logic (language, theories, Peano Arithmetic, Godel incompleteness theorem). Computability and Unsolvability in the real world is also discussed, along with the search for natural examples of incomputable sets, a topic which is currently more interesting than ever. Most of the content of Part I can be found in other good text books (like Odiffreddi's or Roger's) but the way it is presented is unique: the arguments and proofs are given in an informal yet accurate way (according to the modern mode for doing computability) and the whole arrangement is very schematic, often assisted by diagrams, figures, tables and boxes. This is especially helpful in a text book in computability theory, a subject that makes understanding rely so much on intuition and visual images.
The second part is concerned with oracle computation (a core part of computability), Turing degrees, Enumeration degrees, and many other related and complementary topics like polynomial bounds, P=?NP, the Scott model for Lamda calculus and others. The author here tries to give a general idea of the subject by discussing interesting topics (like the ones mentioned above) which don¡t necessarily lie on the core of computability theory.
Read more ›
Comment | 
Was this review helpful to you?
Most Helpful Customer Reviews on Amazon.com (beta)
Amazon.com: 4.5 out of 5 stars  4 reviews
12 of 12 people found the following review helpful
5.0 out of 5 stars A Unique Introduction to Computability 28 Mar 2004
By G Barmpalias - Published on Amazon.com
Format:Hardcover
This book is an introduction to computability theory. It is organized in three parts, starting with basic computability theory and moving up to advanced topics, some of which cannot be found in textbooks today.
In the first part the reader is introduced to basic concepts and results of computability like models of computation, coding, universal machines, enumerability, fixed point theorem. The author also discusses the historical context in which various notions appeared (not only in this part but throughout the book) like Hilbert's programme and makes connections with logic (language, theories, Peano Arithmetic, Godel incompleteness theorem). Computability and Unsolvability in the real world is also discussed, along with the search for natural examples of incomputable sets, a topic which is currently more interesting than ever. Most of the content of Part I can be found in other good text books (like Odiffreddi's or Roger's) but the way it is presented is unique: the arguments and proofs are given in an informal yet accurate way (according to the modern mode for doing computability) and the whole arrangement is very schematic, often assisted by diagrams, figures, tables and boxes. This is especially helpful in a text book in computability theory, a subject that makes understanding rely so much on intuition and visual images.
The second part is concerned with oracle computation (a core part of computability), Turing degrees, Enumeration degrees, and many other related and complementary topics like polynomial bounds, P=?NP, the Scott model for Lamda calculus and others. The author here tries to give a general idea of the subject by discussing interesting topics (like the ones mentioned above) which don¡t necessarily lie on the core of computability theory. This is pretty much the spirit of the whole book: to give the non-expert reader access to the most exciting (and sometimes apparently inaccessible at this level) topics in the subject and motivate him/her to further study towards the direction that looks and feels more appealing.
The third and last part discusses advanced topics like approximation constructions, priority injury, Sack¡s theorems, maximal sets, even the 0¡¡¡-priority method. This is the longest part of the book and the choice its contents (along with the approachable and attractive way they are presented despite their advanced nature) is just another feature which makes this book unique. The construction of maximal sets is remarkable since it uses a tree argument (with infinitary activity of the nodes but without injury) thus making it more intuitive and understandable, in contrast to the usual e-maximal state method which was introduced by the original paper (with the first proof that maximal sets exist) and followed by most text books I am aware of, without many changes. The proof of the existence of a noncuppable c.e. noncomputable degree also deserves to be mentioned as it is not something that one finds in text books. Also, it is different than the original pinball argument one finds in papers (with the restraints tending to infinity, often mentioned as an example of this bizarre feature) as it is done on a tree. Finally, computability in mathematics (structures, combinatorics, Analysis) and science is discussed along with randomness and computable models.
In the end of the book there is a bibliography for further reading. This is very personal (and, of course, by no means complete) but very helpful as it ranges over a wide range of computability related topics and it matches the spirit of the book very well.
To sum up, this introduction achieves the aims set by the author (a leading specialist in computability) in the preface and the epilogue: it deals with the subject in a very wide context, discusses it from its most hardcore features (priority, forcing) to its most distant echoes (incomputability in science) and most importantly it relates these two, showing how technical work is motivated and inspired by more general concerns. It is intended as a text book for undergraduate and early postgraduate students but is also suitable for any non-specialist. The features discussed above along with the modern style of presentation make the subject look as attractive as it really is and the book unique over the other computability text books available today. I wish this book had been in my library when I first started reading computability.
8 of 9 people found the following review helpful
5.0 out of 5 stars Clear explanations and fresh approach that enables real understanding 22 July 2005
By Dexter - Published on Amazon.com
Format:Hardcover
This is a lovely book, which gives a fresh and invigorating account of current developments in computability theory. Personally, I don't feel it can helpfully be compared to Cutland's computability text, as though that book supplies enough background for some undergraduate introductory courses in computability theory, it doesn't reach beyond that level. Cooper sensibly avoids using the same approach as Cutland for the area of over-lap -there would be little point duplicating an existing, in-print work- instead, he has in the early chapters given an intuitive approach to those topics which helps the reader understand what is going on under the morass of symbols which so often obscure rather than promote comprehension. Nor can much useful comparison be drawn with Hartley Roger's classic text, as the main bulk of Cooper's book is concerned with material which post-dates Hartley Rogers.

Computability theory has a fearsome reputation for incomprehensibility and difficulty, even amongst logicians. When, many years ago, I attended my first logic conference and was asked my area of study by a senior logician, I was a little disconcerted by his response of, `Good luck - you'll need it,' to my reply of `computability theory'. Conversations with Cooper proved invaluable, in that his understanding is holistic: he understands what is going on, he understands the big picture. Better, he can draw pictures, both literal and figurative, to explain to others how particular proofs work.

That is what you get with this book: a minimum of technical jargon and deceptively clear explanations of many modern developments in computability theory. It's a great book for anyone beginning research in the area, or for an undergraduate who wants a deeper understanding to underpin their coursework, or, indeed, for researchers in other areas wanting to find out more about modern computability theory and its relevance to their work.
17 of 23 people found the following review helpful
3.0 out of 5 stars Not recommended as a starting point 28 April 2005
By Todd Ebert - Published on Amazon.com
Format:Hardcover|Verified Purchase
The book is divided into roughly three parts: an introduction to computability theory, followed by a more advanced introduction to the theory of degrees of unsolvability and decidable theories, and finally some newer material on computation and structure.

As for the introduction to computability, let me just say that I'm thankful to have already been introduced to computability via Nigel Cutland's excellent and concise text "Computability : An Introduction to Recursive Function Theory". Unlike this book, Cutland does not skip any of the important details (or have the reader fill them in with exercises). For example, Cutland acutally provides rigorous but intuitive proofs of the s-m-n Theorem and the existence of universal computers. Contrast this with how this book leaves the general theorem as an exercise, follwed by the sentence "But let us get back to more important matters". What I found remarkable when reading Cutland is that because of the s-m-n (which is trivialized in this book), Cutland rarely invoked "Church's Thesis" when proving the computability of a function or relation, where as Church's Thesis gets invoked in this book for matters as trivial as showing that computable relations are closed under the various logical operations. In short, by reading Chapters 1-11 of Cutland, the reader can easily (and thankfully) skip the first 8 or 9 Chapters of this book, while receiving a more complete thoughtful treatment. Yet another reason to read Cutland is his excellent introductions to both recursion theorems, where as in this book the fixed-point theorem receives one page in an awkward location in the book.

As for the remaining parts, I made an honest attempt to read them in hope that the author's informal style of writing might shed light on some of the more complex results about degrees of unsolvability. And to his credit, I found the Chapter on priority and immunity more understandable than say what is presented in Hartley Rogers's classic "Theory of Recursive Functions and Effective Computability".

The following editorial note originally enticed me to buy the book: "The final chapter explores a variety of computability applications to mathematics and science". Unfortunately this chapter seemed overly brief, and left me looking for better references. In short, reading this book did little to enhance my viewpoint towards computability theory. I'm glad the author is excited about the subject and wants to make the material seem more appealing by trying to provide more intuition about the subject matter, but the way that it was carried out simply did not work for me. For the casual reader I recommend Dewdney's "Turing Omnibus", and for the serious reader, the books by Cutland, Oddifredi, and Rogers in that order. I often hear or read the claim that Rogers's book is "outdated", but it still makes for an amazing read, and is in my opinion still the best graduate text on the subject. Note that most of the results in this book can be found in Rogers. And for the programming oriented reader, the book by Neil Jones "Computability and Complexity" ought not to be missed.
5.0 out of 5 stars Accessible Intermediate Textbook 23 Dec 2011
By Michael - Published on Amazon.com
Format:Hardcover
The first part (about 100 pages) introduces the basics of computability theory including some logic (Gödel's theorem + computability of theories). For me the presentation was a bit too informal (often invoking Church's thesis, only a few very simple problems are actually encoded in Turing machines/-recursion, proofs of basic theorems such as the equivalence of the two models or the non-primitive-recursiveness of the Ackermann function are not even sketched).

The second part and the first chapter of the third part deal with reducibilities and corresponding hierarchies and degree structures. The treatment is both intuitively accessible and rather thorough. Besides the standard Turing degrees/arithmetical hierarchy, it includes topics such as enumeration reducibility, the Medvedev lattice and finally an introduction to immunity and the priority method, which I found very accessible. Much more material on these topics can be found in classics like Rogers, but Cooper book provides a very good introduction even to quite complicated technical areas.

The third part first gives an overview of applications of forcing, topology and determinacy to computability theory. The treatment is not very deep (many results are left unproven and only simple problems are given as exercises), but there seems to be no comparable textbook treatment of these topics (which partly post-date Rogers), in particular not in textbooks at this level. Thus, I found it a very useful starting point. The last two chapters deal with the computability of theories and with the relation between computability and other mathematical structures. The last chapter was again somewhat shallow, but very interesting from a broader mathematical perspective, which Cooper also emphasizes in other parts.

In general, the book is maybe not the ideal first introduction, but a very accessible intermediate texbook which guides the reader to more advanced topics which are of interest to current research in the field.
Were these reviews helpful?   Let us know
Search Customer Reviews
Only search this product's reviews

Customer Discussions

This product's forum
Discussion Replies Latest Post
No discussions yet

Ask questions, Share opinions, Gain insight
Start a new discussion
Topic:
First post:
Prompts for sign-in
 

Search Customer Discussions
Search all Amazon discussions
   


Look for similar items by category


Feedback