Introduction to Computability Theory

Author: Sipser
Publisher:
Publish Date: 2002-02-01
Features: This book — by a noted authority and educator in the field — presents computer science theory from a uniquely intuitive, “big picture” perspective. The author grounds his clear and interesting study on broad mathematical principles, not low-level technical details: proofs are presented with a “proof idea” component that reveals the concept underlying the mathematical formalism. Similarly, algorithms are presented using prose rather than pseudocode to focus attention on the algorithms themselves, rather than on specific models. Formerly published in a Preliminary Edition, this First Edition features additional chapters on space complexity (Chapter 8), provable intractability (Chapter 9), and advanced topics in computability theory (Chapter 10). For further information, see the Worldwide Website for the book at: http://www-math.mit.edu/sipser/book.html