4
$\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$
4
  • $\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
5
$\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$
7
  • $\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
3
$\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
  • 2
    $\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
-3
$\begingroup$

The answer is that you have found a legitimate problem with these naive proofs by diagonalisation. In practice, diagonalisation cannot be applied to computational theory. Diagonalising is only possible in the fantastical land of actually infinite sets. There are no such things in the world of computation.

The problem is this: It is impossible to build a machine g case by case, because we would require an infinite number of cases, and the description of g would grow in length forever. However, to define g differently to any total computable function requires that g itself is not a total computable function, otherwise it would be different to itself! But we cannot begin by assuming what has to be proven.

$g(i)=f_i(i)+1$ is not a definition. It is a property. It means "define g of i such that ..."

Unless a procedure can be legally described which computes g, then this property is meaningless in the world of computation. The reason that functions with such properties can be assumed to exist in the fantastical world of actually infinite sets is because the Axiom of Choice allows them to choose elements from every set in an infinite set all at once. Obviously in the finite world of computation, this is impossible.

Finally, I would like to point out that Turing, in his original 1936 paper does not give such a stupidly naive argument for the existence of uncomputable real numbers. His proof is much more complex, precisely because he was aware that direct self-reference such as this must be avoided.

$\endgroup$
4
  • $\begingroup$ This is an Agda formalization of the argument. Agda runs on computers (real ones, not imaginary Turing machines). I think working programmers would be amused to hear that $g$ cannot be defined, since it's something so basic they wouldn't even think about doing it day-to-day in actual programming languages that run on actual computers. :) $\endgroup$ – Dan Doel Jan 27 at 5:24
  • $\begingroup$ You can actually quite easily write $g$ in any programming language you like. In Python it would be return f[i](i) + 1. You are not supposed to assume anything about $g$. The only thing we assume is that there is an iteration of total functions and that you therefore can get the ith function using f[i] in Python. $\endgroup$ – Pål GD Jan 27 at 11:05
  • $\begingroup$ @DanDoel g above is not a definition of a function. However, your agda implementation of g is indeed a well-defined function. Unfortunately you do not prove that your implementation of g is total computable. In fact. it is impossible to prove this, since by definition the function is not total, and cannot be computed on the elements of the domain for which it is not defined. $\endgroup$ – Ciarán Taaffe Apr 17 at 18:32
  • $\begingroup$ @PålGD actually it is assumed that g is total computable if f is. If you read 3.1 and 3.2 of the paper "Breaking the Normalization barrier", you will learn why the assumption that g is total if f is, is incorrect. $\endgroup$ – Ciarán Taaffe Apr 17 at 18:36

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.