## 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 Gödel 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 | 303 |

Absolutely Unsolvable Problems and Relatively | 338 |

407 | |

### Other editions - View all

### Common terms and phrases

according allow appears application arbitrary argument assertion assumed axioms basis called canonical form Church complete computable concept condition consider consistency constructive contains conv convertible correct corresponding defined definition described determine distinct elements enunciation equations equivalent exists expression fact finite formal free variables give given Gödel Hence holds induction infinite introduce involving Kleene least letters logic machine Math mathematical means method natural numbers normal form normal system notes obtained occur operations ordinal formula ordinal logic particular positive integers possible predicate premise present primitive recursive prints problem production proof proposition provable prove question rank recursive function recursively enumerable set reducibility referred relation replace represents respectively result rules sense sequence simple square substitution suppose symbolic logic symbols theorem theory tion true Turing unsolvability valid variables