5
$\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
    Commented Jul 24, 2018 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
    Commented Jul 24, 2018 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
    Commented Jul 24, 2018 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
    Commented Jul 24, 2018 at 8:03

5 Answers 5

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
    Commented Jul 24, 2018 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
    Commented Jul 24, 2018 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
    Commented Jul 24, 2018 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
    Commented Jul 24, 2018 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
    Commented Jul 24, 2018 at 8:01
4
$\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$
0
$\begingroup$

I think the original question to be valid and Ciarán Taaffe's answer to be useful: Consider a diagonalisation on Turing machines, computing total computable functions from N to N. Then, G would be given a number, select the corresponding TM from the assumed enumeration, calculate the value and so on. But by assuming G was part of this list, there is a recursion (if G is given its own number in the enumeration) and therefore G does not terminate on that number and, in conclusion, does not compute a total function. With this contradiction, only the assumption that G was on that enumeration, is wrong (especially since it would not compute a total function if it were) and does not help proving more than that.

$\endgroup$
1
  • $\begingroup$ This is exactly the property to be proved. Given an enumeration of (representations of) total functions, we can build a total function that is not on the list. Ergo, there is no way to list all and only total functions; every listing is incomplete. $\endgroup$
    – Dan Doel
    Commented Dec 19, 2023 at 0:15
0
$\begingroup$

Suppose f_k, k = 0,1,… is any enumeration of total functions on the natural numbers, n >=0, that is, total functions whose domain and codomain are the natural numbers. Then g(n) = f_n(n) + 1 is a total function which is not in the enumeration. For if it were, say the mth, then g(m) = f_m(m) + 1 = g(m) + 1, a contradiction. We conclude that there is no enumeration of ALL the total functions on the natural numbers as the above argument applies to all the enumerations of total functions on the natural numbers.

$\endgroup$
-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
    Commented Jan 27, 2021 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$ Commented Jan 27, 2021 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$ Commented Apr 17, 2021 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$ Commented Apr 17, 2021 at 18:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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