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
addition apply arguments arithmetic assigns atomic axioms begin blank block called chapter code number complete computable condition conjunction consequence consider consistent constant contains correct deducible defined definition denotation derivation disjunction domain effectively elements entry enumerable equivalent Example exists extension fact Figure finite follows formal formula function symbols give given going halt hence holds identity implies induction infinite instance interpretation involving isomorphic language least Lemma less logic matter means natural numbers nonstandard Note notion obtained occur operations pairs positive integers preceding predicate present primitive recursive problem proof Proposition provable prove quantification recursive function relation remainder represented result rules satisfiable semirecursive sequence set of sentences Show specify standard step strokes subset Suppose tape theorem theory true truth Turing machine variables write 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.