Re: The proof that I was referring to is on the website
From: Matt Chaplain (nospam_at_kastagaar.com)
Date: 08/05/04
- Next message: Mitch Harris: "Re: Yet another Attempt at Disproving the Halting Problem"
- Previous message: David C. Ullrich: "Re: Foundation for a Formal Refutation of the Original Halting Problem?"
- In reply to: Peter Olcott: "Re: The proof that I was referring to is on the website"
- Next in thread: Peter Olcott: "Re: The proof that I was referring to is on the website"
- Reply: Peter Olcott: "Re: The proof that I was referring to is on the website"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: 5 Aug 2004 03:57:26 -0700
I've been following this for a couple of weeks now, after its debut on
comp.lang.c++. Very interesting. I've learned a lot from this
discussion.
"Peter Olcott" <olcott@worldnet.att.net> wrote in message news:<fReQc.174382$OB3.174244@bgtnsc05-news.ops.worldnet.att.net>...
> "Rick Decker" <rdecker@hamilton.edu> wrote in message news:4110E973.6010605@hamilton.edu...
>
> > > The (hopefully now obvious) answer to this question is no.
> > > The key point here is whatever answer it provides (or refrains
> > > from providing) in any of these possible cases, it can correctly
> > > determine the correct halting status for every possible TM.
> > >
> >
> > You must be aware that halts(s, d) CANNOT "refrain from providing"
> > an answer. It has to answer "true" or "false" as long as s is
> > the description of a TM. If halts doesn't answer in some case,
> > it's not a halt analyzer and we're done, having proved once
> > again the undecidability of the halting problem.
>
> It still works for all possible inputs. It is not required to work
> under all possible conditions, only all possible inputs. The constraint
> that you have suggested is merely an artificial contrivance.
I think what the lads are trying to say is that a function, when run,
may do one of four things:
1) Return true
2) Return false
3) Return something else
4) Not return.
A Halt Analyser, by the very nature of the problem, is defined as
correctly returning true, should an input program halt, or correctly
returning false, should the input program not halt. These are its
only valid responses.
>From this we deduce:
5) Since a Halt Analyser MUST do 1) or 2), which are mutually
exclusive with 3) and 4), **anything that performs 3) or 4) is by
definition NOT a Halt Analyser**.
The proof then defines a further function, D, which is trivially
implementable as a Turing Machine (thus removing it from contention as
any "problems in the problem") that uses a hypothetical Halt Analyser.
Note that, by the very definition of Halt Analyser, it MUST work in
all circumstances. Hence it is immune to hammers, lightning strikes,
alien abductions and acts of dog.
By the very definition of a Halt Analyser, if your hypothetical Halt
Analyser fails under any circumstances, it is not a Halt Analyser.
Trade it in for a new, working version that is immune to whatever
caused it to fail.
The problem is that, given this function D (which has been described
many times, so I wont describe it again here), an observable
phenomenon is that, when running the very same Halt Analyser on THIS
program, while it can perform 1) or 2), neither response is actually
correct. By 5), it's not ALLOWED to perfom 3) or 4).
Since a Halt Analyzer MUST, in all circumstances, be able to do 1) or
2) correctly, and yet cannot,
6) It does not exist.
QED.
- Next message: Mitch Harris: "Re: Yet another Attempt at Disproving the Halting Problem"
- Previous message: David C. Ullrich: "Re: Foundation for a Formal Refutation of the Original Halting Problem?"
- In reply to: Peter Olcott: "Re: The proof that I was referring to is on the website"
- Next in thread: Peter Olcott: "Re: The proof that I was referring to is on the website"
- Reply: Peter Olcott: "Re: The proof that I was referring to is on the website"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
