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.
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.)