Re: Yet another Attempt at Disproving the Halting Problem

From: Peter Olcott (olcott_at_worldnet.att.net)
Date: 07/30/04 

Date: Fri, 30 Jul 2004 12:26:48 GMT

"Rick Decker" <rdecker@hamilton.edu> wrote in message news:4109ABDC.1070503@hamilton.edu...

> > So it is always possible for an outside observer to correctly
> > determine whether or not any possible program will halt, or not.
> > Is this correct?
> >
> Not quite. That's not what David said. If you have a program
>
> that happens to halt, then you can verify that: just start it
> and eventually it will halt, after which time you'll know it.
> On the other hand, if you have a program that doesn't halt,
> there will never be a time at which you can assert "this
> doesn't halt." You don't, under the standard model of computation,
> have the luxury of waiting until one second after infinity.
>
> That's the difference between recursive and recursively enumerable.
>
>
> Regards,
>
> Rick "taking careful aim with the M31A6"
>
>

My question was my question. I want to know that answer to my
question, not my question in the context of some other question. It
seems to me that im each and every one of these halting problem
cases, I can see whether or not the program will halt or not, even if
the program itself can not see this.

I can see this because the halting problem can not be constructed to
effect the view of the outside observer. It can't go into any infinte loop,
or an infinte cycle based on the results of analysis that is not available
to it.

Because of this any outside observer can (in theory) solve the Halting
Problem. This is the same idea as the void WillHalt() function. We
don't have to have a void WillHalt() function, void functions are not
available in Turing Machines. We can have a separate memory space.

Relevant Pages

  • Re: Halting Problem Final Conclusion
    ... > was to detect programs that failed to halt, ... The primary benefit of a universal Halting Problem ... about programs that fail to halt. ... if this program would halt" analyzer may be as ...
    (comp.theory)
  • Re: Halting Problem Final Conclusion
    ... > was to detect programs that failed to halt, ... The primary benefit of a universal Halting Problem ... about programs that fail to halt. ... if this program would halt" analyzer may be as ...
    (sci.logic)
  • Re: The formal and informal proofs
    ... I am paid to formalize all day. ... > HALT(x,y) = List the TMs that halt. ... > possible, you have a formalization of the Halting Problem, the Every ...
    (sci.logic)
  • Re: A modern view of the halting problem
    ... program will halt. ... design of the language? ... The halting problem is not about stopping at specific instructions; ... using Riemann Hypothesis instead. ...
    (alt.lang.asm)
  • Re: What is the Result from Invoking this Halt Function?
    ... > produce a halt analyzer that returns a correct ... >> refute the definition of the Halting Problem ... (The problem of finding out whether a given Turing Machine ...
    (sci.logic)
Quantcast