1
$\begingroup$

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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

The encodings you mention are admissible. Why do you think they need to be bijections?

In fact, there is no admissible numbering of partial computable maps that is a bijection. If there were one, we could decide equality if partial computable maps, which would allow us to implement the Halting oracle.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – user111064
    Commented Nov 30, 2020 at 11:35
  • $\begingroup$ What does "get the set" mean? $\endgroup$
    – Andrej Bauer
    Commented Nov 30, 2020 at 12:37
  • $\begingroup$ 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"? $\endgroup$
    – user111064
    Commented Nov 30, 2020 at 12:44
  • $\begingroup$ Nope, just one that represents the same map as the original. $\endgroup$
    – Andrej Bauer
    Commented Nov 30, 2020 at 12:48
  • $\begingroup$ @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. $\endgroup$
    – Mario Carneiro
    Commented Nov 30, 2020 at 12:48
2
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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