On 04/01/2015 10:15 AM, Jacob Torrey wrote:
> I've had similar thoughts, and a rather hasty blog post I wrote a while
> back may be of interest:
> http://blog.jacobtorrey.com/towards-a-new-model-of-computational-expressiveness
>
> - Jacob
>
Thanks for that link. I'm glad to see others thinking about this!
Your blog post inspired me to try to define "isolation" using Turing
machines as a model. If you can do it for a Turing machine, then that
should apply to any more specific model by the Church-Turing thesis.
I failed terribly. I was trying to say something along the lines of: If
A and B are disjoint subsets of tape indices, then A is isolated from
B iff you can freeze the machine at any time, wiggle the tape cells in
A, and the cells in B won't be affected by your wiggling for the
remainder of the computation (and vice-versa).
That doesn't work because the sets A and B have to depend on the input
length (I'll omit the proof; consider the language of strings containing
a "1").
The whole notion doesn't make much sense for a Turing machine on
a single input (we're just saying "these are cells the TM never
meaningfully uses, even though it might read/write them"), but if you
allow parts of the inputs to be chosen by different actors, the idea
makes more sense.
You can come up with a reasonable definition for a constant number of
actors. If there are K actors, let A1, A2, ..., AK be disjoint sets and
give the TM K read-only input tapes plus one work tape, where input tape
i is contained in Ai, and so on...
But that's not good enough. Real systems interact with an arbitrary
number of actors, each wanting to be isolated from the others.
So here's a question. Is it possible to give any TM-based definition of
isolation that (1) doesn't depend on the number of actors or input
length, and (2) is more insightful than
On any K-tuple input (W1, W2, ..., WK) the machine outputs a K-tuple
(R1, R2, ..., RK) and if Wi is fixed, Ri is fixed no matter how you
change the other Wj's.
That definition doesn't satisfy me because it has nothing to do with
computation; it's just a property of a *function* that a TM might
compute. It doesn't expose any Turing-machine internals to reason about.
Is there a good definition that does?
-Taylor
_______________________________________________
langsec-discuss mailing list
langsec-discuss@mail.langsec.org
https://mail.langsec.org/cgi-bin/mailman/listinfo/langsec-discuss
