1

Consider the following set of four symbols $M=\{S,\square,\circ,-\}$. Take $S\colon \mathbb{N}\to \mathbb{N}$ to be the successor function $x\mapsto x+1$. Given $f,g\colon \mathbb{N}\to \mathbb{N}$, let $f\circ g$ denote the usual composition operator on two functions $x\mapsto f(g(x))$, let $f-g$ be the function where $$ x\mapsto \begin{cases}f(x)-g(x) & \text{if $f(x)\geq g(x)$}\\ 0 & \text{ otherwise,}\end{cases} $$ and let $f^{\square}$ be the "iteration" of $f$ defined recursively by the conditions $f^{\square}(0)=0$ and $$ f^{\square}(x+1)= f(f^{\square}(x)). $$

Instead of writing expressions as above, I will instead use Polish notation. So, for example $\circ \square SS$ is the Polish notation for $S^{\square}\circ S$, whereas $f- \square f$ is not a well-formed expression. There is a very easy algorithm for determining whether any string of symbols from $M$ is a well-formed expression or not.

It is known, due to work of Daniel E. Severin, that every unary primitive recursive function is given by such a well-formed expression from the set $M$.

Now, consider the following pseudo-code (that I could easily implement on a computer):

Step 1: Take $n$ as input from the user.

Step 2: Create the ordered list of all strings of length $\leq n+1$ from the alphabet $M$, in the shortlex order (where we put $S<\square < \circ < -$).

Step 3: Run through this list and remove any string that does not yield a well-formed expression.

Step 4: Take the $n+1$st expression, $e$, from the remaining expressions in the list.

Step 5: Construct the code for the function $f$ represented by $e$.

Step 6: Print $f(n)+1$ to the screen, and terminate.

This program cannot describe a unary primitive recursive function, because it disagrees with them all (due to the "$+1$" part of Step 6). I'm trying to figure out exactly where this fails primitive recursion. I'm guessing it is in Step #5, where we replace the expression with the actual function it expresses.

However, I've been taught that primitive recursive functions are those computer programs that don't use unbounded searches/while loops, and I'm not seeing an unbounded search here. I expect that an expert will immediately see the issue, and so I want to express thanks in advance for any comments and thoughts.

Pace Nielsen
  • 584
  • 5
  • 15

1 Answers1

4

It's not step $5$, but step $6$. Or more precisely (as Andreas Blass comments below), it's the implicit "step $5.5$" which is needed to make sense of step $6$: computing $f(n)$ in the first place.

The issue is that there is no "universal compiler" for primitive recursive functions which is itself primitive recursive. The issue, intuitively, is that each individual p.r. function is "bounded complexity" in a particular sense but there is no single "bound on the bounds."

In fact there's nothing specific to primitive recursion here: by simple diagonalization, if $F=(f_i)_{i\in\mathbb{N}}$ is any indexed family of total computable functions then there is no $F$-universal function in $F$ itself. (Totality plays a crucial role here of course.)

Noah Schweber
  • 245,398
  • 1
    For the 6 steps in the question, this is the right answer. But I'd be inclined to say that there's a missing step 5.5, namely "run the code produced in step 5 on input $n$." And then I'd say the "run" in this step is the problem. (I think the OP took step 6 to implicitly contain what I call 5.5, which puts the problem into step 6, but the implicitness can hide the problem.) – Andreas Blass Feb 10 '21 at 20:56
  • @AndreasBlass Yes, that's of course a more exact way of phrasing my answer. I'll edit to clarify that. – Noah Schweber Feb 10 '21 at 20:57
  • @AndreasBlass and Noah: Thanks! Supposing I have access to two functions $f$ and $g$, then I believe I can write a primitive recursive program that runs $f-g$ or $f\circ g$ or $f^{\square}$. Similarly, I can write a program to handle a fixed finite number of concatenations of these operations. Certainly, I can suppose $S$ is already compiled and ready to go. So, is the issue simply that I cannot run arbitrarily long concatenations of these processes, in a primitive recursive manner, because as I build up these functions, the run times are not a priori bounded in terms of the given data? – Pace Nielsen Feb 10 '21 at 21:49
  • P.S. Regarding partial unary primitive recursive functions, is there a universal function for those? – Pace Nielsen Feb 10 '21 at 21:56
  • @PaceNielsen Re: your first comment, if I understand it correctly then yes, that's basically right. Re: your second comment, what is a partial unary primitive recursive function? – Noah Schweber Feb 11 '21 at 04:09
  • @NoahSchweber I was thinking that might be troublesome. I suppose my real question is "Why did you emphasize the word total?" Perhaps a better question would be to remove the word "primitive" and ask whether or not there is a universal function for the partial unary recursive/computable functions. I would have guessed not (even if the usual proof for total functions doesn't work here). – Pace Nielsen Feb 11 '21 at 17:08
  • @PaceNielsen Yes, there is a universal function for the partial computable unary functions - this is exactly what a universal Turing machine does. – Noah Schweber Feb 11 '21 at 17:37
  • @NoahSchweber Thanks! – Pace Nielsen Feb 11 '21 at 17:56