Is there a recursive injective and surjective function f:N→PRF?

394 Views Asked by At

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?

1

There are 1 best solutions below

0
On

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