proof of theorem 11.3 (Godel Incompleteness on HALTONZERO)

[l0g2]

proof of theorem 11.3 (in section 11.2) is WRONG. A right proof as follows:

Let ALL = all turing machines H = {M | M is a turing machine and M(0) does NOT halt}

Suppose algorithm V: ALL × {0,1}* -> {0,1} satisfy:

1. (Effective) for any x in ALL, for any w in {0,1}*, V(x,w) halts,
2. (Sound) for any x in ALL-H, for any w in {0,1}*, V(x,w) outputs 0,
3. (Complete) for any x in H, exists w in {0,1}*, V(x,w) outputs 1.

We build an algorithm A: ALL -> {0,1} as follows: Input: a turing machine M Performs the following two tasks in PARALLEL:

1. check every w in {0,1}*, if V(M,w)=1, then return 0,
2. simulate M(0), if halts, then return 1.

Here A computes HALTONZERO, contradiction, that completes proof.