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 10:10:53 -0400

Peter Olcott wrote:

> "Robert Low" <mtx014@linux.services.coventry.ac.uk> wrote in message news:cgnb3n$vrh$1@sunbeam.coventry.ac.uk...
>
>>Peter Olcott <olcott@worldnet.att.net> wrote:
>>
>>>It would seem that a regular Turing Machine would be able
>>>to provide protected memory. If we cast the problem as
>>
>>I have no idea what you think this means, but it would
>>certainly be possible to set up a TM which never wrote
>>on some specified portion of its tape.
>>
>>And it doesn't make the slightest damned bit of difference
>>to solving the halting problem. If there is no TM that can
>>do some particular task, then a forteriori there is
>>no TM with 'protected memory' which can do it.
>>
>>--
>>Rob. http://www.mis.coventry.ac.uk/~mtx014/
>
>
> A commonly held assumption might prove to be false.
> Try and show me how LOOP_IF_HALTS can "Loop If Halts"
> when it can't get to the private key that encrypts the meaning
> of TRUE that Halt returns? **
>
> If it can't get at the meaning of TRUE, then it can not LOOP IF HALTS.
> It can LOOP IF ONE, and it can LOOP IF ZERO, it can
> no longer LOOP IF HALTS.
>
> ** The Private key is a single bit of protected memory that
> holds the value of TRUE, either 0, or 1.

Now I understand why you were asking about whether a UTM *can* provide
"protected memory". Here's the problem, you don't get to choose which
UTM to run your Halt Analyzer and Loop If Halts on. Moreover, the UTM
cannot protect the memory from itself, since it is the program that
actually reads and writes to the "protected cell". Now you have two
problems: first, you have no way to *guarantee* that the cell of Halt
Analzer will be protected by the UTM running it. Second, you have no
way to prevent Loop If Halts from being the UTM that is running Halt
Analyzer. Either of these is enough to very simply render your notion
of protected memory unimportant. If your Halt Analyzer truly works, it
must work *always*, regardless of the choice of UTM to run it under,
regardless of whether it runs under a UTM at all.

I strongly encourage you to consciously do something that will be very
difficult. Forget everything you think you know about computers and
programming. Every idea you have offered so far is based on notions of
secure computing in a modern language running on something like Windows.
  The notion of a TM corresponds more closely with a very very old
device. Think along the lines of one of the old mainframes. Think of a
device that you "program" by physically moving wires around. It has a
magnetic tape. You have a special device that prepares the tape called
a punch card reader. The punch card reader takes the punch cards, reads
their data and copies it to the start of the tape. You then move the
tape onto the mainframe, set the wires for the "program", and turn it
on. It will do its thing. It probably has a light to let you know it
has halted, at which point you can take the tape off, put it on a card
puncher which will read the tape and put the contents of the tape onto
punch cards which a human can read.

There is no memory, only the tape. There is no state transition table,
only connections made by wires. There is only one input, the contents
of the tape when the mainframe is turned on. There is only one output,
the contents of the tape when the computer is turned off. The only part
that does not correspond is you have to pretend the tape is infinitely long. 

-- 
Will Twentyman
email: wtwentyman at copper dot net

Relevant Pages

  • Re: PROOF that numbers are countable
    ... >>where we need the godel number while we figure out if it halts. ... Then please tell me how to *objectively* determine if a particular TM halts. ... > a numerical index, is only accessible by the UTM. ... > We can get the UTM to run the UTM represented on the tape. ...
    (comp.theory)
  • Re: Can a regular Turing Machine provide Protected Memory?
    ... >>on some specified portion of its tape. ... > If it can't get at the meaning of TRUE, then it can not LOOP IF HALTS. ... UTM to run your Halt Analyzer and Loop If Halts on. ...
    (sci.logic)
  • Re: [PO] Re: Can a regular Turing Machine provide Protected Memory?
    ... >> is run inside of another TM, it simply halts. ... If the UTM that is running ... The UTM is then asked to look at its own tape, ... > correctly analyze Turing machines, we would of necessity also have to ...
    (sci.logic)
  • Re: [PO] Re: Can a regular Turing Machine provide Protected Memory?
    ... >> is run inside of another TM, it simply halts. ... If the UTM that is running ... The UTM is then asked to look at its own tape, ... > correctly analyze Turing machines, we would of necessity also have to ...
    (comp.theory)
  • Re: PROOF that numbers are countable
    ... Well, all programs eventually *do* halt (when the power goes out, ... a series of symbols readable from and writable to tape. ... > We can get the UTM to run the UTM represented on the tape. ... >> usual proof of diagonalization doesn't quite work here, ...
    (comp.theory)