Timeline for What does an admissible numbering of computable functions look like?
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 30, 2020 at 13:22 | comment | added | user111064 | Thank you both! @MarioCarneiro | |
| Nov 30, 2020 at 12:48 | comment | added | Mario Carneiro | @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 | comment | added | Andrej Bauer | Nope, just one that represents the same map as the original. | |
| Nov 30, 2020 at 12:44 | comment | added | user111064 | 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:37 | comment | added | Andrej Bauer | What does "get the set" mean? | |
| Nov 30, 2020 at 11:35 | comment | added | user111064 | 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:31 | vote | accept | user111064 | ||
| Nov 30, 2020 at 7:26 | history | answered | Andrej Bauer | CC BY-SA 4.0 |