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 (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 (x, x)+1 and 1- (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) corresponds to an unbounded µ-operator. For a (k + 1)- place partial function g, we define the least number y such that both g(x, y) = 0 and for all t less than y, the value g(x, t) is defined µy[g(x, y) = 0] = and is nonzero, if there is any such y undefined, if there is no such y.