4
$\begingroup$

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?

$\endgroup$
7
$\begingroup$

(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$.

$\endgroup$
2
  • $\begingroup$ Beautiful indeed - I appreciate the answer you gave. I wish the references I have seen explained it is about the rate of growth of computations, not values that make for the difference. $\endgroup$ Aug 27 '15 at 6:45
  • $\begingroup$ Presumably the material here attributed to Rósza Péter is from her book "Recursive functions". It's been a long time since I looked at it, but my recollection is that it's mostly about many sorts of extensions of primitive recursion, more than about general recursive functions. So it may give the OP a more detailed picture of what can and cannot be done with various sorts of recursions. $\endgroup$ Aug 28 '15 at 23:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.