A Programming Approach to Computability

1 Introduction. - 1. 1 Partial Functions and Algorithms. - 1. 2 An Invitation to Computability Theory. - 1. 3 Diagonalization and the Halting Problem. - 2 The Syntax and Semantics of while-Programs. - 2. 1 The Language of while-Programs. - 2. 2 Macro Statements. - 2. 3 The Computable Functions. - 3 Enumeration and Universality of the Computable Functions. - 3. 1 The Effective Enumeration of while-Programs. - 3. 2 Universal Functions and Interpreters. - 3. 3 String-Processing Functions. - 3. 4 Pairing Functions. - 4 Techniques of Elementary Computability Theory. - 4. 1 Algorithmic Specifications. - 4. 2 The s-m-n Theorem. - 4. 3 Undecidable Problems. - 5 Program Methodology. - 5. 1 An Invitation to Denotational Semantics. - 5. 2 Recursive Programs 110 5. 3* Proof Rules for Program Properties. - 6 The Recursion Theorem and Properties of Enumerations. - 6. 1 The Recursion Theorem. - 6. 2 Model-Independent Properties of Enumerations. - 7 Computable Properties of Sets (Part 1). - 7. 1 Recursive and Recursively Enumerable Sets. - 7. 2 Indexing the Recursively Enumerable Sets. - 7. 3 Gödel's Incompleteness Theorem. - 8 Computable Properties of Sets (Part 2). - 8. 1 Rice's Theorem and Related Results. - 8. 2 A Classification of Sets. - 9 Alternative Approaches to Computability. - 9. 1 The Turing Characterization. - 9. 2 The Kleene Characterization. - 9. 3 Symbol-Manipulation Systems and Formal Languages. - References. - Notation Index. - Author Index. Language: English