Computability and Logic
Cambridge University Press, Sep 17, 2007 - Computers - 350 pages
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.
What people are saying - Write a review
We haven't found any reviews in the usual places.
Other editions - View all
arguments arithmetically definable atomic formulas atomic sentence axioms blank block called chapter Church’s thesis closed term code number compactness theorem conjunction consider consistent constant contains Corollary deducible definition denotation derivation diagonal lemma disjunction domain effectively computable elements entry Example existential quantification finite set finite subset first-order first-order logic flow chart follows formal function f function symbols given hence identity implies infinite isomorphic L¨owenheim–Skolem theorem language of arithmetic leftmost Lemma monadic logic natural numbers negation nonenumerable nonlogical symbols nonstandard model normal form notation notion obtained one-place pairs positive integers primitive recursive function Proposition provable prove rational numbers real numbers recursive set recursive total function result right number rudimentary formula satisfiable scanning second-order logic semirecursive set of sentences sets of natural Show Skolem standard interpretation strokes subformula Suppose tape theory total function Turing computable Turing machine universal quantification variables write xB(x xF(x zero
Page 347 - The special aim of the present edition has been to increase the pedagogical usefulness of the book by adding a selection of problems at the end of each chapter, and by making chapters more independent of each other, so as to increase the range of options available to the instructor or reader as to what to cover and what to defer.