Re: Olcott is cured of CrackPottery! (Halting Problem)

From: Charlie-Boo (chvol_at_aol.com)
Date: 09/24/04

  • Next message: LarryLard: "Re: Another set with cardinality |Z|" 
    Date: 23 Sep 2004 20:00:40 -0700

    mtx014@linux.services.coventry.ac.uk (Robert Low) wrote
    > Charlie-Boo <chvol@aol.com> wrote:
    > >3. Incomplete or inconsistent specs.
    > >Come to think of it, the halting problem (and Godel's Incompleteness
    > >Theorem et. al.) is just a case of # 3. Ho hum.
    >
    > Except, of course, that it isn't. The specification "f is a
    > function which takes a TM description and an input tape, and
    > returns 1 if the TM halts on the input and 0 if it does
    > not" is neither incomplete nor inconsistent. It just happens
    > to be a function that cannot be computed by a TM. Proving
    > that is not so "ho hum" (though it's easy once you know the
    > answer, of course).

    A horse is a horse, of course, of course.
    http://www.bussongs.com/songs/a_horse_is_a_horse_mr_ed_tv_show.php
    That is, of course, unless . . . you're wrong. You miss subtleties of
    programming that only an experienced programmer (such as myself) would
    appreciate. Consider, for example, the following innocent looking
    rules proposed as "specs":

    A. There is a routine for entering in the type of transaction.
    B. If the type of transaction is greater than 1, then the system
    writes "yes" and then halts.
    C. If the type of transaction is less than 3, then the system writes
    "no" and then halts.

    The experienced programmer knows to try out cases to see if the specs
    are valid for each one. So consider the case where the input type of
    transaction is 2. Rule B says to write "yes" while rule C says to
    write only "no". These innocent looking rules are actually
    inconsistent!

    Now for the problem at hand. No, the definition of the function is
    not incomplete or inconsistent. That's not where the problem lies, of
    course. The problem, as I've tried to explain, is in the
    specification of what the program is supposed to do.

    Define two-place relations (here and forever) YES, NO and HALT to mean
    that TM a run with input b halts yes, or halts no, or halts,
    respectively. Let the program that I am to write be P and its input
    to test if TM a halts on input b be ab. Then the specs say that we
    have two rules:

    HALT(a,b) => YES(P,ab) (1) If a halts on b, then my program P halts
    YES.
    ~HALT(a,b) => NO(P,ab) (2) If a does not halt on b, then my program P
    halts NO.

    Now define M to be the program resulting from taking a copy of P and
    (1) changing the second read to use a copy of the value of the first
    read, and (2) changing every Halt YES to a LOOP command.

    So our program P must be such that when M is fed a value a, it uses a
    for both inputs to program P, then LOOPs if a would halt on a, and
    halts NO if a would not halt on a. Thus our program must also meet
    the following two rules:

    HALT(a,a) => ~HALT(M,a) (3)M loops if a halts on a.
    ~HALT(a,a) => NO(M,a) (4)M halts NO if a does not halt on a. [same as
    P Rule 2]

    Now, the case that we examine to attempt to verify or refute these
    specs is the case where the user enters in M for both inputs into my
    new program P. Now consider the case where M halts on an input of M,
    i.e., HALT(M,M). Then by rule (1) where a=M and b=M program P must
    halt YES. However, by rule (3), if HALT(M,M) then ~HALT(M,M) [which
    really simply tells us that ~HALT(M,M)] and by rule (2) where a=M and
    n=M we have that P halts NO.

    Thus if the user enters in M for the two inputs and M halts on M, my
    program is supposed to both halt yes and halt no. The specs are
    inconsistent! Now, we might say that this never happens and it is ok
    for specs to not mention why apparent inconsistencies don't actually
    occur, but that doesn't fix the problem. For, consider the other
    case: M does not halt on M. What do the specs say to do then? Well,
    if M does not halt on M, then Rule (2) where a=M and b=M says that my
    program P should halt NO. However, rule (4) where a=M says that M
    would halt NO on M, so that M on M would halt and rule (1) where a=M
    and b=M tells me that my program P should then halt YES!

    So, whether program M with input M halts or not, the specs are
    inconsistent as to what my program should do.

    As far as Godel's Incompleteness Theorems go, the fact that the
    complement of a recursive set is partially decidable allows us to
    construct program M from P above. (If the halting set HALT(a,b) is
    recursive then programs P and M exist.)

    This is equivalent to saying that for any wff w such that:

            |- w(a) <=> ~ |- ~ w(a)

    there is a wff v(a) such that:

            |- ~w(a) <=> |- ~v(a)

    and: ~ |- v(a)

    for all values of a. (Wff w is any program e.g. P that represents a
    recursive set and thus always halts YES or halts NO, so that it halts
    YES iff it doesn't halt NO, i.e., we can prove w(a) iff we cannot
    prove ~w(a). Wff v is program M which still halts NO if P does, i.e.,
    we can prove ~v(a) just when we can prove ~w(a), but M loops if P
    halts yes, i.e., we cannot prove v(a).

    How can we construct a wff v given any such wff w? That is left as an
    exercise. Hint: Let G be any undecidable (neither provable nor
    refutable) sentence. What functions of w and G satisfy v?

    C-B

    PS Yes, it is easy to explain - even formalize as I have done -
    Turing's proof. However, poor Gregory Chaitin still hasn't gotten it
    straight. In "Computers, Paradoxes and the Foundations of
    Mathematics", page 5, Chaitin writes, [
    http://www.cs.auckland.ac.nz/CDMTCS/chaitin/amsci.pdf ]

    "Let me outline Turing's reasoning: Suppose that you could write a
    computer program that checks whether any given computer program
    eventually halts. Now create a second program that uses the
    termination tester to evaluate some program. If the program under
    investigation terminates, have your new program go into an infinite
    loop. Here comes the subtle part: Feed the new program a copy of
    itself. What does it do? Remember, you've written this new program
    so that it will go into an infinite loop if the program under test
    terminates. But here it is itself the program under test. So if it
    terminates, it goes off in an infinite loop - a contradiction."

    What does it do, he asks? The true answer is "Nothing.", because you
    haven't given your second program the input that goes along with the
    program you've given it (itself.) Turing's second program doesn't
    tell if its input program halts and do the opposite. It determines
    whether the input run against itself halts, and does the opposite of
    that. Chaitin messed up "the subtle part". He didn't set up the self
    reference right.

    And that's after writing about it for 30 years!

  • Next message: LarryLard: "Re: Another set with cardinality |Z|"

    Relevant Pages