You are here

The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions

Martin Davis
Dover Publications
Publication Date: 
Number of Pages: 
BLL Rating: 

The Basic Library List Committee strongly recommends this book for acquisition by undergraduate mathematics libraries.

[Reviewed by
Fernando Q. Gouvêa
, on

This is a Dover reprint of a book originally published in 1965. The book collects several fundamental articles on undecidability (see the table of contents for the list). An extended review appeared in the Journal of Symbolic Logic and can be accessed through JSTOR.

The only thing to say, really, is that this is a fundamental resource for anyone interested in seeing the most important papers on undecidability and related issues in logic. Most libraries probably already have a copy. (If they don't, shame on them!) The Dover edition makes it accessible to everyone else.

Fernando Q. Gouvêa is the editor of MAA Reviews.


Kurt G”del: On Formally Undecidable Propositions of the Principia Mathematica and Related Systems; On Undecidable Propositions of Formal Mathematical Systems, On Intuitionistic Arithmetic and Number Theory, On the Length of Proofs, Remarks Before the Princeton Bicentennial Conference of Problems in Mathematics

Alonzo Church: An Unsolvable Problem of Elementary Number Theory, A Note on the Entscheidungsproblem

Alan M. Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Systems of Logic Based on Ordinals

J. B. Rosser: An Informal Exposition of Proofs of G”del's Theorem and Church's Theorem, Extensions of Some Theorems of G”del and Church

Stephen C. Kleene: General Recursive Functions of Natural Numbers, Recursive Predicates and Quantifiers

Emil Post: Finite Combinatory Processes, Formulation I; Recursive Unsolvability of a Problem of Thue, Recursively Enumerable Sets of Positive Integers and Their Decision Problems, Absolutely Unsolvable Problems and Relatively Undecidable Propositions-Account of an Anticipation.