Enumerating the primitive recursive functions without repetition According to this paper (and this one), it is possible to enumerate the primitive recursive functions without duplication, even though equality of primitive recursive functions is not decidable. I am having trouble understanding how the enumeration actually works, however. Can anyone provide a concrete example of an algorithm that enumerates the primitive recursive functions, or does anyone know of a resource that provides such an algorithm?
Any help would be greatly appreciated!
 A: In general, if I can enumerate a list of computable functions I know to be total, then I can enumerate that same list without repetition. 
Here's how to do this. Suppose I have an enumeration $\{f_n: n\in\mathbb{N}\}$ of some total computable functions. Say $f_n$ looks new at stage $s$ if for every $m<n$, there is a $k<s$ such that $f_n(k)\not=f_m(k)$; that is, $f$ is visibly different from each of the previous $f_m$s, just by looking at the first $s$-many bits.
Since each $f_n$ is total, the predicate "$f_n$ looks new at stage $s$" is computable (just look at the first $s$ bits of $f_1, f_2, . . . , f_n$ and compare). So to build a list without repetitions, we just wait until we see some new $f_n$ look new, and then add it to our list; since we only add $f_n$s which look new, we're guaranteed to not get repetition, and as long as we do things in a reasonable order, every $f_n$ will wind up represented on the list.
Formally, here's how we build our no-repetitions list:


*

*Note that $f_1$ automatically looks good at stage $1$; let $n_1=1$.

*Let $s_1$ be the least natural number such that some $f_n$ ($n\not= n_1$) looks new at stage $s$; let $n_2$ be the least such $n$.

*In general, having defined $n_i$, let $s_i$ be the least natural number such that some $f_n$ ($n\not=n_1, n_2, . . . , n_i$) looks new at stage $s$; and let $n_{i+1}$ be the least such $n$.
We get a sequence of numbers $n_1, n_2, n_3, . . .$ this way. Our no-repetitions list is just $$f_{n_1}, f_{n_2}, f_{n_3}, . . .$$ It's now a good exercise to show that this list has no repetitions, and for each $n$ there is some $i$ such that $f_n=f_{n_i}$.

A huge caveat:

There is no effective procedure to tell where a given function shows up on this repetition-free list. Specifically, let's say I want to know where $f_{12}$ lands. Unfortunately, there's no way to find which $i$ satisfies $f_{n_i}=f_{12}$! This is a good exercise, and is why this construction doesn't contradict the fact that deciding equality of primitive recursive functions isn't effective.


You may also be interested in the much harder construction of a Friedberg enumeration: there is a computable sequence $e_i$ such that


*

*Every partial recursive function $\varphi_e$ is equal to some $\varphi_{e_i}$, and

*$\varphi_{e_i}=\varphi_{e_j}$ iff $i=j$.
That is, we can list the partial recursive functions without repetition! This is really crazy, and may seem to contradict the fixed point theorem.  The saving grace is, again, the fact that this list is basically terrible: there's no way to tell where a specific function appears on it. In particular, basic operations on indices are no longer computable.
