3

Is it possible to list all partial recursive functions such that every function appears only once in the enumeration. More precisely, does there exist (total) recursive function $f:\mathbb{N} \rightarrow \mathbb{N}$ such that for any two different values $a,b \in \mathbb{N}$ (where $a\ne b$) the following two properties are satisfied:

(1) $\phi_{f(a)} \ne \phi_{f(b)}$ (the two functions on the left and right hand side aren't the same)

(2) For any possible partial recursive function $g:\mathbb{N} \rightarrow \mathbb{N}$ there exists some value $N \in \mathbb{N}$ such that $g=\phi_{f(N)}$ (the two functions on the left and right hand side are the same)

$\phi_x$ denotes the function computed by the program corresponding to index $x$ (under a reasonable 1-1 correspondence between the collection of programs and $\mathbb{N}$).

SSequence
  • 1,022
  • "Non repeating complete list" rather than "unique listing" may better describe it. Up to you. – DanielV Aug 30 '18 at 10:02
  • This would require a zero-test for partial recursive functions, which in turn would require a solution to the halting problem. – Mark Aug 30 '18 at 13:05

1 Answers1

4

Yes, there is a total computable function with those properties. The existence was proved by Friedberg in 1958 using a priority argument.

Friedberg, Richard M. “Three Theorems on Recursive Enumeration. I. Decomposition. II. Maximal Set. III. Enumeration Without Duplication.” The Journal of Symbolic Logic, vol. 23, no. 3, 1958, pp. 309–316. JSTOR www.jstor.org/stable/2964290.

These uniformly computable non-repeating enumerations are called Friedberg numberings in the literature.

Carl Mummert
  • 81,604
  • Thanks, having a glance .... it seems that the last result there is exactly what I was asking. After posting this question, one other variant of this question also came to my mind. If we denote the set of partial recursive functions (1 input) as $P$ and the set of total recursive functions (1 input) as $R$ then does there exist a total computable function that enumerates (using indexes) every element of $P-R$ once and exactly once (original question was for $P$). Does that follow as a not-so-difficult corollary of the results/techniques in the paper (or is this question little different)? – SSequence Aug 30 '18 at 14:43
  • 1
    The original article linked to in this answer is unfortunately spywalled, but a different (rather dense) two-page proof by M. Kummer (1990) is found at https://www.sciencedirect.com/science/article/pii/0304397590901414 – hmakholm left over Monica Aug 30 '18 at 16:06
  • @SSequence: The technique in the proof I linked to does extend directly to enumerating the non-total partial recursive functions without repetition. – hmakholm left over Monica Aug 30 '18 at 16:24
  • @HenningMakholm Nice link .... sounds quite interesting that there are two different techniques for the same problem – SSequence Aug 30 '18 at 16:32
  • @SSequence: The author I link to does credit Friedberg with a core idea in the proof, so "two different techniques" may be to oversell the difference. It's probably more of an incremental improvement -- though evidently enough of an improvement that TCS accepted the 1990 article. – hmakholm left over Monica Aug 30 '18 at 16:38