Re: Yet another Attempt at Disproving the Halting Problem

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

  • Next message: Pete Becker: "Re: A simple way to track available memory in C/C++ and why is there so many different types of it?" 
    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
  • Next message: Pete Becker: "Re: A simple way to track available memory in C/C++ and why is there so many different types of it?"

    Relevant Pages