CSC 341: March 7, 2007
From CSWiki
Instructor's notes for the class session
The next surprise about partial recursive functions is that the useful, seemingly natural predicate defined? is not partial recursive. This binary predicate takes the encoding for a partial recursive function as its first input, the encoding for an argument list as its second input, and returns 1 if the encoded function is defined for the encoded arguments, 0 if it is not.
I describe the proof as a diagonalization, but the "diagonal" part may not be obvious from the prose of the proof. Think of some of the values of the defined? as being laid out in a two-dimensional array, in which the rows correspond to (encodings for) partial recursive functions and the columns to individual numbers, supplied as arguments to any of those functions that are singulary. Each of the entries in the array is either 1 or 0 (here understood as "true" or "false"), depending on whether the function represented in the row is defined for the argument represented in the column.
We'll stipulate that the rows for non-singulary functions are all zeroes, since the valence mismatch essentially means that the function provides no value when given an argument list of the wrong length. This is consistent with the definition of apply, which is undefined when the valence of the function encoded by its first input differs from the length of the list encoded by its second input.
We'll also specify that the rows whose numbers don't actually encode partial recursive functions are all zeroes. This, too, reflects the fact that apply is undefined whenever its first input does not encode any function.
The self-undefined? function basically walks down the diagonal of this array, which is made up of cases in which the two arguments to defined? are equal. It looks at the value of defined? and reverses it, which in effect proves that self-undefined? is not among the functions whose encodings are listed (and so is not partial recursive, so that defined? cannot be partial recursive either).
The proof of Theorem 14.1 actually reaches the contradiction in a slightly more elaborate way, using self-undefined? as the basis for an unbounded minimization that, in effect, converts all the ones along the diagonal of the array into zeroes and all the zeroes into "undefined". The self-blocker function that results from the construction cannot be partial recursive, because, if it were, it would by definition be undefined at its own encoding if, and only if, it was defined at its own encoding.
Incidentally, it turns out that the total? predicate, which takes the encoding for a partial recursive function and outputs 1 if that function is total and 0 if it is not, is not partial recursive either. On the other hand, the predicate that returns 1 if its argument encodes a partial recursive function and 0 otherwise is partial recursive (and indeed primitive recursive -- it's the function? predicate from section 11), and so is the predicate that tests whether its argument encodes a primitive recursive function.
Study questions
- Show that apply is undefined whenever the valence of the function encoded by its first input is not equal to the length of the list encoded by its second input.
- The encoding
for a singulary, partial recursive function f is self-denying if, and only if, 
. Prove that the set of self-denying encodings is not a primitive recursive set.
