Multiway Turing Machines
This feels like, he is giving examples and questions, but like this post, for the most part, kinda doesn&#x27;t give any answers?  
Like, he asks &quot;how should we define universality with regards to multi-way systems&quot;, and then says &quot;here are some criteria such a definition should probably meet&quot;, but then, doesn&#x27;t, give a definition?<p>It seems to me like it would make sense to at least start with some temporary&#x2F;provisional definition, even if one expects that one may come up with a better one later.<p>As a definition of &quot;simulates&quot;, &quot;For every configuration of x, there is a corresponding configuration of y, such that that configuration of y can continue to a configuration where it halts iff the configuration of x can&quot; seems like a decent starting point, even if one wants to change what notion one is using.<p>Alternatively, one could come up with some particular set-up which one is confident that, under whatever definition one eventually decides to go with, this set-up should satisfy that definition.<p>For example, given a language for describing a non-deterministic turing machine, it should be straightforwards to design a non-deterministic turing machine which, by all reasonable definitions, simulates that other non-deterministic turing machine.<p>(just make it so that when there are multiple possible next steps in the turing machine to be simulated, that you choose one non-deterministically, in a way such that there is a bijection between the possible next steps, and the different branches you take.)<p>And then look at what properties that thing satisfies.<p>Seems to me that every possible state (with &quot;possible state&quot; meaning, possible following from the initial conditions) in the simulating machine, should map to some state of the simulated machine, and that this map (call it f) should be both surjective and computable (computable in polynomial time?), and in addition, for every pair of states x_1, x_2, of the simulating machine, if x_1 can evolve to x_2, then f(x_1) should be able to evolve to f(x_2), and also, for every y_1 and y_2, if y_1 can evolve to y_2, then there should exist an x_1 and an x_2 such that f(x_1) = y_1 and f(x_2) can evolve to y_2, and x_1 can evolve to x_2 .<p>That is,<p>\forall x_1, x_2 \in X, if R_X(x_1,x_2) then R_Y(f(x_1),f(x_2)) , and \forall y_1, y_2 \in Y, \exists x_1, x_2 \in X s.t. f(x_1)=y_1, f(x_2)=y_2 , and R_Y(y_1,y_2) iff R_X(x_1,x_2)<p>where R_X and R_Y are transitive relations on X and Y respectively, which represent &quot;can evolve to&quot;.
[note : later in this comment I realize a larger error in this, and fix it]<p>This seems like a good definition to me.<p>Well, ok I think there are probably a few patches that should be applied to it.
Like, what if there was some state x_1 in X s.t. ... well, s.t. x_1 can only lead to simulations of some of the execution paths that follow from f(x_1), not all of them, and also not just restricting what happens in the very next non-deterministic step, but many steps down the line? With the definition I gave, that is allowed, at least provided that there are other x in X s.t. f(x)=f(x_1) and where x doesn&#x27;t have that property. Though I&#x27;m not really sure that that&#x27;s an issue.<p>And, as a place to start from, it seems to me like the definition I listed seems like a good starting point, which is serviceable.<p>Other properties could be tacked on as needed. (e.g. if you wanted to include a notion of &quot;a next step&quot; in addition to simply &quot;a later step&quot; ).<p>Hm, I think this definition might actually work as as a definition for the morphisms in some category? Like, I think it composes.<p>suppose f : X \to Y , and g : Y \t Z satisfy the property. Then does the composition also satisfy the property?
for x_1, x_2 in X, if R_X(x_1,x_2), then R_Y(f(x_2),f(x_2)), and so R_Z(g(f(x_1)),g(f(x_2)) , so that&#x27;s one side.
Ah, I notice a flaw in how I phrased the second art of the definition.
What I should have said, is that there is some function which is a one-sided inverse of f,  which is f^{-1} : Y \to X s.t. \forall y, f(f^{-1}(y))=y, and for all y_1, y_2, R_Y(y_1,y_2) iff R_X(f^{-1}(y_1)f^{-1}(y_2)) .
This is really what I meant to say, I just didn&#x27;t think it through clearly, and so I said the wrong thing.
Anyway, with this part of the definition fixed, yes, this property respects composition.
So, yes, we have that if X simulates Y, and Y simulates Z, then X simulates Z.<p>Does anyone have any critique for this setup?