1

Phrased differently, is there a computable list of (indices for) total computable functions, such that every total computable function appears at least once? If true, it would mean that even though we can't list all the total computable algorithms, we can list all total computable functions. So the question is philosophically interesting, if nothing else.

Notation:

$\varphi_e$ is the $e$-th partial computable function in some fixed effective list.

$\mathrm{Tot}:=\{e:\forall x [\varphi_e(x)\downarrow]\}$

$\mathrm{Fin}:=\{e:\exists n\forall x>n[\varphi_e(x)\uparrow]\}$

My thoughts:

To show that the answer is "no", it would suffice to show that there is no computable set $B\subset\mathrm{Tot}$ such that $B$ contains an index for every total computable function. (Since any c.e. set enumerated in increasing order is computable, it suffices to — given a c.e. set $A=\{a_0,a_1,\cdots\}$ as in the title — enumerate an increasing c.e. set $B=\{b_0,b_1,\cdots\}$ so that $\varphi_{a_i}=\varphi_{b_i}$ for each $i$. This is easy to do by padding.)

Interestingly, if you replace $\mathrm{Tot}$ with $\mathrm{Fin}$, then the answer is "yes, such a c.e. set does exist": Let $f$ be your favorite bijection from $\omega$ to $\{\sigma\in 2^{<\omega}: \operatorname{length}(\sigma)\text{ is even}\}$. If $f(e)=(x_1,\cdots,x_n,y_1,\cdots,y_n)$, let the $e$-th function on your list send $x_i$ to $y_i$ and diverge on input other than $x_1,\cdots,x_n$. There doesn't seem to be an obvious way of applying this same trick to $\mathrm{Tot}$, though.

A. Howells
  • 845

1 Answers1

4

There is indeed no such set.

The key point is that when we diagonalize against a computable list of (indices for) total functions, we (1) preserve totality and (2) get a computable function not on the list.

Specifically, suppose $E=(e_i)_{i\in\mathbb{N}}$ is any computable sequence of natural numbers. Associated to the sequence $E$ is the computable, possibly partial, function $d_E$ given by

  • $d_E(i)=\varphi_{e_i}(i)+1$ if $\varphi_{e_i}(i)\downarrow$, and

  • $d_E(i)\uparrow$ otherwise.

Now if $\varphi_{e_i}$ is total for each $i$, we get that $d_E$ is also total. Moreover, we clearly have that $d_E\not\cong\varphi_{e_i}$ whenever $\varphi_{e_i}(i)\downarrow$, and in particular whenever $\varphi_{e_i}$ is total.

So given a computable sequence $E$ of indices for total computable functions, the associated function $d_E$ is total computable and does not have an index in $E$.

Noah Schweber
  • 245,398