Multiway Turing Machines
wolframphysics.org
wolframphysics.org
Are quantum effects simulatable classically? Let's say our universe is a turing machine working in the timewards direction, how many extra layers would be needed to add quantum effects? Assuming the extra layers work outside the flow of time and have edit power over reality.
Yes. A QM cannot compute anything a TM cannot. But there are certain problems for which a QM can provide exponential speedup over a TM. The most obvious of these is solving the Schroedinger equation for systems with a large number of degrees of freedom.
This is obviously pure theoretical computer science (turing complete automata), but what Wolfram is trying to investigate, is if physical phenomenon can be explained through the use of cellular automata configured with simple rules (which explains why he's trying to link it to quantum physics).
If he is right, it would mean that we would have completely new ways of computing physical calculations of nature and that could posses some advantages.
Besides that, it also opens up our knowledge on what exactly computing is, through the articulation of computational process.
For a more comprehensive article on this aspect o suggest you see https://writings.stephenwolfram.com/2020/04/finally-we-may-h...
I like his diagrams, they look cute.
It seems to me like it would make sense to at least start with some temporary/provisional definition, even if one expects that one may come up with a better one later.
As a definition of "simulates", "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" seems like a decent starting point, even if one wants to change what notion one is using.
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.
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.
(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.)
And then look at what properties that thing satisfies.
Seems to me that every possible state (with "possible state" 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 .
That is,
\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)
where R_X and R_Y are transitive relations on X and Y respectively, which represent "can evolve to". [note : later in this comment I realize a larger error in this, and fix it]
This seems like a good definition to me.
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't have that property. Though I'm not really sure that that's an issue.
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.
Other properties could be tacked on as needed. (e.g. if you wanted to include a notion of "a next step" in addition to simply "a later step" ).
Hm, I think this definition might actually work as as a definition for the morphisms in some category? Like, I think it composes.
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'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'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.
Does anyone have any critique for this setup?
But, I will try to give a more succinct definition-in-words : Between a pair of a (partial) function from one preordered set to another, which is surjective and order preserving, along with a pre-composition inverse which is both order preserving and order reflecting. (except instead the relations on the sets being a preorder, I'd rather it just be transitive, rather than transitive and reflexive).
Is that really more clear than the pseudo-LaTeX ? I'm not sure.