Re: Can a regular Turing Machine provide Protected Memory?

newstome_at_comcast.net
Date: 09/01/04 

Date: Wed, 01 Sep 2004 14:57:13 GMT

In comp.theory Peter Olcott <olcott@worldnet.att.net> wrote:
>
> <newstome@comcast.net> wrote in message news:fjoYc.65234$9d6.56329@attbi_s54...
>> In comp.theory Peter Olcott <olcott@worldnet.att.net> wrote:
>> >
>> > <newstome@comcast.net> wrote in message news:9D8Yc.251050$eM2.4450@attbi_s51...
>> >> In comp.theory Peter Olcott <olcott@worldnet.att.net> wrote:
>> >
>> >> 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.
>> >
>> > If you can effectively refute every combination of all of my
>> > methods then do it. Start with the one where I only write
>> > the output to the screen. If this refutation works, I can probably
>> > construct the rest from this one.
>> >
>> > Note it must be framed as an input that no TM can possibly
>> > correctly process, otherwise it does not meet the burden of
>> > proof of proving a negative.
>>
>> No, it will not be *an* input that no TM can possibly correctly
>> process, because there is no such input. It will be a *process* for
>> creating an input, *given* a TM, such that this TM will not correctly
>> process that input.
>>
>> I wanted to do this step by step before, because you have a nasty
>> habit of reading the first few words of a posting, replying without
>> really thinking about it, and then ignoring the rest.
>>
>> Since it's Sunday and I obviously have way too much time on my hands,
>> I'll lay out the entire argument for you, following my 1-4 steps above
>> for your "output to the screen" case. If you have questions or
>> problems with any part of this, then ask, but please *try* to
>> understand it. I won't change the argument, and you don't change the
>> model as you try to do everytime your flaws become obvious (in other
>> words, stick to the "screen" model -- do not say "Oh, ok, then we'll
>> add the ability to inspect the state table" -- we debunk one model at
>> a time). Here we go:
>>
>> 1) The "screen" is no different from a "write only output" that you've
>> talked about before, so we'll model that within the TM framework as
>> a write-only output tape. This is really easy to do: we'll just
>> have a TM with two tapes, and one of them (representing the
>> "screen") is write-only. The transition function f will look like
>> this:
>>
>> f(state, tsym) -> (newstate, newtsym, tmove, outsym, outmove)
>>
>> where "state" is the current state, "tsym" is the current tape
>> symbol on the regular TM tape, "newstate" is the new state after
>> this transition, "newtsym" is the symbol written to the regular TM
>> tape, "tmove" is the movement of the regular TM tape head (we can
>> let this be "left", "right", or "stay still"), "outsym" is the
>> "screen output" symbol, "outmove" is the direction to move the tape
>> head on this output tape (same choices as "tmove").
>>
>> Notice that the transition function doesn't depend on the output
>> tape ("screen"), so the "screen" can't possibly affect the
>> computation -- this makes it write-only.
>>
>>
>> 2) Given the above model, here's how I'll create an *input* for any
>> halt analyzer that runs in this model. First, the halt analyzer
>> has to be supplied, and the obvious way of doing that is that the
>> state transition function is specified. Say a table of 7-tuples is
>> given that defines the "f" function given in part 1. This table
>> completely determines the actions of the halt analyzer in this
>> model, so completely defines the program. Whenever we use a
>> function name as a parameter, or a "value", it means this encoding
>> of the transition table for the function.
>>
>> It's also true that any way of correctly "executing" this
>> program/transition table is as good as any other, as long as the
>> transition function is correctly followed using the rules defined
>> by the model (defined back in step 1). So whether I build hardware
>> that actually realizes the model from step 1, or make a UTM program
>> that follows the state transition table, or implement it by using
>> lego mindstorm pieces, it really doesn't matter -- if it works in
>> *any* correct execution environment, it must work in *all*
>> *correct* execution environments, since all such environments do
>> exactly the same thing with this state transition table.
>>
>> Now keep in mind here, before you have a knee-jerk reaction to the
>> above statements, and trot out your debunked "turning the power
>> off" example, that in the end (step #4 below) I will be running
>> *exactly* the given halt analyzer in *your* model exactly. I will
>> not be changing any conditions.
>>
>> Now consider a UTM that *exactly* and *correctly* implements your
>> model. This is very easy to do -- it simply keeps track of the
>> current state, and keeps the tape contents in arrays, along with
>> the current tape position. The "code" of my UTM follows your state
>> transition table, so after every step of its execution it will be
>> in exactly the same state, with exactly the same tape contents, as
>> your machine. If your halt analyzer works in your model, it
>> clearly works in my UTM as well, since my UTM exactly implements
>> your model.
>>
>> However, my UTM does one more thing -- after the execution is
>> completed, it can look at the "write-only output tape". *Your*
>> program can't do that, because your model doesnt allow it, but my
>> UTM certainly can. So my UTM code looks like this:
>>
>> void myUTM(HA, 2ndParam) {
>> while (not in a final state) {
>> Execute HA exactly as defined by your model (given the state
>> transition table provided as the 1st parameter to myUTM), using
>> input <2ndParam,<HA,2ndParam>>
>> }
>>
>> result = Look at the simulated output tape to see what the halt
>> analyzer output
>>
>> if (result == "Halts")
>> Loop forever;
>> else
>> halt;
>> }
>>
>> Notice that myUTM is just a program, which takes a transition table
>> and an input to a TM as its input. The first part of myUTM (the
>> while loop) exactly executes HA(2ndParam,<HA,2ndParam>) following
>> the rules of your model. Let me repeat that last part with
>> emphasis: *FOLLOWING THE RULES OF YOUR MODEL*.
>>
>> The input for myUTM is going to be the pair <HA,myUTM>, which means
>> that the first part of this code exactly executes
>> HA(myUTM,<HA,myUTM>). This is the input that I will supply to your
>> halt analyzer: the machine to analyze is "myUTM", and the input for
>> that machine is "<HA,myUTM>". This is easy to write down, once you
>> supply a halt analyzer in step 3, so this defines my procedure for
>> producing the input that your halt analyzer can't correctly
>> process.
>>
>>
>> 3) Now you get to supply whatever halt analyzer you like, claiming
>> that it works in your model with the write only output. Let's call
>> this PHA for "Peter's Halt Analyzer", and remember that it takes
>> two inputs, "machine" and "input".
>>
>>
>> 4) Now I'll show you that your halt analyzer (PHA), run in your model
>> with the write-only output (the "screen"), will not work on the
>> input that I described in step 2. Notice that I don't care how
>> your PHA works. It is perfectly free to examine the input given to
>> it to see if the machine is "myUTM", since you know exactly what
>> that is. In other words, PHA is perfectly free to see if I'm
>> trying to fool it. And it can "know" when I'm trying to fool it.
>> It's just that it can't do anything about it. Here's the full
>> argument:
>>
>> We're running PHA(myUTM, <PHA,myUTM>) in your model, under your
>> conditions. Since it's your model and your conditions, it's
>> required to output the answer of the halt analysis to the "screen",
>> which must be "Halts" or "Doesn't Halt", so consider each case
>> separately:
>
> This is my first preliminary analysis. I will have to study it for
> several more days to make sure that it is completely consistent
> with everything that I have said, and everything that you have
> said.
>
> It looks like it is completely impossible for you to execute my
> model exactly as I have originally designed it. My model "knows"
> that it is completely impossible for any other TM to have any
> access to its results, then it sees that you have provided this
> access. We can't assume that it is my original model, because
> you have already directly contradicted that.

[ As an aside, I'll mention that I've seen tom_usenet's response to
this as well, and he's spot-on with his comments. But since you seem
to listen to me, I'll explain as well. ]

Go back to my original posting (quoted fully above, it seems), and
look at this statement from step 2:

    It's also true that any way of correctly "executing" this
    program/transition table is as good as any other, as long as the
    transition function is correctly followed using the rules defined
    by the model (defined back in step 1). So whether I build hardware
    that actually realizes the model from step 1, or make a UTM program
    that follows the state transition table, or implement it by using
    lego mindstorm pieces, it really doesn't matter -- if it works in
    *any* correct execution environment, it must work in *all*
    *correct* execution environments, since all such environments do
    exactly the same thing with this state transition table.

Your halt analyzer, in your model, must follow the behavior defined
for it in the state transition table. As long as my simulator follows
the transition table, it will do exactly and precisely the same thing
as if it were executed in any other setting that correctly follows the
transition table. Your program can *never* "know" if another TM has
access to its results -- which is the downfall of all your arguments.

I've been sticking to the precise argument, but let me throw in a more
abstract question: What exactly do you think a "computation" is?
It's simply something that follows a set of rules that change one
state into another state. Is there some reason that you feel a
software simulator doing precisely that (evolving the state) is any
less genuine a computation than hardware doing the same thing?
Hardware is simply an interpreter, but at a different level. There
are even things in-between raw hardware and a full software simulator:
most CPUs these days (CISC CPUs, anyway) use microcode, so in a sense
even basic machine code is being interpreted by software (the
microcode). Where are you going to draw the line and say "computing
on hardware is a computation" but "computing in a simulator is somehow
different."

Anyway, try to wrap your mind around that -- if you think that your
halt analyzer does something (anything!) different when run directly
in your model and when run in my simulator, tell me exactly and
precisely how it's different. What state transitions are followed
differently in these two situations?

> This seems to leave only one option. Any model that I am going
> to create that fits within the specifications that you provided
> would not report that the inner nested invocation would halt.
> Neither can it correctly report that it will not halt. It would be
> smart enough to see that both of these answers are wrong within
> the specific context that you provided. This leaves the outer
> nested invocation to conclusively determine that the inner nested
> invocation would halt.
>
> That's that way that I see it right now. I will continue to check
> and double check what I have said against what you have said.
>
>
>> Case 1 ("Halts"): Remember what we said in step 2 -- the first
>> part of myUTM (through the while loop) runs PHA(myUTM,<PHA,myUTM>)
>> in *your* model. In other words, this part runs exactly the same
>> code, in exactly the same way, as the call to PHA. Since this
>> case is defined by the fact that PHA(myUTM,<PHA,myUTM>) says
>> "Halts" (to the "screen"), the value of "result" in myUTM will be
>> "Halts". This in turn makes myUTM loop for ever, so it doesn't
>> halt. Therefore, the answer of PHA is wrong.
>>
>> Case 2 ("Doesn't Halt"): Same basic argument as case 1.
>>
>>
>> Summary: We defined a model with a write-only "screen". Then we
>> described how to make an input to a halt analyzer, running in the
>> "write-only screen" model. Then we showed that if you took any halt
>> analyzer in the "write-only screen" model, and produced an input as
>> described, then the halt analyzer (in the "write-only screen" model)
>> would output the *wrong* answer TO THE SCREEN.
>>
>> This means that any halt analyzer does not work on at least one input
>> in the "write-only screen" model.
>>
>> Since this works for any possible halt analyzer in the "write-only
>> screen" model, we have shown that there cannot be a halt analyzer that
>> gives the correct answer for all inputs in the "write-only screen"
>> model.
>>
>>
>> --
>>
>> That's News To Me!
>> newstome@comcast.net
>
> 

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

Relevant Pages
Loading