ENTSCHEIDUNGSPROBLEM – keeping simple

The basic result of the incompleteness proofs is pretty simple. The proofs are complicated because the idea was literally unthinkable until programming was invented. The heroic efforts of Gödel, Skolem, Post, and Church to create a mathematics in which doing mathematics could be represented as some sort of calculation were an incredible feat of imagination. But today, programming is kind of obvious. So the general result should be simpler.

Suppose we have a computer with an infinite memory that holds arbitrary integers and can execute a simple programming language that consists of numbers. The key thing about the computer is that numbers in memory can be interpreted as integers or instructions, as we please. It’s certainly possible that the number encodes a program that makes no sense, but every program is just an integer and every integer encodes some program. Suppose that the computer has the usual arithmetic operations and conditionals plus recursion. Because numbers are programs, we can have a number, say x, and a second number y and compute x(y) because x “encodes” some program.

Programs as values, means that we can pass programs that compute functions as arguments to other functions. For example we should be able to write “evaluate” so that “evaluate(x,y) = x(y)”. If f(x) = x*x then evaluate(f,5) = 25. It would be useful to have a function “S” which computes a “solution” to a function so that “S(f,x) = the smallest number y ≥ x so that f(y)=0”. In fact, such a function is easy to define in our language: S(f,x) = ( if f(x)= 0 then x; else S(f,x+1) ). It is easy to see that S(f,x) will never terminate if there is no y ≥ x so that f(y)=0. For example if g(x) = x+1 then S(g,1) never terminates. The question is whether we can write a function E(f,x) so that E(f,x) always terminates and so E(f,x)=1 if S(f,x) terminates and E(f,x)=0 if S(f,x) does not terminate. E doesn’t find the solution, it just has to tell us whether S will find the solution. However, we can prove that we cannot write E with these specifications.

The proof is by contradiction. Suppose we could write E. Then someone could write a “diagonal” program

D(f) = { if E(f,f)=0 then 1; else S(f,f) }.

So D(f) =1 if E(f,f)=0; there is no y ≥ f so that f(y)=0 but D(f) never terminates otherwise. What about D(D) ? Does it terminate? If E(D,D)=0 then D(D) terminates with value 1. But if E(D,D)=0 then for every y ≥ D, D(y) never completes. Which means D(D) does not terminate. So

D(D) terminates with value 1 if and only if D(D) does not ever terminate.

D(D) does not terminate if and only if D(D) does terminate.

Assuming that the world makes logical sense ( a big leap) then to get to this paradoxical result, we must have assumed something that is false: namely that we could somehow define E(f,x) so that it always terminates and correctly computes the answer to whether S(f,x) terminates.

For mathematics, this result has all sorts of interesting implications. For example, if it were not true, we could, in principal, write a function that tested numbers to see if they were odd perfect numbers and marched up the positive integers until it found one. If that function could be evaluated by E, we’d know if there was such a number – something nobody seems to know right now. Any theorem Exists x, P(x) where P can be represented in our language could be tested by evaluating E on a function that tests P on consecutive integers until it finds a solution. Any theorem Forall x P(x) could be evaluated by seeing if a program that looks for a
counter-example ever terminates. All that should indicate that E is implausible as well as impossible. For computer science the implications are more subtle because the fact that we don’t really have computers with infinite memory matters in computer science. That’s also interesting in pure mathematics: see Godel’s lost letter.

Gödel’s Lost Letter

Gödel’s perspective in this letter is a refutation of the simplistic take on Turing’s proof seen so often in the computer science literature. In particular:

After all, one would simply have to choose the natural number n so large that when the machine does not deliver a result, it makes no sense to think more about the problem

Here is the letter:

“One can obviously easily construct a Turing machine, which for every formula F in first order predicate logic and every natural number n , allows one to decide if there is a proof of F of length n (length = number of symbols). Let \(\psi(F, n)\) be the number of steps the machine requires for this and let \(φ(n) = max_F (F, n)\) . The question is how fast φ(n) grows for an optimal machine. One can show that φ(n) ≥ kn . If there really were a machine with \(φ(n) \sim k·n\) (or even \(\sim k·n^{2}) \), this would have consequences of the greatest importance [Tragweite]. Namely, it would obviously mean that in spite of the undecidability of the Entscheidungsproblem, the mental work of a mathematician concerning Yes-or-No questions could be completely replaced by a machine. After all, one would simply have to choose the natural number n so large that when the machine does not deliver a result, it makes no sense to think more about the problem. Now it seems to me, however, to be completely within the realm of possibility that φ(n) grows that slowly. Since (1) it seems that \(\phi(n)∼ kn \) is the only estimation which one can obtain by a generalization of the proof of the undecidability of the Entscheidungsproblem; and (2) after all \(φ(n) ∼ k·n\) (or \(∼ k· n^2 \)) only means that the number of steps as opposed to trial and error can be reduced from N to log N (or \((log N )^2 )\). However, such strong reductions appear in other finite problems, for example in the computation of the quadratic residue symbol using repeated application of the law of reciprocity. It would be interesting to know, for instance, the situation concerning the determination of primality of a number and how strongly in general the number of steps in finite combinatorial problems can be reduced with respect to simple exhaustive search.”

( Peter Clote’s translation of Godel’s letter to von Neumann from Sam Buss’s paper).

See also Sipser’s paper which has a different translation of the letter.

Here is Turing’s claim:

I propose, therefore, to show that there can be no general process for determining whether a given formula U of the functional calculus Z is provable, i.e. that there can be no machine which, supplied with any one U of these formulae, will eventually say whether U is provable.

It should perhaps be remarked what I shall prove is quite different from the well-known results of Gödel [15]. Gödel has shown that (in the formalism of Principia Mathematica) there are propositions U such that neither U nor –U is provable. As a consequence of this, it is shown that no proof of consistency of Principia Mathematica (or of Z) can be given within that formalism. On the other hand, I shall show that there is no general method which tells whether a given formula U is provable in Z, or, what comes to the same, whether the system consisting of Z with –U adjoined as an extra axiom is consistent.

If the negation of what Gödel has shown had been proved, i.e. if, for each U, either U or –U is provable, then we should have an immediate solution of the Entscheidungsproblem. For we can invent a machine K which will prove consecutively all provable formulae. Sooner or later K will reach either U or –U. If it reaches U, then we know that U is provable. If it reaches –U, then, since Z is consistent (Hilbert and Ackermann, p.65), we know that U is not provable.

Note: fixed Greek symbols March 16 2015

Added Turing quote 10/1/2015