1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Jul 24 '18 at 6:21
  • $\begingroup$ It seems you have found and understood the contradiction, but not why this completes the proof. Hm. Maybe go back to understanding Proof by Contradiction, e.g. using Book of Proof? $\endgroup$ – Raphael Jul 24 '18 at 6:22
  • $\begingroup$ I understand proof by contradiction, just not why we could build $g$ in the first place. It seems to me we could build a program $g$, but that it will not stop on input $k$, so that function $g$ is not total, and there is no contradiction. $\endgroup$ – agemO Jul 24 '18 at 6:42
  • $\begingroup$ No, we can't. You can't build something that doesn't halt by plugging together things that halt (without something equivalent of the $\mu$-operator or while-loop, that is, which doesn't enter the picture here). $\endgroup$ – Raphael Jul 24 '18 at 8:03
4
$\begingroup$

$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.

$\endgroup$
  • $\begingroup$ "The concatenation of + and f is computable by construction" In most of the cases yes, but if $f$ itself is "The concatenation of + and f" then we have infinite recursion and it will never stop, so it is not computable. $\endgroup$ – agemO Jul 24 '18 at 6:47
  • $\begingroup$ Is there any fully formal proof (like one you can verify automatically), so that the fact that $g$ is total is clearly proven from the hypothesis ? $\endgroup$ – agemO Jul 24 '18 at 6:52
  • $\begingroup$ @agemO Such recursion can not be constructed. Note also that concatenation ($f \circ f$, i.e. $f(f(x))$) is not the same as recursion. In recursion, $f$ appears on the left-hand side of the definition as well, which it doesn't in concatenation. $\endgroup$ – Raphael Jul 24 '18 at 8:00
  • 1
    $\begingroup$ @agemO I'm afraid this proof is seen as quite basic (once you grok the ideas of proof by contradiction and diagonalization), so I don't think such a thing exists. I don't know for sure, though. $\endgroup$ – Raphael Jul 24 '18 at 8:00
  • 1
    $\begingroup$ @agemO Again, I think your issue lies with something more fundamental. Revisit the definition of (total) computability, and the exercises you did on that. Pretend $f$ was, say, multiplication -- does the construction make sense to you then? $\endgroup$ – Raphael Jul 24 '18 at 8:01
2
$\begingroup$

The problem really is in how you're approaching the proof by contradiction. You're objecting to one conclusion ("$g$ is computable and total") by drawing a different conclusion ("$g$ isn't total computable, since it's not on the list" or "... since there is a way to interpret it as referring to itself") contradicting it. But this is exactly the point: that from our hypothesis we can conclude contradictory things, so our hypothesis must be wrong. That is, within a proof by contradiction you have to sort of give yourself "tunnel vision:" when trying to prove Thing A inside a proof by contradiction, don't let its clear falseness stop you!

It may be helpful in this case to rewrite the usual proof as a direct proof, and I've done this below. Incidentally, exactly the same thing can be done with Cantor's diagonal argument, and it might help to get comfortable with that first if this proof is still confusing.


First, convince yourself of the following:

If $f$ is a total computable function of two variables, then the function $g_f: x\mapsto f(x,x)+1$ is also total computable.

Exactly how you do this will depend on which definition of "computable" you're using, but they'll all make it fairly easy. For example, in $\lambda$-calculus this is immediate: $g_f$ is just $\lambda x.S(f(x,x)).$ With Turing machines, this will take a bit more work but really only a bit.

We can now prove:

If $f$ is a total computable function of two variables, then $g_f$ is not any of the "rows" of $f$: for each $x$ we have $g_f\not=f(x,-)$ (since in particular $g_f(x)\not=f(x,x)$).

Now an effective enumeration of (some, not necessarily all) total computable functions of one variable is really just a single total computable function of two variables: "$(f_e)_{e\in\mathbb{N}}$" is really the same as the two-ary function $f: (x,y)\mapsto f_x(y)$. So phrasing things differently, what we have is:

If $(f_e)_{e\in\mathbb{N}}$ is an effective enumeration of total computable functions, then there is a total computable function $g$ which is not equal to any of the $f_e$s.

Namely, let $g(x)=f_x(x)+1$.

Note that everything here is direct: I haven't used a proof by contradiction anywhere. But now it should be obvious that there is no effective enumeration of all the total computable functions, since that would contradict the point above.

The basic flow of ideas in the proof-by-contradiction-version of this argument is:

  • We start with a hypothetical object: an effective enumeration $E$ of all the total computable functions.

  • Well, in particular it's an effective enumeration of some total computable functions (it just happens to hit them all) ...

  • ... And for any effective enumeration of total computable functions, we have a total computable function not so enumerated.

  • So in particular there is a total computable function not in $E$, and this contradicts the assumption on $E$, so we're done.

Note, though, that this is really just adding an unnecessary level of confusion: it's really better to proceed as above, where we prove directly a fact ("For every effective enumeration of total computable functions, we can find (in fact, effectively in an index for the enumeration!) a total computable function not so enumerated") which implies the thing we want ("No effective enumeration of total computable functions gets all of them").

$\endgroup$
-2
$\begingroup$

Ok I think I got it, what I found unclear was that for $g$ to be computable we have to suppose that it is not in our enumeration $E$ (otherwise it leads to the self reference I wrote), which seems wrong since it is what we are trying to show. But it is not a problem: we can try both possibilities ($g \in E \lor g \notin E$) and show that both leads to contradiction:

If $g \notin E$, then there is no self reference for $k$, so $g$ is computable, so it should be in $E$: contradiction.

If $g \in E$, then $g(k) = g(k) + 1$: contradiction.

That was obvious, but I still (maybe erroneously) think that saying that $g$ is total computable by definition is wrong and it is what mislead me.

$\endgroup$
  • 1
    $\begingroup$ Your worries are unecessary, and so is your case distinction, so you did not actually explained anything. I am saying this because I do not want you to walk away with a false feeling of security. Just read the theorem as follows. Let $(f_e)_{e \in \mathbb{N}}$ be any computable sequence of total computable functions. (Any sequence whatsoever!) Then we can construct a total computable $g$ which is not in this sequence. (Do not preoccupy yourself wheter $(f_e)_e$ enumerates all computable funcitons or whether $g$ is enumerated by them or whatever. The theorem just works.) $\endgroup$ – Andrej Bauer Jul 24 '18 at 20:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.