Synopses & Reviews
Computability and Logic has become a classic because of its accessibility to students without a mathematical background and because it covers not simply the staple topics of an intermediate logic course, such as Godel 's incompleteness theorems, but also a large number of optional topics, from Turing 's theory of computability to Ramsey 's theorem. Including a selection of exercises, adjusted for this edition, at the end of each chapter, it offers a new and simpler treatment of the representability of recursive functions, a traditional stumbling block for students on the way to the Godel incompleteness theorems.
Synopsis
Now in its fourth edition, this book has become a classic because it covers not simply the staple topics of intermediate logic courses but also a large number of other topics. John Burgess has enhanced the book by adding problems at the end of each chapter and by rewriting chapters.
Synopsis
Computability and Logic has become a classic because of its accessibility to students without a mathematical background and because it covers not simply the staple topics of an intermediate logic course, such as Godel's incompleteness theorems, but also a large number of optional topics, from Turing's theory of computability to Ramsey's theorem. Including a selection of exercises, adjusted for this edition, at the end of each chapter, it offers a new and simpler treatment of the representability of recursive functions, a traditional stumbling block for students on the way to the Godel incompleteness theorems.
Synopsis
Now in its fourth edition, this book on logic has been enhanced and rewritten.
Synopsis
Computability and Logic is a classic because of its accessibility to students without a mathematical background.
Table of Contents
Part I. Computability Theory: 1. Enumerability; 2. Diagonalization; 3. Turing computability; 4. Uncomputability; 5. Abacus computability; 6. Recursive functions; 7. Recursive sets and relations; 8. Equivalent definitions of computability; Part II. Basic Metalogic: 9. A precis of first-order logic: syntax; 10. A precis of first-order logic: semantics; 11. The undecidability of first-order logic; 12. Models; 13. The existence of models; 14. Proofs and completeness; 15. Arithmetization; 16. Representability of recursive functions; 17. Indefinability, undecidability, incompleteness; 18. The unprovability of consistency; Part III. Further Topics: 19. Normal forms; 20. The Craig interpolation theorem; 21. Monadic and dyadic logic; 22. Second-order logic; 23. Arithmetical definability; 24. Decidability of arithmetic without multiplication; 25. Non-standard models; 26. Ramsey's theorem; 27. Modal logic and provability.