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.
Contents
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