J.I. Zucker and L. Pretorius (1993): Introduction to computability theory, South African Computer Journal, 9, April 1993, 3-30. [text.ps]

Abstract. These are notes for a short introductory course on Computability Theory (or recursive function theory). The basic notion of computability is defined in terms of a simple imperative programming language.

1. Introduction
2. Mathematical Preliminaries
3. Programs which Compute Functions
4. G-Computable Functions
5. Primitive Recursiveness
6. Some Techniques for Defining PR Functions
7. PR Codings of Finite Sequences of Numbers
8. The Church-Turing Thesis
9. The Halting Problem; The Universal Function Theorem
10. Recursive Enumerability
11. Enumerability of Total Computable Functions
12. mu-Primitive Recursive Functions
13. `loop' Programs
14. `while' Programs
15. The S-n-m Theorem
16. The Recursion Theorem
17. Rice's Theorem