Why exactly is the diagonal function on p.r. functions not itself p.r.?

85 Views Asked by At

1 The argument on this page strikes me as sound: however, after reading it, I found myself with the following question:

If the process of computing $F_n(k)$ is not p.r., then there must be some way in which the process uses unbounded minimization. But I can't see where that is so. Indeed, the process $F_n(k)$ seems wholly defined by referencing only p.r. functions. So I am confused about where a non-p.r. function enters into the definition of $F_n(k)$.

I assume that the p.r. functions can be enumerated by a p.r. function, but perhaps is that is mistake? Thanks for your help.