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

From: Mitch Harris (harrisq_at_tcs.inf.tu-dresden.de)
Date: 08/04/04 

Date: Wed, 04 Aug 2004 09:24:01 +0200

Peter Olcott wrote:
>
> A program that halts iff it goes into an infinite loop or goes into
> an infinite loop iff it halts is not one of them.
>
> A program that can correctly determine if the set of all programs
> (or TM's) will halt is one of them. (as least as far as the proof that
> it can't be done is concerned).

To me, this sounds like you -got- it. You finally
understand. Such a program is in effect non-existent.

Now for the next step. Because this program (Diag or
LoopIfHalts) doesn't exist, but it was constructed in a
legal manner. then some component of it must also not exist.
The only assumed component was Halt(M,w). Therefore, it is
this component that causes the problem. The assumption of
the existence of Halt(M,w) must be wrong. So, Halt(M,w)
doesn't exist. QED.

Can we break out the champagne now? 

-- 
Mitch Harris
(remove q to reply)

Relevant Pages