Re: The proof that I was referring to is on the website

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

Date: Thu, 05 Aug 2004 12:10:25 GMT

"Matt Chaplain" <nospam@kastagaar.com> wrote in message news:5e256172.0408050257.4cf19489@posting.google.com...
> 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.
> > 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.

and it can do this for every possible input, thus invalidating this
definition of the Halting Problem.

No program can ever be written to determine whether any arbitrary
program will halt
http://www.nist.gov/dads/HTML/haltingProblem.html

> 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**.

It works for every possible input, that is sufficient. It is not required to
work under every possible condition.

>
> 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.

Relevant Pages

  • Re: The proof that I was referring to is on the website
    ... > A Halt Analyser, by the very nature of the problem, is defined as ... should the input program not halt. ... Hence it is immune to hammers, lightning strikes, ... > Analyser fails under any circumstances, it is not a Halt Analyser. ...
    (sci.logic)
  • Re: The proof that I was referring to is on the website
    ... A Halt Analyser, by the very nature of the problem, is defined as ... should the input program not 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 ...
    (sci.logic)
  • Re: The proof that I was referring to is on the website
    ... A Halt Analyser, by the very nature of the problem, is defined as ... should the input program not 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 ...
    (comp.theory)
  • Re: The proof that I was referring to is on the website
    ... >> A Halt Analyser, by the very nature of the problem, is defined as ... should the input program not halt. ...
    (comp.theory)