4
$\begingroup$

It is well known and easy to see that it is possible to effectively number Turing Machine codes. That is, there is an injective and surjective recursive mapping $g:\mathbb N\to {\rm TM}$: each Turing machine has one and only one number. Then each partial recursive function (${\rm PRF}$) will be represented many times, since each ${\rm PRF}$ is produced by many different ${\rm TM}$s. In fact, Kleene's recursion theorem tells much more about how the same ${\rm PRF}$ occurs. However, the proof of the recursion theorem assumes that for each ${\rm PRF}$ it is possible to find its number (one of them).

This leaves open the following question. Is there a recursive injective and surjective function $f:\mathbb N\to {\rm PRF}$ ? That is, is there an algorithm that produces for each natural number a ${\rm TM}$ in such a way that each ${\rm PRF}$ is represented exactly once? The answer seems to be no, but why?

$\endgroup$
3
$\begingroup$

I was wrong. It IS possible to recursively list all ${\rm PRF}$ without duplication. See Richard M. Friedberg, Three Theorems on Recursive Enumeration, The Journal of Symbolic Logic, 23,3,1958

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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