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

From: Peter Olcott (olcott_at_att.net)
Date: 07/10/04 

Date: Sat, 10 Jul 2004 20:33:31 GMT

> > 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.
>
> ITYM tape. Turing machines don't have screens.

This is not relevant here. I am only directly addressing the
conclusion of the original proof. Paraphrase:

It is impossible to construct a WillHalt() function
that can correctly determine if any program will halt.
{see the above referenced link for what I mean by
the WillHalt() function() }

My tentative claim is that the methods described here
refute the conclusion of the original proof. You are
welcome to find any errors or loopholes in these
methods. There might be some errors of loopholes
that I have missed.

> As it is...how are you going to enforce keeping the return value
> of the WillHalt() function from the LoopIfHalts() program?

I don't keep the return value from the LoopIfHalts()
function. I only keep the meaning of this return value
from the LoopIfHalts() function. The WillHalt() function
always returns a one or zero.

Whether the one or the zero takes on the meaning of
true is determined by a hardware based random number
generator. This meaning is provided to the human user,
but kept from the LoopIfHalts() function. One way to
accomplish keeping this meaning from the LoopIfHalts()
function is to simply display a one or zero on the screen.
Whichever (1 or 0) is displayed is the symbol intended
to take on the meaning of true.

Sine the LoopIfHalts() program does not have access
to screen data it has no means to thwart the WillHalt()
function.

Relevant Pages
Quantcast