Is there a computable enumeration of a set of all computable functions $\mathbb{N} \to \mathbb{N}\cup\{\infty\}$?

Question

Consider the set $F$ of all functions from natural numbers to natural numbers (possibly with undefined points) which are computable (implementable in python). Does there exist an enumeration of them $F=\{f_i\}_{i\in\mathbb{N}}$ such the function $g(i, x) := f_i(x)$ is computable?

I know that if we allowed repetitions in the enumeration, the answer would be yes via the universal machine (enumerating algorithms instead of functions is possible).

I know that if we did not allow undefined points, the answer would be no via the diagonal argument on function $g'(x):=g(x, x) + 1$ which would have to be computable but could not coincide with any $f_i$.

However, I can't figure out the middle case. My hunch is that the answer is no.

Such a set is uncountable. Hence there does not exist any enumeration of it. — Vivaan Daga, Aug 10 '22 at 18:43
@Shinrin-Yoku Note that the body of the question specifies that the functions in question are computable. To the OP, you should make the body match the title (or vice versa); the two questions at present are quite different. — Noah Schweber, Aug 10 '22 at 19:38
@NoahSchweber What are you referring to? Is there another meaning for computable enumeration of functions? — Serge Seredenko, Aug 10 '22 at 20:02

score 3 · Accepted Answer · answered Aug 10 '22 at 19:41

Note that the title question does not match the body. I'll answer the question in the body, since the title question is trivial.

Perhaps surprisingly, the answer is yes! That is:

There is a partial computable binary function $f(x,y)$ such that for all partial computable unary functions $g(x)$ there is exactly one $n$ with $$g(-)\simeq f(-,n).$$

Such an $f$ is called a Friedberg enumeration (or numbering); the existence of Friedberg enumerations was first proved by (unsurprisingly) Friedberg, but a simpler argument was later given by Kummer. I've written a bit more about these at CSSE and at MO.

I am happy I topped up your collection of SE sites where you featured this nice result :) — Serge Seredenko, Aug 10 '22 at 20:28

Is there a computable enumeration of a set of all computable functions $\mathbb{N} \to \mathbb{N}\cup\{\infty\}$?

1 Answers1