Halting Problem: Give up

From: Karl Heinz Buchegger (kbuchegg_at_gascad.at)
Date: 08/03/04 

Date: Tue, 03 Aug 2004 10:38:49 +0200

The following is one of latest messages of Peter in comp.lang.c++
It clearly shows that Peter still hasn't understood what the
Halting Problem is and what the Proof is and how they are connected.

I have given up hope.

Peter Olcott wrote:
>
> "Karl Heinz Buchegger" <kbuchegg@gascad.at> wrote in message news:410E3043.B8F8457D@gascad.at...
> > Peter Olcott wrote:
>
> > > > You constantly mix up the Halting Problem theorem with its proof.
> > > >
> The Halting Problem is directly derived from its proof.
> If the proof is shown to be in error, then the Halting Problem
> (which is only derived from the proof) ceases to exist.
>

> > > But the claim that the Halt function will work under all possible conditions
> > > (including smashing its computer) is not the relevant claim. The relevant
> > > claims is simply will the halt function work for every possible input? If it
> > > fails this claim then the Halting Problem continues to exist. If it passes this
> > > claim, then the Halting Problem ceases to exist. It does pass this claim.
> >
> > It does not! For the simple reason that the Halting problem will not simply
> > 'cease to exist'. The Halting Problem is a question and as such has 2 possible
> > answers: Yes or no.

> Nope. The Halting Problem is the problem of not being able to correctly determine
> if every program halts. As soon as a method is determined to circumvent the
> particular restriction, then the Halting Problem is not a problem. A problem that is
> not a problem is a problem no more.

> > The Halting problem is the question: Is there an algorithm which can correctly
> > and in a deterministic way determine if all algorithms ever come to an halt.

> That is not what has been historically referred to as the Halting Problem.
> THE Halting Problem is a much more specific case. It is the case of
> specifically showing why this is "impossible".

> > That is the question. There are 2 possible outcomes:
> > * yes
> > * no
> > Since the first one seems to be the answer which is harder to proof, Turing
> > showed that the second answer is the correct one. The proof is to construct
> > an algorithm (and the clever part is to use the testing function as part of it)
> > where this testing function is bound to fail. Thus the answer to the Halting
> > Problem is: No, there is no such algorithm. Even if we assume that there is
> > one, it turns out that it is possible to cleverly construct an algorithm which
> > cannot be correctly analyzed by this assumed algorithm.

> Except that I have just now (in another newsgroup) shown that this is not true.
> The Halt analyzer can correctly determine whether or not this cleverly
> constructed algorithm halts. Also with my latest method, it can do this
> directly within the basic capabilities of a typical Turing Machine. It needs
> no special hardware. Since the whole Halting Problem depends on this
> proof providing this clever algorithm, and the halt analyzer failing
> to correctly process this algorithm, therefore I only need to show how
> it can be correctly processed, for the proof, and therefore the Halting Problem
> itself, to evaporate. I did this.

> > You constantly mix up the claim with the proof. The function assumption
> > of WillHalt() and the construction of LoopIfHalts() is *not* the claim.
> > They are part of the proof!
> > Even if you modify the proof in such a way that you circumvent the way this

> I don't need to modify the proof, I merely show that it is in error.

> > proof works, it does not mean, that the original proof is no longer valid.
> > It is still there and serves as a perfect example of why the answer to the
> > Halting problem is still: 'No, there is no such algorithm'. 

-- 
Karl Heinz Buchegger
kbuchegg@gascad.at

Relevant Pages

  • Peter Olcotts Source of Confusion
    ... Peter Olcott is so thoroughly confused by the proof of the ... to track down exactly what the source of his confusion is. ... code for an alleged program H that solves the halting problem, ... input x, then loop forever, otherwise halt". ...
    (sci.logic)
  • Re: simple and beauty strategy
    ... the halting problem is a decision problem ... Alan Turing proved in 1936 that a general algorithm to solve the ... the program will eventually halt when run with that input. ... undecidability of a problem in the lambda calculus had already been ...
    (rec.gambling.lottery)
  • Re: Alan Turings Halting Problem is incorrectly formed
    ... Peter is mixing up several things. ... Now the question (Halting problem) actually is not "Does TM M halt on ...
    (sci.logic)
  • Re: Can you find anything wrong with this solution to the Halting Problem?
    ... Peter> LoopIfHaltswill halt. ... Peter> LoopIfHalts() does not halt, this only leaves UNKNOWN, ... have any such program that can return UNKNOWN for any valid input ... the simplest solution to the halting problem "int WillHalt(string Src, ...
    (comp.theory)
  • Re: The halting problem
    ... meanning to halt when H outputs "HALT" and loop when H " outputs ... if the halting problem were decidable, and its existence causes H to ... complete the proof is that there exists an algorithm that messes up H, ... know the mechanics of how Turing machines work to understand the ...
    (comp.theory)