| |
| |
| Preface | |
| |
| |
| Prologue. Prerequisites and notation | |
| |
| |
| |
| Sets | |
| |
| |
| |
| Functions | |
| |
| |
| |
| Relations and predicates | |
| |
| |
| |
| Logical notation | |
| |
| |
| |
| References | |
| |
| |
| |
| Computable functions | |
| |
| |
| |
| Algorithms, or effective procedures | |
| |
| |
| |
| The unlimited register machine | |
| |
| |
| |
| URM-computable functions | |
| |
| |
| |
| Decidable predicates and problems | |
| |
| |
| |
| Computability on other domains | |
| |
| |
| |
| Generating computable functions | |
| |
| |
| |
| The basic functions | |
| |
| |
| |
| Joining programs together | |
| |
| |
| |
| Substitution | |
| |
| |
| |
| Recursion | |
| |
| |
| |
| Minimalisation | |
| |
| |
| |
| Other approaches to computability: Church's thesis | |
| |
| |
| |
| Other approaches to computability | |
| |
| |
| |
| Partial recursive functions (Godel-Kleene) | |
| |
| |
| |
| A digression: the primitive recursive functions | |
| |
| |
| |
| Turing-computability | |
| |
| |
| |
| Symbol manipulation systems of Post and Markov | |
| |
| |
| |
| Computability on domains other than N | |
| |
| |
| |
| Church's thesis | |
| |
| |
| |
| Numbering computable functions | |
| |
| |
| |
| Numbering programs | |
| |
| |
| |
| Numbering computable functions | |
| |
| |
| |
| Discussion: the diagonal method | |
| |
| |
| |
| The s-m-n theorem | |
| |
| |
| |
| Universal programs | |
| |
| |
| |
| Universal functions and universal programs | |
| |
| |
| |
| Two applications of the universal program | |
| |
| |
| |
| Effective operations on computable functions | |
| |
| |
| |
| Computability of the function [sigma subscript n] | |
| |
| |
| |
| Decidability, undecidability and partial decidability | |
| |
| |
| |
| Undecidable problems in computability | |
| |
| |
| |
| The word problem for groups | |
| |
| |
| |
| Diophantine equations | |
| |
| |
| |
| Sturm's algorithm | |
| |
| |
| |
| Mathematical logic | |
| |
| |
| |
| Partially decidable predicates | |
| |
| |
| |
| Recursive and recursively enumerable sets | |
| |
| |
| |
| Recursive sets | |
| |
| |
| |
| Recursively enumerable sets | |
| |
| |
| |
| Productive and creative sets | |
| |
| |
| |
| Simple sets | |
| |
| |
| |
| Arithmetic and Godel's incompleteness theorem | |
| |
| |
| |
| Formal arithmetic | |
| |
| |
| |
| Incompleteness | |
| |
| |
| |
| Godel's incompleteness theorem | |
| |
| |
| |
| Undecidability | |
| |
| |
| |
| Reducibility and degrees | |
| |
| |
| |
| Many-one reducibility | |
| |
| |
| |
| Degrees | |
| |
| |
| |
| m-complete r.e. sets | |
| |
| |
| |
| Relative computability | |
| |
| |
| |
| Turing reducibility and Turing degrees | |
| |
| |
| |
| Effective operations on partial functions | |
| |
| |
| |
| Recursive operators | |
| |
| |
| |
| Effective operations on computable functions | |
| |
| |
| |
| The first Recursion theorem | |
| |
| |
| |
| An application to the semantics of programming languages | |
| |
| |
| |
| The second Recursion theorem | |
| |
| |
| |
| The second Recursion theorem | |
| |
| |
| |
| Discussion | |
| |
| |
| |
| Myhill's theorem | |
| |
| |
| |
| Complexity of computation | |
| |
| |
| |
| Complexity and complexity measures | |
| |
| |
| |
| The Speed-up theorem | |
| |
| |
| |
| Complexity classes | |
| |
| |
| |
| The elementary functions | |
| |
| |
| |
| Further study | |
| |
| |
| Bibliography | |
| |
| |
| Index of notation | |
| |
| |
| Subject Index | |