Re: Foundation for a Formal Refutation of the Original Halting Problem?

From: Peter Olcott (olcott_at_worldnet.att.net)
Date: 08/03/04 

Date: Tue, 03 Aug 2004 00:47:13 GMT

"Daryl McCullough" <daryl@atc-nycorp.com> wrote in message news:celmqg02rtm@drn.newsguy.com...
> Peter Olcott says...
>
> Peter, there is no better proof that you are an incompetent than
> the fact that, after all this time, you haven't even understood
> Turing's counterexample:
>
> You wrote:
>
> >01) int WillHalt(string SourceCode, string DataInput)
> >02) {
> >03) if (TheProgramHalts(SourceCode, DataInput))
> >04) return 1; // also means true in C/C++
> >05) else
> >06) return 0; // also means false in C/C++
> >07) }
> >
> >08) void LoopIfHalts(string SourceCode, string DataInput)
> >09) {
> >10) if (WillHalt(SourceCode, DataInput))
> >11) while(true)
> >12) ;
> >13) else
> >14) return;
> >15) }
> >
> >16) cout << WillHalt(LoopIfHalts, LoopIfHalts);
>
> That is just plain wrong. Note that LoopIfHalts takes *two*
> arguments as inputs. You've only supplied *one* argument. So
> running WillHalt(LoopIfHalts, LoopIfHalts) will produce an
> error.

This error does not effect my basic reasoning.
So simply make WillHalt take a variable number of arguments
two or more.

16) cout << WillHalt(LoopIfHalts, LoopIfHalts, LoopIfHalts);

> Somehow, after all this time, you *still* don't understand
> Turing's proof. The way Turing's proof works is this: (reworded
> to correspond to your terminology)
>
> WillHalt(M,x): is assumed to return "true" if M halts on input x,
> and returns "false" otherwise

I adapted this from another's work, using 1 and 0 are synonymous.

> Note: this *only* makes sense if M is a program with *one* argument.
> If M is a program with more than one argument (or zero arguments)
> then WillHalt(M,x) is ill-defined. You can, perhaps, specify that
> WillHalt(M,x) returns false or an error in that case.
>
> To show that WillHalt can't exist, you construct a new program
> LoopIfHalts(M). This program has only *one* argument (and so it
> is a program that can be analyzed by WillHalt).
>
> LoopIfHalts(M): if WillHalt(M,M) loop forever, otherwise halt
>
> Now, consider the two different computations:
>
> 1. WillHalt(LoopIfHalts,LoopIfHalts)
> 2. LoopIfHalts(LoopIfHalts)
>
> By definition of WillHalt, the first computation should halt and
> return true if and only if the second computation halts. But by
> definition of LoopIfHalts, the second computation should halt if
> and only if the first computation returns false. This is a contradiction.

I have already resolved this, see my 6:41 posting.

> Your way around this is to say that WillHalt(LoopIfHalts,LoopIfHalts)
> returns one value if called from within LoopIfHalts, and returns a
> different value if it is called in isolation. But that means that *one*
> of those two return values is wrong. Either the value returned to
> LoopIfHalts is wrong, or the value returned by WillHalt in isolation
> is wrong. In either case, WillHalt must give the wrong answer in some
> case, and so WillHalt is *not* a solution to the halting problem.
>
> --
> Daryl McCullough
> Ithaca, NY
>

Relevant Pages
Loading