Re: Olcott is cured of CrackPottery! (Halting Problem)

From: Charlie-Boo (chvol_at_aol.com)
Date: 09/24/04 

Date: 24 Sep 2004 10:45:15 -0700

dmarx@cs.bme.hu.nospam (Daniel Marx) wrote
> On 23 Sep 2004 20:00:40 -0700, chvol@aol.com (Charlie-Boo) wrote:

> >PS Yes, it is easy to explain - even formalize as I have done -
> >Turing's proof. However, poor Gregory Chaitin still hasn't gotten it
> >straight. In "Computers, Paradoxes and the Foundations of
> >Mathematics", page 5, Chaitin writes, [
> >http://www.cs.auckland.ac.nz/CDMTCS/chaitin/amsci.pdf ]
> >
> >"Let me outline Turing's reasoning: Suppose that you could write a
> >computer program that checks whether any given computer program
> >eventually halts. Now create a second program that uses the
> >termination tester to evaluate some program. If the program under
> >investigation terminates, have your new program go into an infinite
> >loop. Here comes the subtle part: Feed the new program a copy of
> >itself. What does it do? Remember, you've written this new program
> >so that it will go into an infinite loop if the program under test
> >terminates. But here it is itself the program under test. So if it
> >terminates, it goes off in an infinite loop - a contradiction."
> >
> >What does it do, he asks? The true answer is "Nothing.", because you
> >haven't given your second program the input that goes along with the
> >program you've given it (itself.) Turing's second program doesn't
> >tell if its input program halts and do the opposite. It determines
> >whether the input run against itself halts, and does the opposite of
> >that. Chaitin messed up "the subtle part". He didn't set up the self
> >reference right.
> >
> >And that's after writing about it for 30 years!
>
> That paper appears to be a popular science article, so consider the
> possibility that maybe he is intentionally skipping some details.

To save space he left out 3 words that explain how Turing's proof
actually does work?

If all that was wrong was that detail was missing, the remaining
statements would be true, which is not the case here.

What prevents that reasoning from declaring that any false statement
simply lacks details?

What additional "detail" makes his statements true?

> If we interpret "eventually halts" as "eventually halts for every
> input," then the argument actually works.

So you admit that the argument as stated by Chaitin does not work?
But neither does it work with your interpretation. If you think so,
then give the argument here.

Since some programs do in fact halt on all inputs and others do not,
the given "second" program will sometimes halt and sometimes not.
Then it does not halt on all inputs, * so that it would halt on
itself. But that is no contradiction, as perhaps itself is one of the
inputs on which it does halt. Where is the contradiction?

The 4 rules become:

(aA)HALT(a,A) => YES(P,a) (1) If a halts on all inputs, then my
program P halts
YES.
~(aA)HALT(a,A) => NO(P,a) (2) If a does not halt on all inputs, then
my program P halts NO.

(aA)HALT(a,A) => ~HALT(M,a) (3) M loops if a halts on all inputs.
~(aA)HALT(a,A) => NO(M,a) (4) M halts NO if a does not halt on all
inputs.

Then by substitution for a we get:

(aA)HALT(P,A) => YES(P,P)
~(aA)HALT(P,A) => NO(P,P)
(aA)HALT(M,A) => ~HALT(M,M)
~(aA)HALT(M,A) => NO(M,M)

and by substituting for A we get:

(aA)HALT(P,A) => HALT(P,P) ^ YES(P,P)
(aA)HALT(M,A) => HALT(M,M) ^ ~HALT(M,M) => FALSE

>From this we can only conclude that ~(aA)HALT(M,A) (which I observed *
above.)

C-B

> Daniel Marx

PS Why does Chaitin talk endlessly about improving Godel's 1st Theorem
(which he says he learned as a child) but never mentions Godel's own
extension using w-consistency or Rosser's improvement that premises
only consistency?

Relevant Pages

  • Re: Olcott is cured of CrackPottery! (Halting Problem)
    ... >>computer program that checks whether any given computer program ... >>investigation terminates, have your new program go into an infinite ... >>tell if its input program halts and do the opposite. ... So you admit that the argument as stated by Chaitin does not work? ...
    (comp.theory)
  • Re: Alan Turings Halting Problem is Incorrect (FINAL PART)
    ... : Peter Olcott says... ... :>>> Its basically asking a computer program to determine whether or ... :>>> not each and every other computer program halts, ... :>>> provide the correct answer of whether or not it halts. ...
    (sci.logic)
  • Re: Random data cannot be compressed
    ... impossible to tell if a TM halts. ... And to determine if *that* one terminates... ... take more time than has existed or will exist in this universe. ... ever-increasing amount of time -- to compute whether an FSA halts. ...
    (comp.lang.lisp)
  • Re: Alan Turings Halting Problem is Incorrect (FINAL PART)
    ... >> are or aren't provably any odd perfect numbers. ... If this is supposed to relate to the halting problem, ... since the halting problem requires that H can determine if any halts. ... > not each and every other computer program halts, ...
    (sci.logic)
  • Re: Alan Turings Halting Problem is Incorrect (FINAL PART)
    ... [George Greene writes] ... >not each and every other computer program halts, ... you go around showing what's wrong with the proof of the unsolvability ...
    (sci.logic)