[HN Gopher] Multiway Turing Machines
___________________________________________________________________
Multiway Turing Machines
Author : nsoonhui
Score : 59 points
Date : 2021-02-08 13:55 UTC (9 hours ago)
(HTM) web link (www.wolframphysics.org)
(TXT) w3m dump (www.wolframphysics.org)
| kraemate wrote:
| Very interesting and different way to "visualize" non
| determinism. The connection to quantum mechanics is intriguing...
| sdwr wrote:
| 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 wrote:
| > 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.
| spark3k wrote:
| I speak for many readers when I say: "What?"
| throwaway81523 wrote:
| 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
| boothby wrote:
| Esolang nerds will recognize befunge as a 4-way machine, and Piet
| as an 8-way machine.
| abelaer wrote:
| Wolfram gets (perhaps rightly) mocked a lot for his claims, but I
| think he actually does really good work, and has original ideas.
| Robotbeat wrote:
| 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.
| whatshisface wrote:
| 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_ wrote:
| 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-h...
| taliesinb wrote:
| 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.
| [deleted]
___________________________________________________________________
(page generated 2021-02-08 23:02 UTC)