5 ms·

Multiway Turing Machines

73 points by nsoonhui 6y ago

kraemate 6y ago
Very interesting and different way to "visualize" non determinism. The connection to quantum mechanics is intriguing...
abelaer 6y ago
Wolfram gets (perhaps rightly) mocked a lot for his claims, but I think he actually does really good work, and has original ideas.
- Robotbeat 6y ago
  I agree. I roll my eyes at some grandiose claims WRT physics fundamentals (not that it’s wrong per se, just not a kind of “Theory of Everything”), BUT he does original, brilliant work.
deleted 6y ago
[deleted]
whatshisface 6y ago
I know I risk looking dumb by asking this, but does this idea lead to any new ideas or conclusions, or is it just a way to draw graphs that look like upside-down deciduous trees in the winter?
- max_ 6y ago
  To appreciate the article, you need to first understand the scoop of Stephen Wolfram's intellectual persuite. 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-have-a-path-to-the-fundamental-theory-of-physics-and-its-beautiful/ https://writings.stephenwolfram.com/2020/04/finally-we-may-h...
  - heavenlyblue 6y ago
    If at least one cellular automata configuration is Turing complete and a Turing machine can simulate a quantum computer, then cellular automata can simulate a quantum computer. I like his diagrams, they look cute.
    - undersuit 6y ago
      Well that's why I really like this. There are Turing complete configurations in cellular automata like GoL, but they are fiendishly complex, nothing approaching the simplicity of the simplest complete Turing Machine. A Multiway Turing Machine could get you the simplest possible complete Quantum Turing Machine(irreducible?) in a way where you aren't wasting states on GoL gliders to ferry information across your imaginary cpu.
spark3k 6y ago
I speak for many readers when I say: "What?"
- throwaway81523 6y ago
  tl;dr, but I think we had something like that in CS class back in the day: https://en.wikipedia.org/wiki/Alternating_Turing_machine https://en.wikipedia.org/wiki/Alternating_Turing_machine
boothby 6y ago
Esolang nerds will recognize befunge as a 4-way machine, and Piet as an 8-way machine.
sdwr 6y ago
This is probing the gap between classical and quantum computing. The picture of a turing machine diffusing across probability space looks quantum-y. 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.
- lisper 6y ago
  > Are quantum effects simulatable classically? 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.
- deleted 6y ago
  [deleted]
taliesinb 6y ago
So personally I'm quite excited about the whole "multiway" point of view on non-determinism. The causal graphs that Stephen presents here are one way of summarizing how local events interact with one another across the space of possible histories, but you can go further. I'm working on a generalization of this idea, which I'm calling a token event graph, which "factors" causally distinct subsystems of a rewrite system (such as an NDTM, a hypergraph rewriting system, a string rewriting system, etc.) in a clean and precise way. While it is still early days, there is already an intriguing amount of rich mathematical structure to describe and formalize. I hope to publish a blogpost about this soon.
drdeca 6y ago
This feels like, he is giving examples and questions, but like this post, for the most part, kinda doesn't give any answers? Like, he asks "how should we define universality with regards to multi-way systems", and then says "here are some criteria such a definition should probably meet", but then, doesn't, give a definition? 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?

73 points by nsoonhui 6y ago

Very interesting and different way to "visualize" non determinism. The connection to quantum mechanics is intriguing...

Wolfram gets (perhaps rightly) mocked a lot for his claims, but I think he actually does really good work, and has original ideas.

Robotbeat 6y ago
I agree. I roll my eyes at some grandiose claims WRT physics fundamentals (not that it’s wrong per se, just not a kind of “Theory of Everything”), BUT he does original, brilliant work.

deleted 6y ago

[deleted]

whatshisface 6y ago

I know I risk looking dumb by asking this, but does this idea lead to any new ideas or conclusions, or is it just a way to draw graphs that look like upside-down deciduous trees in the winter?

max_ 6y ago
To appreciate the article, you need to first understand the scoop of Stephen Wolfram's intellectual persuite. 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-have-a-path-to-the-fundamental-theory-of-physics-and-its-beautiful/ https://writings.stephenwolfram.com/2020/04/finally-we-may-h...
- heavenlyblue 6y ago
  If at least one cellular automata configuration is Turing complete and a Turing machine can simulate a quantum computer, then cellular automata can simulate a quantum computer. I like his diagrams, they look cute.
  - undersuit 6y ago
    Well that's why I really like this. There are Turing complete configurations in cellular automata like GoL, but they are fiendishly complex, nothing approaching the simplicity of the simplest complete Turing Machine. A Multiway Turing Machine could get you the simplest possible complete Quantum Turing Machine(irreducible?) in a way where you aren't wasting states on GoL gliders to ferry information across your imaginary cpu.

spark3k 6y ago

I speak for many readers when I say: "What?"

throwaway81523 6y ago
tl;dr, but I think we had something like that in CS class back in the day: https://en.wikipedia.org/wiki/Alternating_Turing_machine https://en.wikipedia.org/wiki/Alternating_Turing_machine

boothby 6y ago

Esolang nerds will recognize befunge as a 4-way machine, and Piet as an 8-way machine.

sdwr 6y ago

This is probing the gap between classical and quantum computing. The picture of a turing machine diffusing across probability space looks quantum-y. 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.

lisper 6y ago
> Are quantum effects simulatable classically? 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.
deleted 6y ago
[deleted]

taliesinb 6y ago

So personally I'm quite excited about the whole "multiway" point of view on non-determinism. The causal graphs that Stephen presents here are one way of summarizing how local events interact with one another across the space of possible histories, but you can go further. I'm working on a generalization of this idea, which I'm calling a token event graph, which "factors" causally distinct subsystems of a rewrite system (such as an NDTM, a hypergraph rewriting system, a string rewriting system, etc.) in a clean and precise way. While it is still early days, there is already an intriguing amount of rich mathematical structure to describe and formalize. I hope to publish a blogpost about this soon.

drdeca 6y ago

This feels like, he is giving examples and questions, but like this post, for the most part, kinda doesn't give any answers? Like, he asks "how should we define universality with regards to multi-way systems", and then says "here are some criteria such a definition should probably meet", but then, doesn't, give a definition? 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?