Chapter I - Recursive Functions

Summary

This chapter is introductory in nature. We summarize material which is normally covered in a first course in Recursion Theory and which will be assumed within this book. Recursive and partial recursive functions are introduced and Church's Thesis is discussed. Relative recursion is then defined, and the Enumeration and Recursion Theorems are stated without proof. The reader familiar with this material should quickly skim through the chapter in order to become familiar with our notation. We refer the reader to the first five chapters of Cutland [1980] for a careful rigorous treatment of the material introduced in this chapter.

The Recursive and Partial Recursive Functions

The search for algorithms has pervaded Mathematics throughout its history. It was not until this century, however, that rigorous mathematical definitions of algorithm were discovered, giving rise to the class of partial recursive functions.

This book deals with a classification of total functions of the form in terms of the information required to compute such a function. The rules for carrying out such computations are algorithms (partial functions for some) with access to information possessed by oracles. The easiest functions to compute are those for which no oracular information is required, the recursive functions. Thus we begin by defining the (total) recursive functions, and then indicate how to modify this definition to obtain the class of partial recursive functions. The section concludes with discussions of Church's Thesis and of general spaces on which recursive functions can be defined.

Definition. Let is the least y such that if such a y exists, and is undefined otherwise. Henceforth, we will refer to as the least number operator.

Definition. The class R of recursive functions is the smallest class of functions with domain N^k for some and range N which contains:

1. (i) The zero function: Z(x) = 0 for all;

2. (ii) The successor function: S(x) = x + 1 for all;

3. (iii) The projection functions: for all and,