A computable universal function for any countable set of computable functions exists.

Question

Assume $\{f_i:\mathbb N^k\to\mathbb N\}^\infty$ is a countable set of computable functions. Prove that a computable universal function exists for this class.

This more general question stems from the special case of the polynomials. I have reduced the less general one to this one, but I don't know how to proceed.

EDIT: By a universal function for a class $\{f_i:\mathbb N^k\to\mathbb N\}_{i\in I}$ I mean a function $\Phi:\mathbb N^{k+1}\to\mathbb N$ such that $\forall i\in I\quad\exists j\in\mathbb N\quad \Phi(j,x)=f_i(x)$ and the converse $\forall j\in \mathbb N\quad\exists i\in I\quad \Phi(j,x)=f_i(x)$. Therefore, a universal function exists for a class if and only if the class is of countable or finite cardinality.

I believe that if the all the functions of a countable set are computable, a computable universal function exists. Isn't that so?

This seems false. What do you have in mind when you say "a computable universal function"? — Carl Mummert, Nov 23 '13 at 01:33
Presumably the set has to be computably countable. Otherwise I think it's not true, e.g. if $f_i(n)$ is the Busy Beaver function $BB(i)$ for all $n$. — TonyK, Nov 23 '13 at 08:59
@Ivan: For instance, the set of Turing machines that never halt is certainly countable, because the set of all Turing machines is countable. But it's not computably countable, because you can't write a program that lists them one after the other. — TonyK, Nov 23 '13 at 14:24

score 3 · Accepted Answer · answered Nov 23 '13 at 12:28

Let $A \subseteq \omega$ be a set that is not recursively enumerable. For each $i \in A$ let $f_i$ be the constant function $\lambda x.i$; each $f_i$ is computable. Then $\{f_i : i \in A\}$ has no computable universal function. Because, if $\Phi$ was a computable universal function, then $A = \{ \Phi_j(0) : j \in \omega\}$ would be recursively enumerable.

There is terminology for a collection $C = \{g_j : j \in \omega\}$ of partial computable functions that does have a universal function: we would say $C$ is uniformly computably enumerable. More generally, if we have a sequence of functions $\langle g_j : j \in\omega\rangle $ we would say $g_j$ is uniformly computable if there is a computable function $\Phi$ such that $g_j(i) = \lambda i. \Phi(j,i)$ for all $i,j \in \omega$.

A computable universal function for any countable set of computable functions exists.

1 Answers1