# What does an admissible numbering of computable functions look like?

I'm trying to understand how we can construct an admissible ordering of the computable (meaning, partial recursive) functions.

Initially my take on such an enumeration was from the point of view of an enumeration of programs. For instance, we could enumerate all possible Turing machines using some set of rules (for instance, first the 1-state machines, then the 2-state machines, with some sort lexicographic order within each of the groups). Or alternatively, perhaps we could encode each program uniquely via some numbering system and then simply take them in increasing order.

These produce computable maps from $$\mathbb{N}\to$$ set of computable functions. But of course these are not bijections since multiple programs will compute the same function.

So my question is, for the purposes of something like Rice's theorem, how does one construct an admissible numbering of the computable functions?

• Oh ok I see! My confusion came from the fact admissible numberings are described as " enumerations of the set of partial computable functions that can be converted to and from the standard numbering". I interpreted this as meaning "from $N$ we can get $f_N$ and from $f_N$ we can get $N$", but non-bijection would mean we don't get a unique choice. Does it mean we can get the set $\{n\,|\,f_n =f_N\}$? Or something else entirely? Nov 30, 2020 at 11:35
• Sorry that wasn't clear -- does the "converted to and from" mean "if I give you $f_N$, the admissible numbering allows you to give me back all indices of the functions that are equal/copies of $f_N$ in that enumeration"? Nov 30, 2020 at 12:44
• @user111064 I think it means that you can describe computable functions $A$ and $B$ such that $f_n=\phi_{A(n)}$ and $\phi_m=f_{B(m)}$, where $\phi_n$ is the standard numbering. In other words, although they are not bijections, the compositions back and forth describe equivalent partial recursive functions. Nov 30, 2020 at 12:48
Any reasonable encoding will do. For example, you can imagine a version of C (or your favorite programming languages) in which integers are unbounded, and there is a reasonable input/output convention. Interpret $$i \in \mathbb{N}$$ as encoding a string $$s_i$$ in ASCII (in base 256). If $$s_i$$ is a valid C program, then it encodes some partially computable function. Otherwise, treat $$s_i$$ as encoding some fixed partially computable function, say $$f(x) = 0$$.