Fundamentals of computability

The basic theory of the partial computable functions, built on the enumeration Φₑ given by Kleene's normal form: approximation by stages, the universal function, the SMN theorem and acceptable numberings, the undecidability of the halting problem and many-one reductions, computably enumerable sets and the m-completeness of the halting set, Kleene's fixed point theorem, and the theorems of Rice and Rice–Shapiro.

Contents

1. 1

   Programs as numbers

   The enumeration Φₑ of the partial computable functions, its approximation by stages, and computable sets and relations.

   1. 1.1 The enumeration
   2. 1.2 Approximation by stages
   3. 1.3 Computable sets and relations
   4. 1.4 Uniformity
   5. 1.5 Exercises
   6. 1.6 Notes and references
   35 min
2. 2

   The universal function and the SMN theorem

   The universal partial computable function, the SMN theorem and its use with parameters, the padding lemma, and acceptable numberings.

   1. 2.1 The universal function
   2. 2.2 The SMN theorem
   3. 2.3 The padding lemma
   4. 2.4 Acceptable numberings
   5. 2.5 Exercises
   6. 2.6 Notes and references
   40 min
3. 3

   The halting problem

   Undecidability of the halting problem; many-one reductions; undecidability of totality and of halting on a fixed input.

   1. 3.1 The halting set
   2. 3.2 Many-one reductions
   3. 3.3 Undecidable problems in mathematics
   4. 3.4 Exercises
   5. 3.5 Notes and references
   35 min
4. 4

   Computably enumerable sets

   Characterizations of the computably enumerable sets, closure properties, the graph and selection theorems, and the m-completeness of the halting set.

   1. 4.1 Definition and characterizations
   2. 4.2 Closure properties
   3. 4.3 The graph and selection theorems
   4. 4.4 Computable and c.e. sets
   5. 4.5 The halting set is m-complete
   6. 4.6 Exercises
   7. 4.7 Notes and references
   45 min
5. 5

   Kleene's fixed point theorem

   Every total computable transformation of indices has a fixed point up to the function computed; the version with parameters; self-referential programs and applications.

   1. 5.1 The theorem
   2. 5.2 Fixed points with parameters
   3. 5.3 Applications
   4. 5.4 Exercises
   5. 5.5 Notes and references
   40 min
6. 6

   Rice's theorem

   Non-trivial index sets are not computable; the halting set reduces to them; c.e. index sets are monotone and determined by finite information.

   1. 6.1 Index sets
   2. 6.2 Rice's theorem
   3. 6.3 Which index sets are c.e.
   4. 6.4 Consequences
   5. 6.5 Exercises
   6. 6.6 Notes and references
   40 min