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?
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.