Computability Theory

2 General Recursive Functions

In the preceding chapter, we saw an overview of several possible formalizations of the

concept of effective calculability. In this chapter, we focus on one of those: primitive

recursiveness and search, which give us the class of general recursive partial functions.

In particular, we develop tools for showing that certain functions are in this class.

These tools will be used in Chapter 3, where we study computability by register-

machine programs.

2.1 Primitive Recursive Functions

The primitive recursive functions have been defined in the preceding chapter as the

functions on N that can be built up from zero functions

f (x

1

, . . . , x

k

) = 0,

the successor function

S(x) = x +1,

and the projection functions

I

k

n

(x

1

, . . . , x

k