Computability Theory

General Recursive Functions 49

g (so the right-hand side will be undefined) and not in Q (so the left-hand side will

be 0). Instead, we can first use primitive recursion to construct the function

G(Ex, 0) = 0

G(Ex, y +1) = g(Ex),

which is like g except that it has a “on–off switch.” Then we have the equation

g

Q

(Ex) = G(Ex, C

Q

(Ex)).

showing that g

Q

is a general recursive partial function.

Now if we also have another k-place general recursive partial function f, and we

define

h(Ex) =



f (Ex) if Q(Ex)

g(Ex) if not Q(Ex)

then h is a general recursive partial function because h(Ex) = f

Q

(Ex) +g

Q

(Ex).

24A. Assume that g is a general recursive partial (k + 2)-place function, ...