Author | Kfoury, A. J. author |
---|---|
Title | A Programming Approach to Computability [electronic resource] / by A. J. Kfoury, Robert N. Moll, Michael A. Arbib |
Imprint | New York, NY : Springer New York, 1982 |
Connect to | http://dx.doi.org/10.1007/978-1-4612-5749-3 |
Descript | VIII, 251 p. online resource |
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