Computability Theory

General Recursive Functions 47

functions by the use of composition and primitive recursion. We can, with some effort,

code such trees by natural numbers. The “universal” function

9(x, y) =



f (x) if y codes a tree for a one-place primitive recursive function f

0 otherwise

is effectively calculable (and total). But 9(x, x)+1 and 1−

·

9(x, x) are total effectively

calculable functions that cannot be primitive recursive. (See also page 19.)

2.2 Search Operation

We obtain the class of general recursive partial functions by allowing functions to be

built up by use of search (in addition to composition and primitive recursion). Search

(also called minimalization) ...