Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!wuarchive!uunet!mstan!sethb
From: sethb@Morgan.COM (Seth Breidbart)
Newsgroups: comp.theory
Subject: Re: Question on halting problem
Keywords: recursive
Message-ID: <3177@ylum.Morgan.COM>
Date: 3 May 91 00:52:20 GMT
References: <18974@crdgw1.crd.ge.com> <4760@osc.COM> <7277@rex.cs.tulane.edu>
Organization: Morgan Stanley, & Co., Inc. / New York City, NY
Lines: 36

In article <7277@rex.cs.tulane.edu> fs@caesar.cs.tulane.edu (Frank
Silbermann) asks:

>We have concluded that the halting problem
>is decidable for any specific input-free program P.
>
>Proof:
>Consider algorithms A & B such that
>algorithm A reads in a program and returns YES;
>algorithm B reads in a program and returns NO.
>One of these algorithms solves the halting problem for P.
>
>Is there any program P for which it has been proven that
>we can never know which of these two algorithms, A and B,
>is the right one?

It depends on what you mean by "proven".  If you specify the formal
system in advance, then I can construct such a machine:  Pick a random
string whose length is longer than the description of the system.  Set
a machine to testing whether that string is random, to halt if it
determines that the string is not random, to loop forever if it cannot
so determine.  Since, in any formal system, there is an upper limit to
the length of any string that can be proven random, this machine will
not halt.  But a proof that it will not halt is a proof that the
string is random.

"Random" is used in the algorithmic sense, as described by Chaitin.

On the other hand, the answer is "no".  If the machine will halt, then
that can obviously be proven.  If it will not halt, then add as an
axiom "that machine does not halt".  The new system is consistent, and
the non-halting of the machine is easy to prove in that system.  In
fact, we see that if the halting of the machine is unprovable, it
cannot halt.

Seth		sethb@fid.morgan.com