Re: Can a regular Turing Machine provide Protected Memory?

From: Peter Olcott (olcott_at_worldnet.att.net)
Date: 08/29/04 

Date: Sun, 29 Aug 2004 19:07:17 GMT

Since I accept your claim to have a PhD in computer science and
hold that rank of associate professor, I will give your response a
much higher weight of priority, and carefully study this today. I just
printed it out.

<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:
>
> 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

Relevant Pages