Re: Can you find anything wrong with this solution to the Halting Problem?

From: David C. Ullrich (ullrich_at_math.okstate.edu)
Date: 07/11/04 

Date: Sun, 11 Jul 2004 06:55:56 -0500

On Sat, 10 Jul 2004 15:40:48 GMT, "Peter Olcott"
<olcott@worldnet.att.net> wrote:

>Only direct refutation or confirmation of this message will
>be replied to, anything else will be considered off-topic and
>ignored.
>
>http://www.netaxs.com/people/nerp/automata/halting2.html
>I am using this as the basis of my discussion so that the
>specific constituent parts of the Halting Problem can be
>explicitly referred to by their counter-part in this example.
>>From what I understand this version of the Halting Problem
>is sufficiently analogous to the original.
>
>I am not sure that this "solution" is correct. There may be one or
>more errors or loopholes that I have failed to discover. Since the
>basic conclusion of the Halting Problem is that it is impossible
>to construct a WillHalt() function that will correctly determine
>whether or not any other program will halt or not, I have
>freely modified the other aspects of the problem definition
>to refute this single conclusion.
>
>(1) The LoopIfHalts() function can not see the screen.
>
>(2) The only access that the LoopIfHalts() function has to the
> WillHalt() function is through a function call.

Here's another way to explain what I've been trying to
say - maybe this one will get through:

Let's ignore for a second the question of why you feel
it's ok to modify the problem and then claim that the
result has something to do with the original problem.
The key point is that (1) and (2) are _not_ modifications
to the problem! They are restricitions on the way one
is allowed to give the _proof_ that the problem is
impossible.

Supposing for the sake of argument that a proof under
these restrictions was impossible, that proves nothing
whatever. Because there exists a proof _without_ these
restrictions that proves it can't be done.

One of those analogies you love: You've seen a proof
that sqrt(2) is impossible. The proof involves the
notion of even and odd numbers. You decide for some
reason to "modify the problem", declaring that the
_proof_ is not allowed to mention the words "even"
and "odd". Now suppose for the sake of argument
that it's impossible to prove that sqrt(2) is
irrational without mentioning those two words.
So what? That doesn't make sqrt(2) rational,
and in fact it doesn't even cast the slightest
doubt on _whether_ sqrt(2) is irrational.
Because the proof without the bizarre restriction
is still valid - saying "let's consider only
proofs that don't mention the words even and
odd" does not have any effect on the validity
of the proof that _does_ mention those words.

>***************************************************
>To solve the Halting Problem all that is needed is for the meaning
>of the return value from Willhalt() be kept from the LoopIfHalts()
>function. The WillHalt() function arranges a coded reply to the
>human user.
>
>It could be as simple as one and zero. The meaning of true would
>be assigned to either one or zero, the meaning of false would be
>assigned to the other. Before the program takes the input of the
>LoopIfHalts() function it outputs either a one or a zero to the
>screen. Whichever (1 or 0) is output, holds the meaning of true.
>Whichever one it outputs is generated by a hardware noise based
>random number generator. (thus it is impossible to predict which
>of these two will be generated) Now the LoopIfHalts() function
>has no way to thwart the WillHalt() function, and the human user
>can understand the result.
>***************************************************
>

************************

David C. Ullrich

Relevant Pages
Loading