Re: Yet another Attempt at Disproving the Halting Problem

From: Karl Heinz Buchegger (kbuchegg_at_gascad.at)
Date: 07/27/04 

Date: Tue, 27 Jul 2004 15:07:39 +0200

Peter Olcott wrote:
>
> I just posted a detailed explanation to in my immediately prior post.
> Basically my contention is that the conclusion does not logically
> follow from the proof. It looks like every proof only applies the
> corrupted version to itself. When the original uncorrupted version
> is applied to any other TM (including the corrupted one), the result
> is conclusive rather than undecidable. Thus Turing did not prove
> that solving the Halting Problem is impossible, only that there is
> one way to try to solve it, that does not always work.

You did not understand the proofing idea this proof is based on.
In this type of proof you really don't want to solve anything.
You assume that it is already solved (in this case: you assume
that there is a function WillHalt() that works) and use that
assumption to turn it against itself.

infinte amount of Prime numbers

  assume there is a border such that no numbers bigger then that
  border are prime.

  use that border to construct a number which is
    a) greater then the border
    b) prime

  -> conclusion: No such border can exist

Halting problem

  assume there is a working function WillHalt()

  Using that function WillHalt(), construct a function
  which uses the result of WillHalt() in such a way that
  inconsistent results are obtained.

  -> conclusion: No such function can exist.

Also note: in the case of the Halting problem we are not interested
in a WillHalt function() that works most of the time. In fact such
things can be done, no problem. The Halting problem is about a function
wich works *always*, and it is the nature of for-all theorems that one
single counter example is enough to make them false.

See also:
http://en.wikipedia.org/wiki/Halting_problem
http://en.wikipedia.org/wiki/Reductio_ad_absurdum 

-- 
Karl Heinz Buchegger
kbuchegg@gascad.at

Relevant Pages