## The Antidiagonal of the Primitive Recursive Functions

Just for fun, I'm reading Peter Smith's draft of his new book on GÃ¶del's Incompleteness Theorems. So far, it's quite enjoyable. I might say more about it later. But here is something of which I'm not sure it's correct. (I'm also not sure it's false, that's why I'm posting it here.)

Smith shows that not all computable functions are primitive recursive by proving that the antidiagonal of the p.r. functions can't be p.r., even though it is intuitively computable. Having identified the p.r. functions with functions whose implementation doesn't require unbounded loops, he then asks why the antidiagonal function doesn't satisfy that condition:

Of course, once the table [on which we take the diagonal] is constructed, getting the value of f_n(n)+1 doesn't involve any unbounded procedures. But go back a step. How do we construct the table? We need to find f_n, the n-th function in our enumeration of p.r. functions, and how do we do that? To repeat, we start by setting out all the possible function definitions in some standard language, and then we trawl along the list, looking for those function-definitions that fit the conditions for specifying a p.r. function. And that involves unbounded searches -- when we've found the n-th function, we search until we find the n+1-th (we know that there will always be a next p.r. function, because there are plainly unlimitedly many of them since they can be defined by unlimitedly long definitional chains: but we don't know when the next p.r. function will turn up.) (p.67)

Is this true? Suppose the definitions are written in the Boolos/Jeffrey notation, where e.g. 'Cn[A,B]' denotes the composition of A and B, and 'z' the zero function of one argument. Suppose then we've identified a string A as representing the n-th p.r. function of one argument. Then 'Cn[z,A]' represents another such function. So we have a p.r. upper bound for when we'll reach the n+1-th p.r. function.

In fact, couldn't we encode the p.r. functions in such a way that every natural number represents some p.r. function? Then the (trivially p.r.) identity function enumerates the p.r. functions.

So I suspect that unbounded loops aren't needed for the enumeration of the p.r. functions, but rather somewhere in the decoding of the enumerated GÃ¶del numbers, or more generally in the meta-algorithm that executes arbitrary p.r. functions. Comments?

# on 04 October 2004, 02:02

You're exactly right. The unbounded search occurs not in finding f_n, but in computing f_n(n). Given any encoding scheme of p.r. functions, there can be no primitive recursive bound (depending on n) on the length of the computation of f_n for input m. More generally, there's no p.r. function u(n, m) = f_n(m) because the length of the computation of f_n(m) is not bounded (primitive recursively) in n, m. In other words, there's no p.r. universal p.r. function.

# on 04 October 2004, 18:48

Thanks! Yes, that's what I suspected, except that you put it much more succinctly.

# on 18 October 2004, 02:41

Thinking about this a little more it seems to me that the following might be true: A standard G?del numbering of p.r. definitions (e.g., a G?del numbering of the Boolos/Burgess/Jeffrey notation) may be such that there is a p.r. bound on the length of the computation of f_n(m) in terrms of m and the G?del number of f_n (although not of n). In that case, the unbounded search is indeed in finding the G?del number of f_n (and the function from n to the G?del number of f_n is not p.r.)

# on 18 October 2004, 11:23

I'm afraid I don't get it. The complexity of a p.r. function's definition, and therefore its g?del number, certainly constrains the length of computing it (for a given value). But why is this constraint a *p.r.* function of the complexity?

Consider the list x+x, x*x, x^x, etc., whose diagonal is also not p.r. Given the p.r. definition of any item on this list in Boolos notation, one gets the next definition simply by concatenating the n-th defition with a few other g?del numbers (and concatenation is p.r). So the g?del number of the n-th function f_n in this list is a p.r. function of n. Yet there is no p.r. upper bound on f_n(n) in terms of n. Did I miss something?

# trackback from on 28 September 2004, 17:09