## The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable FunctionsAn anthology of fundamental papers on undecidability and unsolvability, this classic reference opens with Gödel's landmark 1931 paper demonstrating that systems of logic cannot admit proofs of all true assertions of arithmetic. Subsequent papers by Gödel, Church, Turing, and Post single out the class of recursive functions as computable by finite algorithms. 1965 edition. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

On Formally Undecidable Propositions of | 4 |

On Undecidable Propositions of Formal | 39 |

On Intuitionistic Arithmetic and Number Theory | 75 |

On the Length of Proofs | 82 |

An Unsolvable Problem of Elementary Number Theory | 88 |

A Note on the Entscheidungsproblem | 108 |

Systems of Logic Based on Ordinals | 154 |

J B ROSSER | 222 |

Extensions of Some Theorems of Giidel and Church | 230 |

General Recursive Functions of Natural Numbers | 236 |

Recursive Predicates and Quantifiers | 254 |

Finite Combinatory Processes Formulation I | 288 |

Recursively Enumerable Sets of Positive Integers | 304 |

Absolutely Unsolvable Problems and Relatively | 338 |

407 | |

### Other editions - View all

### Common terms and phrases

Alonzo Church arbitrary argument axioms C-K ordinal formula canonical form Church complete conﬁguration computable numbers concept consistency consistency proof constructive conv convertible corresponding decision problem deﬁned deﬁnition determine diﬁerent effectively calculable eﬁectively elementary Entscheidungsproblem enunciation equations equivalent exists expression ﬁgure ﬁnd finite ﬁnite number ﬁnite sequence ﬁniteness problem ﬁrst ﬁxed footnote formal free variables Giidel Godel representation Hence induction intuitive Kleene Lemma m-conﬁguration mathematical means metamathematical method modiﬁcation n-th natural numbers normal form normal system notes number theory number-theoretic theorems obtained occur operations ordinal logic paper partial recursive positive integers premise primitive assertion primitive letters primitive recursive function Principia Mathematica production proof provable formulas prove quantiﬁers recursive relation recursively enumerable set reducibility replace result rules satisﬁes set of positive speciﬁc square subset substitution suppose symbolic logic theorem tion Turing undecidable propositions unsolvability valid well-formed formulas