Wyd. I

Roman Murawski
Recursive Functions and Metamathematics. Problems of Completness and Decidability, Gödel's Theorems
Kluwer Academic Publishers, Dordrecht/Boston/London 1999
404 stron

Contents


Preface
Introduction

1. Recursive Functions
    1.1. Computable Functions
    1.2. Recursive Functions
    1.3. Markov Algorithms nad Turing Machines
    1.4. Primitive and Elementary Recursive Functions
    1.5. Arithemetical Hierarchy
    1.6. Church's Thesis
    1.7. Historical Remarks

2. Gödel's IncompletenessTheorems
    2.1. Arithmetic of Natural Numbers
    2.2. Representability in Peano Arithmetic
    2.3. Arithmetization of Syntax
    2.4. Gödel's Theorems
    2.5. Paris-Harrington and Paris-Kirby Theorems
    2.6. Satisfaction and Consistency
    2.7. Historical Remarks

3. Decidability Theory
    3.1. Basic notions and theorems
    3.2. Decidable Theories
    3.3. Undecidable Theories
    3.4. Historical Remarks

4. Philosophical Comments
    4.1. Direct Consequences of Gödel's Results
    4.2. Gödel's Theorems vs. Hilbert's Program
    4.3. Generalized Hilbert's Program
    4.4. Relativized Hilbert's Program vs. Reverse Mathematics
    4.5. Hilbert's Tenth Problem
    4.6. Gödel's Theorems and Computer Science
    4.7. Gödel's Theorems and General Philosophy
    4.8. Conclusions

Bibliography
List of Symbols
Index