Re: What is the Result from Invoking this Halt Function?

From: Acme Diagnostics (LFinezapthis_at_partpostmark.net)
Date: 08/09/04 

Date: 8 Aug 2004 21:40:17 -0500

">parr\(*>" <gniKyruaL@tenretnitb.moc> wrote:
>"Acme Diagnostics" <LFinezapthis@partpostmark.net> wrote in message
>news:4113c167$0$10272$45beb828@newscene.com...
>>
>> Is there any *linkable* proof of the Halting Problem for a computer
>> language that does not contrive a logic paradox and require
>> self-reference to make the proof?

<snip>

>Anyway, I think this is what Kent is saying:

> The halting problem starts from an implicit
> position of self-reference. A halt detecting
> computer program has to deal with any possible
> program, including itself and any program which
> contains copies of itself.

Well, since you and Kent seem to think I have some doubt about
the proof, let me explain how I reason just the opposite. I see the
proof "for a computer program" as composed of two parts:

1. A simple universal affirmative proposition. I see Kent's "any" or
"infinite," and your "any possible" and the traditional "any arbitrary"
as all equivalent to the classical "ALL." Editing to the shortest
terms which I can still inference into the detail, I get:

True or False? ALL program/input combinations ARE halt decidable.
(Same as: True or False? ALL crows ARE black.)

2. The counter-example which is called the Halting Problem proof.
(Same as: One albino crow.)

It doesn't matter to me if the one counter-example is contrived,
paradoxical, self-referential, genetically engineered, or spray
painted. One counter-example is logically *sufficient* to prove a
universal proposition logically *false*. It is unassailable, and as far
as I am concerned, now and forever, that was the *end* of that
story before Olcott ever showed up (as everyone has pointed out
ad nauseum).

Also, to avoid another confusion, I should say that I consider all
terms below equally applicable to the falsification of a universal by
counter-example:

Proof by contradition (Not my favorite, possibly ambiguous)
Proof by exception (I hear it a lot.)
Proof by counter-example (Probably most universally understood)
Proof by contrary-case (I've used it once in a while.)
Reductio Ad Absurdum (Nice for being theatrical!)
Proof by falsification (Scientists like it.)
Larry's "X=" (aka "It is what it is." - to defeat obfuscation)

> As only one proof is
> needed, e.g. the contradiction approach, why
> look for more?

To better define the problem for real-world application. I've posted
this before, and thought it would be unambiguous. Sorry it wasn't.

>The diagonalisation approach, as described in the page you
>referenced, is a second way.

Yes, but I had explicitly factored that out of my question for the
the reason that is now probably apparent.

I am not really confused about this distinction between TM's and
real computers. I'm aware of Sloman's paper on parallel development of
computers, for instance. (And agree with it.)

>I can conceive a third way and that is to set the halt detecting
>program to work on an algorithm which is attempting to solve a
>problem known to be indeterminate

I did read two PDF docs on Hilbert's 10th problem. Most of it flew way
over my head, but I could probably understand that one specific problem
if I did a bunch of work. I also noticed references to the Halting
problem. But I didn't stumble upon what I could recognize as a proof of
the halting problem "for a computer program."

In any case, we may need to give Chris Menzel credit for possibly
already providing an example of an indeterminate problem also having to
do with integer math. This was in response to the first time I posted
the question a while back. But he did not call it a proof or even a
possible proof (or anything at all for that matter).

I posted a little trivial example solver in that post which I will
link. Please ignore at least two speed errors and one design error, as
there was some theatrical context and newsgroup intrigue of which
you are unaware, nothing serious. Anyway, it works as advertised and
may suffice as a good simplification if we imagine an unlimited number
of bytes for all the variables. Also, ignore everything after the GFA
program (about the super-computer):

http://www.google.com/groups?selm=40f1e64c$0$92951$45beb828@newscene.com

The line "IF Q>1.4142135623 AND Q<1.4142135624 THEN" is unnecessary and
only to make a short output for that post.

I can't say if that problem is indeterminate, and I am still too lazy
to google it, but I don't think Chris would have posted it if it
wasn't.

Could a program decide if this example halts? Well, it may loop
forever, so it seems not. Either way, is there a way to tell without
running it in "interpretive mode" which Kent calls illegal in context
of the Halting Problem proof?

>It depends what you want this third approach for. If it's to place
>in front of Peter,

I see that obvious inference; however that's a definite no. Olcott is
entirely factored out of my tests of fact. I suggest everyone else do
the same. Let's not avoid testing for facts out of fear of what Olcott
may do with the results.

>you already know what will happen when confronted
>with indeterminacy!

Olcott will buzz along forever with or without our help as long as
people keep replying to him in context. How much he thinks he is
right, as if indeterminacy could increase that, is not a variable in
our Olcott equation. If not indeterminacy, next I suspect he'll be
using hash tables, or an infinite variety of other devices to continue
the kook troll. But I see nothing wrong with engaging him not in
context. Entertaining, also incentive for others not to engage him in
context.

Thanks for the example. I can think of lots of real-world reasons why
halting is undecidable, my favorite being Alife programs (which I know
almost nothing about except that I think some can "evolve" and that
would be one hell of a loop to check) and some AI designs which have
been described (yet not demonstrated <g>), but also having handy
real-life examples on my desk which could never in a million years be
checked for infinite loops and which I do know all about. But your (and
Chris's) examples remain theoretical (I think), so are pertinent to the
question I asked, and these may possibly be applicable to an AI
problem I'm trying to define.

Larry

Relevant Pages

  • Re: What is the Result from Invoking this Halt Function?
    ... proof "for a computer program" as composed of two parts: ... The counter-example which is called the Halting Problem proof. ... running it in "interpretive mode" which Kent calls illegal in context ... however that's a definite no. Olcott is ...
    (sci.logic)
  • Re: Alan Turings Halting Problem is Incorrect (FINAL PART)
    ... > can determine if every other computer program halts. ... > everything because it can not ever solve the Halting Problem. ... > provide the rational square root of two. ...
    (sci.logic)
  • Re: Alan Turings Halting Problem is Incorrect (FINAL PART)
    ... >> can determine if every other computer program halts. ... >> in such a way that it is utterly impossible for any single entity ... >> everything because it can not ever solve the Halting Problem. ... >> provide the rational square root of two. ...
    (sci.logic)
  • Re: Peter Olcotts Source of Confusion
    ... > proof of the unsolvability of the halting problem. ... I do not accept the validity of this counter-example program. ... Besides showing that no computer program can possibly determine ... answer to the question: Does this program halt? ...
    (sci.logic)
  • Re: Alan Turings Halting Problem is Incorrect (FINAL PART)
    ... >> are or aren't provably any odd perfect numbers. ... If this is supposed to relate to the halting problem, ... since the halting problem requires that H can determine if any halts. ... > not each and every other computer program halts, ...
    (sci.logic)