Re: [PO] Halting Problem Final Conclusion

From: Tim Peters (tim.one_at_comcast.net)
Date: 09/08/04

  • Next message: Isaac To: "Re: Olcott is cured of CrackPottery! (Halting Problem)" 
    Date: Tue, 7 Sep 2004 21:55:02 -0400

    [Peter Olcott]
    >>> The Liar Paradox can be shown to be nothing more than
    >>> a incorrectly formed statement because of its pathological
    >>> self-reference.

    [Tim Peters]
    >> I think that's true.

    [George Greene]
    > Well, I don't.

    It's possible that's because you're responding to what Peter wrote instead
    of to what he meant <0.5 wink>. That is, I'm sure you take well-formedness
    to be a syntactic (or maybe in this context, also grammatical) property.
    But I don't expect Peter to use technical terms correctly, and don't see
    much point to going on about that.

    In context, he means there's "something fishy" about the Liar Paradox, and I
    agree that there is. It bears all the signs of a cheap trick. If he can
    challenge his intuition that a cheap trick necessarily also powers the
    unsolvability of the halting problem, that would be a bit of progress.

    > "This sentence is true" is every bit as well-
    > or ill-formed, and every bit as self-referential,
    > as "This sentence is not true",

    That's true. I'd say it's well-formed, but senseless.

    > but it is not the least bit paradoxical.

    But I think "This sentence is true." is exactly as senseless as "This
    sentence is false.", which are in turn as senseless as "If this sentence
    were a color, it would be more aqua than orange.".

    > And in point of fact, both the paradoxicality of
    > the Liar sentence and the non-paradoxicality of
    > its "denial" are determinable PRECISELY in virtue
    > of the fact that BOTH sentences are so very WELL-
    > formed. If they were in fact ill-formed, they would
    > be HARD (as opposed to trivial) to classify.

    Ya, ya. Senselessness of informal English remains hard to define crisply,
    though, and it's highly paradoxical to me that anyone could believe that
    "This sentence is true." *means* something <wink>.

    ...

    >> Read the books you ordered, and maybe one will spell out other proofs.

    > No, DON'T do that. Read Mates or Jeffrey and Boolos and
    > LEARN WHAT FIRST-ORDER LOGIC IS. In particular, learn how
    > to prove universally quantified first-order statements, and
    > stop importing bull*** from Perry Mason like "proving a negative
    > is hard".

    That would sure be a help!

    >> In recent times, Chaitin gave what I think is a particularly
    >> informative proof, showing the impossibility of solving the halting
    >> problem as a consequence *of* the impossibility of an effective
    >> procedure for determining whether an arbitrary program P is the
    >> *smallest* program that produces the same output as P.

    > Peter Olcott wouldn't understand that proof, either,
    > ESPECIALLY if it is indirect.

    I don't know that. Chaitin is an accomplished programmer, and Peter's
    intuitions come more from programming than from training in logic <doh>. A
    Turing machine isn't a good formalism for someone whose only experience in
    these areas is programming C++ -- a TM's repertoire is too numblingly feeble
    for them to live with, and so we suffer an endless succession of gimmicks to
    extend the TM model in some way. Chaitin is notorious for writing actual
    programs (in his own dialect of LISP) to make his results concrete. I don't
    know why he bothers with that, but it may resonate with the programmer in
    Peter.

    >> He proved that there are only finitely many programs P for which we
    >> can prove that P is the smallest program producing P's output.

    > PO does not believe that that proof is valid, and PO thinks he can
    > construct counter-examples, or, at the very least, "refute" some "step"
    > of that proof, showing that Chaitin hasn't really proved it.

    He may. If history is a predictor of the future, the odds sure favor it.
    But I don't think it's certain.

    ...
    >> If you persist, you'll eventually discover that, in a real sense (which
    >> can be made formal), there's no non-trivial property of program behavior
    >> that's effectively decidable. "Does it halt?" is just one of them.

    > Rice's Theorem is WAY beyond Peter Olcott.
    > Come on.

    That's shock therapy for his intuition. Of course I don't expect him to
    grasp Rice's Theorem at this point. But if he learned that his intuition
    was at least a little off, this is a good time to remind him of how far it
    may still be off, and that there's nothing inherently special about the
    halting problem in the unbounded universe of unsolvable problems. Maybe he
    won't seriously entertain the notion unless newstome tells him too, and
    that's fine. All he has to do is ask.

  • Next message: Isaac To: "Re: Olcott is cured of CrackPottery! (Halting Problem)"