Proof that total computable functions are not enumerable

In an answer to this question, a sketch of the proof that total computable functions are not enumerable is made:


Because of diagonalization. If $(f_e:e \in N)$ was a computable enumeration of all total computable functions from N to N, such that every $f_e$ was total, then $g(i)=f_i(i)+1$ would also be a total computable function, but it would not be in the enumeration. That would contradict the assumptions about the sequence. Thus no computable enumeration of functions can consist of exactly the total computable functions.

I really don't understand why


then $g(i)=f_i(i)+1$ would also be a total computable function

Indeed if $g$ was a total computable function, then $\exists k, f_k=g$, so that $g(k) = f_k(k) + 1 = g(k) + 1$, which is impossible.

So it seems to me that building $g$ is impossible, so that we cannot reach a contradiction by saying that we have built another total computable function which is not in our enumeration.

I tried shifting the diagonal to avoid this effect, but other loops of the same kind can't be ruled out.

$g$ is total computable by definition.

• By assumption $f : \mathbb{N}^2 \to \mathbb{N}$ is total computable.

• $1$ certainly is.

• $+$ certainly is.

• The concatenation of $+$ and $f$ is computable by construction, and that's $g$.

The details depend on the exact definition of "computable" (i.e. the machine model) you use; see e.g. here.

So under the assumption that such $f$ existed, $g$ is computable; therefore, it must have an index in $f$, which is impossible (as you note); therefore, the assumption must be false.

StackExchange Computer Science Q#95567, answer score: 5