Re: Yet another Attempt at Disproving the Halting Problem

From: Kent Paul Dolan (xanthian_at_well.com)
Date: 07/30/04 

Date: Fri, 30 Jul 2004 15:59:02 +0000 (UTC)

"Peter Olcott" <olcott@worldnet.att.net> wrote:

> It seems to me that [in] 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.

Bully for you.

However, the statement of The Halting Problem is
_not_:

    It is possible to construct a single, unique
    Peter Olcott such that for every Turing Machine
    "TM", the Peter Olcott we have constructed,
    given that "TM" and that "w" in a fashion
    appropriate to the formal definition of a Peter
    Olcott, can correctly predict, emitting exactly
    one of the two values "True" or "False" (however
    encoded), and do so in finite time, whether that
    TM will halt when run on that input data string
    "w".

Instead, the statement of the Halting Problem is
something much closer to (and forgive the mess that
attempting to anticipate, based on your past
idiocies, all the ways you will attempt to do this
incorrectly, and cutting you off at the pass before
you make those attempts, creates from what should be
an equally simple formulation, and is, in
environments where computationally competent people
converse) this:

    It is possible to construct a single, unique
    Turing Machine "TmThatSolvesTheHaltingProblem"
    such that for _every_ Turing Machine "TM"

        (sensibly programmed or not doesn't matter,
        it just has to be a Turing Machine meeting
        the formal definition of what constitutes a
        Turing Machine, in particular supporting a
        "halt" state, it is permitted to be utter
        rubbish past that single requirement that
        it _be_ a Turing machine)

        [and notice that
        "TmThatSolvesTheHaltingProblem" is such a
        Turing Machine, so feeding it to itself
        explicitly IS within the rules, as feeding a
        TM that contains
        "TmThatSolvesTheHaltingProblem" as a
        subroutine explicitly IS within the rules],

    and every possible string of input data "w" to
    that TM

        (meaningful or not, just a string in the set
        of input symbols that "TM" is designed to
        process, it can be utter rubbish past that
        single requirement)

        [and notice that "w" can be an appropriate
        encoding of "TmThatSolvesTheHaltingProblem"
        or of some TM that includes
        "TmThatSolvesTheHaltingProblem" as a
        subroutine, that explicitly IS within the
        rules],

    the "TmThatSolvesTheHaltingProblem" we
    have constructed, given that "TM" and that "w"
    in a fashion appropriate to the formal
    definition of a Turing Machine, can correctly
    predict, emitting exactly one of the two values
    "True" or "False" (however encoded), and do so
    in finite time, whether that TM will halt when
    run on that input data string "w", or will not
    halt (and therefore will loop forever).

Notice that to prevent an infinite recursion on the
number of different of tape symbols required, it is
conventional to limit them to zero, one, blank, and
perhaps some "beginning of tape" marker; it is well
known that such a symbol set suffices to encode a
Turing machine and its data set.

Notice extremely carefully, because there are lots
of attempts to solve The Halting Problem that end up
having tried this incorrect approach in some well
disguised way, that the requirement for finishing in
a finite time explicitly _excludes_ as a candidate
implementation of "TmThatSolvesTheHaltingProblem" an
implementation that runs "TM" on "w" in
_interpretive mode_ to "see what happens" and then
returns "True" for "the interpretive mode test of
'TM' on 'w' halted" or "False" for "the interpretive
mode test of 'TM' on 'w' looped forever", since the
second case explicitly won't return its result in
finite time.

It is, [modulo my dodgy ability to write correct
formal English text expressing a formal mathematical
requirement in a comprehensibly informal way], _that
precise claim_ which Alan Turing proved to be
unsatisfiable by any single Turing Machine
"TmThatSolvesTheHaltingProblem", and your challenge,
that Turing was incorrect in his proof, unless it
addresses the proof of correctness of_that precise
claim_, is and will forever remain meaningless
drivel that makes you a subject of constant
derision, rather than gaining you the undeserved
fame and adulation you seek.

This has been the error of all your attempts to
date, not a single one of which has limited itself
to the problem Turing proved unsolvable, but instead
have wandered over hill and dale, blundering through
thickets comprised of some other problems entirely,
like some drunk seeking his home on an island not
his native land, and where he never had a home.

_Try_, despite your utter incompetence for the task,
to comprehend the big picture here and not get
distracted by some bit of trivia I may have
miswritten.

Consider it a test of your manhood to do so.

HTH

xanthian. 

-- 
Posted via Mailgate.ORG Server - http://www.Mailgate.ORG

Relevant Pages