From Primitive Recursive to Recursive by Iterating over more than one Argument?

Question

Is the only way a function can be recursive and not primitive recursive by growing faster than primitive recursion allows (as with Ackerman's function)?

If so, then consider the following. Primitive recursion allows for recursion in only one variable. Ackerman's function is able to grow faster than primitive recursion allows because it's recursion is over two (or three) variables. If we relax primitive recursion to allow for recursion over any finite number of variables, do we get the recursive functions? How about over countably many variables? (I am aware the minimization operator brings us to the recursive functions.)

Can someone explain intuitively why adding the minimization operator mu to PR functions gives us the "full power" of computable functions?

Answer 1

(a) Adding the minimization operator $\mu$ to primitive recursion in effect adds computation with open-ended searches ("do until" loops) to fixed-depth searches ("for" loops). So that's what gives us access to full-power, unrestricted computation.

(b) Rosza Péter gives a beautiful example of a function which is computable, takes only the values $0$ and $1$, so is not fast-growing, but is not primitive recursive.

Take a standard enumeration $f_i$ of primitive recursive functions. We can define by a double recursion a $\mu$-recursive function $\varphi$ such that $\varphi(m, n) = f_m(n)$.

Now consider the functions $g_i(n) =_{\mathrm{def}} \mathit{sg}(f_i(n))$, where $\mathit{sg}(k) = 0$ for $k = 0$, and $\mathit{sg}(k) = 1$ otherwise.

Evidently, running through the $g_i$ gives us an effective enumeration -- with many repetitions -- of all the primitive recursive functions which only take the values 0 and 1.

Now consider the $\mu$-recursive function $\psi(n) = \mathit{\overline{sg}}(\varphi(n,n)) = |1 - \mathit{sg}(\varphi(n,n))|$. This function too only takes the values 0 and 1; but it can't be primitive recursive. For suppose otherwise. Then for some $k$, $\psi(n) = g_k(n) = \mathit{sg}(\varphi(k,n))$. So we'd have $$\mathit{sg}(\varphi(k,n)) = \psi(n) = |1 - \mathit{sg}(\varphi(n,n))|$$ and hence

$$\mathit{sg}(\varphi(k,k)) = \psi(k) = |1 - \mathit{sg}(\varphi(k,k))|$$

Which is impossible. Therefore there are $\mu$-recursive-but-not-p.r. functions which only ever take the values 0 and 1, and hence do not suffer value explosion.

(c) It can be shown, however, that while values of such functions as $\psi$ remain entirely tame, lengths of computations for values of $\psi$ go wild. Less metaphorically, we can show that for any such $\psi$ which is computable but not p.r., there can't be a p.r. function $s(n)$ which bounds the number of steps required in the Turing computation of $\psi(n)$.

(d) Again Rosza Péter discusses multiple recursion: and shows we can still diagonalize out even if we allow nested recursion on $n$ variables for every $n$.