Re: Can a regular Turing Machine provide Protected Memory?

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

Date: Sat, 28 Aug 2004 09:28:55 -0400

Peter Olcott wrote:

> "Will Twentyman" <wtwentyman@read.my.sig> wrote in message news:412f33ca_2@newsfeed.slurp.net...
>
>>Peter Olcott wrote:
>>
>>>It would seem that a regular Turing Machine would be able
>>>to provide protected memory. If we cast the problem as
>>>a regular TM that was designed as a UTM, it would seem
>>>to be able to provide Protected Memory Services to any
>>>TM that is being simulated within it. All that would be required
>>>would be for this TM to have an elemental Operating System.
>>>
>>>This operating system would allocate specific portions of its
>>>tape to specific Turing Machines being simulated within it.
>>>These separate Turing Machines could be identified by their
>>>Turing Machine Identifier (similar to a Process ID). Whenever
>>>any Turing Machine refers to any tape space, the operating
>>>system only provides access to the space that has been
>>>allocated to that specific Turing Machine. From the Turing
>>>Machine's point of view it has an infinite tape. From the Operating
>>>systems point of view, whenever the TM refers to a tape location
>>>that is outside the allocated range, the whole TM is copied to the
>>>end of its own tape, thus providing this one TM with infinite
>>>memory, until the next TM needs more room.
>>
>>Yes a UTM can run multiple TM's simultaneously. If you want them to not
>>interfere with each other, interleaving the spaces on the tape would
>>probably be simpler. So, based on the "TMIDs", you would allocate three
>>TMs space on the tape as follows: 123123123123...
>
>
> The idea here is to provide the means for the Halt Analyzer
> to have a single bit of protected memory where it stores the
> (1 or 0) meaning of TRUE. This way no other TM's can
> write to this location, or read from this location. This allows
> the Halt Analyzer to always determine whether or not any
> TM halts, and always return its answer to every caller.
> There can no longer be any such program as LOOP_IF_HALTS.
> We can have LOOP_IF_ONE, or LOOP_IF_ZERO, but,
> LOOP_IF_HALTS can not possibly exist.
>
> Since this halt analyzer is implemented as a standard TM, it
> directly refutes Turing's orginal proof.

However, LOOP_IF_HALTS *is* the UTM running the Halt Analyzer. Or, if
you prefer, the Halt Analyzer code is part of the LOOP_IF_HALTS code. A
UTM can hide portions of the tape from simulated TMs, but not from itself. 

-- 
Will Twentyman
email: wtwentyman at copper dot net

Relevant Pages