1

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.

nontology
  • 19
  • See para.3 of the linked site: the "unbounded loop" issue. The unbounded loop moves us to "general recursive" but we loose certainty of halting. – Mauro ALLEGRANZA Mar 03 '22 at 10:51
  • And that is exactly unbounded search. – Mauro ALLEGRANZA Mar 03 '22 at 10:53
  • Yes, para.3 describes how the relevant process can be computed using an unbounded loop, but why must it be? In particular, in para. 2, the process seems defined using only p.r. functions. – nontology Mar 03 '22 at 11:07
  • The argument shows that $F_n$ is computable but not p.r. (the assumption that is p.r. leads to a contradiction). Thus, there are more computable functions that p.r. ones. The computable but not p.r. ate those needing unbounded search. – Mauro ALLEGRANZA Mar 03 '22 at 12:43
  • Right, I understand that. I apologize if I am not stating my question clearly. My background assumption is that, if you can define a process using only p.r. functions, that suffices to show that it is p.r. The definition of the relevant process in para. 2 seems to use only p.r. functions. But the process is not p.r. So the definition in para. 2 of the process must somehow depend on unbounded minimization. But I can't see how it does. I grant that other definitions of the same process might reference minimization, as in para. 3. But my question is about the definition in para 2. – nontology Mar 03 '22 at 12:53
  • 1
    In para.2 you have described a function that looks "computable" (and it is...). But to state that it is p.r. you have to show how you can build it from initial p.r. functions and "p.r. only" rules and this is not shown in para.2. Why so? because it is not possible: diagonalization prove that the assumption that we can do it leads to a contradiction. – Mauro ALLEGRANZA Mar 03 '22 at 13:04
  • 1
    Ah, got it! Thank you Mauro. – nontology Mar 03 '22 at 13:13
  • See also here. – Noah Schweber Mar 03 '22 at 15:35
  • 1
    Intuition (rather than diagonalization): The "universal" p.r. function $(n,k)\mapsto F_n(k)$ would have to simulate arbitrarily nested primitive recursions $F_n$, but its construction (as a p.r. function) would involve only some fixed depth of primitive recursion. That's prima facie implausible. – Andreas Blass Mar 03 '22 at 15:44

0 Answers0