Re: Yet another Attempt at Disproving the Halting Problem

From: Will Twentyman (wtwentyman_at_read.my.sig)
Date: 08/19/04 

Date: Thu, 19 Aug 2004 10:50:23 -0400

Peter Olcott wrote:

> "The Ghost In The Machine" <ewill@aurigae.athghost7038suus.net> wrote in message news:6j3cv1-fc4.ln1@lexi2.athghost7038suus.net...
>
>>In sci.logic, Peter Olcott
>
>
>>>It is a trivial augmentation to the basic definition of a UTM.
>>
>>An interesting requirement, but how does a UTM know that a given
>>TM implements the Halting Problem? And how does a TM call up to
>>the UTM to ask whether its thread of execution is looping?
>>
>>Standard TM machines don't *have* function calls, although they can
>>emulate them easily enough by writing something on the tape. The
>>requirement then gets translated into writing a special something
>>twice -- when the special something look like just another number.
>
> Apparently you don't have the basic idea correctly.
> All the halt analyzer asks the UTM is if there are any other
> TM's running on it. Only if the answer is NO does it even
> begin to do its halt analysis.
>
> This means that whenever Halt() sees anything like LoopIfHalts,
> it can safely say that it simply halts.

The problem is: LoopIfHalts *is* the UTM that is running Halt.
Secondly: if Halt outputs "it halts", then LoopIfHalts will see that and
not halt. 

-- 
Will Twentyman
email: wtwentyman at copper dot net

Relevant Pages