Re: Can a regular Turing Machine provide Protected Memory?

newstome_at_comcast.net
Date: 08/29/04 

Date: Sat, 28 Aug 2004 23:33:25 GMT

In comp.theory Peter Olcott <olcott@worldnet.att.net> wrote:
>
> <newstome@comcast.net> wrote in message news:Sc%Xc.324401$a24.84951@attbi_s03...
>> In comp.theory Peter Olcott <olcott@worldnet.att.net> wrote:
>
>> > I don't see where you have shown this.
>> > You can't LOOP_IF_HALTS because you can't see
>> > the meaning of the result of the halt analysis. This part
>> > is airtight.
>>
>> Please read what I wrote again, and actually think about it this time.
>> I'm NOT using *YOUR* LOOP_IF_HALTS (which indeed "can't see the meaning
>> of the result"). See below for more.
>>
>> >> >> Now I'm going to wrap *this* in a "loop if halts." This will be
>> >> >> the input to your halt analyzer (run all by itself on a completely
>> >> >> honest UTM which you provide) -- remember, this is an *input* to your
>> >> >> halt analyzer. I'm not changing your program, and it's allowed to run
>> >> >> in whatever environment you want. And yet it gets the wrong answer on
>> >> >> the input that I've provided. Quelle surprise.
>>
>> See? *MY* "loop if halts" doesn't check your halt analyzer directly,
>> but rather asks my UTM that is wrapping yours to get the result.
>> *THIS* program has just as much access to, and ability to
>> "understand", the result as a "user" running your machine (in fact, my
>> UTM *IS* the "user" -- I suppose your next model will be to have a
>> magical TM which can restrict it's output to be only understandable by
>> a hunk of biomass (a person). Can a hunk of biomass do anything a TM
>> can't?)
>
> I am not sure that your reasoning is correct, but, I can make it moot in
> any case. Everyone always simply ignores IO. They always simply
> assume that everything is read from and written to the tape. This is
> all well and good but ignoring how it gets to the tape does not make
> this problem go away. There must be some way for a person to place
> data on the tape. One person suggested that this is a simple paper
> tape, and a pencil is how the data gets to the tape. In actual practice
> this will not work, the tape would wear out far too quickly, and the TM
> is incapable of repairing a broken tape. If we assume a magnetic tape,
> now we have something that a person can neither write to nor read from,
> without the aid of additional technology. This leads us to the biomass
> detector technology. Data is entered through the keyboard, and
> written to the screen. Although it is possible to make specialized
> software that can "see" what is on the screen, and it is also possible
> to make specialized software that can enter keystrokes, both
> of these devices could easily be contructed to make this impossible.
> I will review this material more closely to see if there are other
> ways of refuting it.

No, I don't ignore IO at all. I have no idea what you're talking
about in a lot of that paragraph, but it seems like you're trying to
get back around to the old "write-only output" argument that you
started with oh so many weeks ago. It doesn't help, not even a little
bit. I'll even give you a good idea for a write-only output on a real
computer: a printer. With a standard printer you can send the output,
which can be read by a person, but if you erase your result from
memory after you send it to the printer there's no way for another
program to "get back" the answer that was written.

So does this matter? Of course not. Remember that I'm wrapping your
entire program, including any special UTM you want to provide (that
can do "protected memory", "write-only output", "providing access to
the state transition tables", *whatever*), with my own UTM. If I have
to, my UTM will simulate an entire operating system to make it look
like your output is going to the printer when I instead grab it and do
whatever I want to with the result you computed. Your program cannot,
in *any* way, detect that I've done this. Your program might be able
to ask *your* UTM if it is running alone (and it is!), but it can't
ask *my* UTM that wraps yours.

Then I put loop-if-halts around *my* UTM (not yours). This then is
the *input* to your halt analyzer. Remember that I'm not changing
your model on you -- you still get to run your program on your UTM
in your environment. It simply gets the wrong answer on my *input*.

>> Again, let me make sure that you understand:
>> 1) The program running and analyzing this (the halt analyzer) is
>> exactly *your* program, running in *your* environment, providing
>> the answer however *you* feel is appropriate. I'm not changing
>> any of that.
>> 2) The *input* program (the program being analyzed by your program)
>> is one that *I* construct as described above. Since it's part of
>> the input program, it's obviously on tape (including the full
>> state transition table) and you can analyze it to your heart's
>> content. You can in fact easily detect that it's exactly the
>> input that has been designed to fool your halt analyzer. And
>> even with that knowledge, there's *nothing* you can do to make it
>> give the right answer.
>
> I am not sure that I agree with this, but, can make it moot in any case.

Well, you can't "make it moot", and there's nothing wrong with what
I've written. Let me expand the basic argument into more basic steps:

 1) You define your model of computation, and how you provide an
    answer in your model.

 2) I define a way of constructing an input from a halt analyzer
    description such that the halt analyzer will not work on the
    input.

 3) You provide a halt analyzer. You can use all of the information
    you want from step #2, knowing exactly how I'm going to construct
    my input to your halt analyzer. Even though you know this, you
    can *not* make a halt analyzer that will give a correct answer on
    my input.

 4) I construct my input for your halt analyzer, following the
    procedure from step #2, and your halt analyzer gets the wrong
    answer.

I was trying to lead you through this step by step before, but you
never could complete even step #1 and define your model.

Any time you want to try, just let me know.

> > >> >> Apparently, you just don't know what it takes to "prove a negative,"
>> >> >> Peter. You have to show that your halt analyzer can't be fooled by
>> >> >> *ANY* input, not just one specific example. That's why it's so hard
>> >> >> to "prove a negative." [ This last paragraph written with tongue
>> >> >> firmly planted in cheek. ]
>>
>> --
>>
>> That's News To Me!
>> newstome@comcast.net
>
> 

-- 
That's News To Me!
newstome@comcast.net

Relevant Pages