Re: Can returning a value change the value itself (in the Halting Problem)

From: The Ghost In The Machine (ewill_at_aurigae.athghost7038suus.net)
Date: 08/21/04 

Date: Sat, 21 Aug 2004 08:00:20 GMT

In sci.logic, Peter Olcott
<olcott@worldnet.att.net>
 wrote
on Sat, 21 Aug 2004 03:57:11 GMT
<rKzVc.230526$OB3.129707@bgtnsc05-news.ops.worldnet.att.net>:
>
> "The Ghost In The Machine" <ewill@aurigae.athghost7038suus.net> wrote in message news:ljdgv1-p97.ln1@lexi2.athghost7038suus.net...
>> In sci.logic, Peter Olcott
>> <olcott@worldnet.att.net>
>> wrote
>> on Fri, 20 Aug 2004 02:30:12 GMT
>> <UmdVc.481023$Gx4.314007@bgtnsc04-news.ops.worldnet.att.net>:
>> >
>> > "Marc Goodman" <marc.goodman@comcast.net> wrote in message news:gf6Vc.281984$a24.37388@attbi_s03...
>> >> tom_usenet wrote:
>> >> > I assume you mean that as long as there is one theoretical halt
>> >> > analyzer that can't be proven not to work, then there is no evidence
>> >> > either way as to whether a halt analyzer can be constructed or not.
>> >>
>> >> That's my reading as well.
>> >>
>> > I do think that we can go 1/2 step further.
>> > It seems that the strongest claim that could be made of the
>> > method that I propose is that undecidability can no longer be
>> > shown to exist for the Halting Problem.
>> >
>>
>> So can you construct WillHalt() on the modified TM? (Or at
>> least an algorithmic representation thereof?)
>
> No, and neither can anyone else. At least not yet. No one
> has even tried because it was "known" to be impossible.
> Now that undecidability has been refuted people may again
> to begin to work on this no longer hopeless cause.

You have proven that it's possible. However, because skeptics
(like me) abound you should at least give us a clue as to how one
might construct this, at a high level. Obviously the general
TM construction methods can be refined later, and perhaps
even coded into a computer.

Of course you can forestall criticism easily enough by embarking
on a years-long research program for developing a Halting Solver.
You've identified some of the characteristics already:

[1] It must not output to an instance of itself, by monitoring
    its own context.
[2] It must be able to detect an instance of itself inside of a
    test machine.
[3] It cannot be observed by another machine.

So go for it. It should now be fairly simple. :-)

>
>> If you can, please do so, and post the results on www.halting-problem.com.
>>
>> --
>> #191, ewill3@earthlink.net
>> It's still legal to go .sigless.
>
> 

-- 
#191, ewill3@earthlink.net
It's still legal to go .sigless.

Relevant Pages