Multiway Turing Machines—Wolfram Physics Bulletins
PRELIMINARY VERSION
Contents
Top
Ordinary vs. Multiway Turing Machines
Turing Machines with Simple Rules
Visualization and Multispace
The World of Simple Multiway Turing Machines
What Is the Simplest Universal Multiway Turing Machine?
The Halting Problem and Busy Beavers
Causal Graphs
Causal Invariance
Finite Tapes
Notes
Multiway Turing Machines
Multiway Turing Machines
Stephen Wolfram
February 4, 2021
Related livestreams
Related notebooks
Video work logs
Related tweets
Related livestreams
December 29, 2020 (with Jonathan Gorard)
January 5, 2021 (with Mano Namuduri and Ed Pegg)
Related notebooks
NDTM-01 (by Stephen Wolfram)
NDTM-02 (by Stephen Wolfram)
NDTM-03-Multispace (by Stephen Wolfram)
NDTM-04 (by Stephen Wolfram)
NDTM-05 (by Stephen Wolfram)
NDTM-06 (by Stephen Wolfram)
NDTM-07 (by Stephen Wolfram)
NDTM-08 (by Stephen Wolfram)
NDTM-09 (by Stephen Wolfram)
NDTM-10–123 (by Stephen Wolfram)
NDTM-11–computation (by Stephen Wolfram)
NDTM-12-multispace (by Stephen Wolfram)
NDTM-13-multispace (by Stephen Wolfram)
NDTM-14-halting (by Stephen Wolfram)
NDTM-15 (by Stephen Wolfram)
NDTM-16 (by Stephen Wolfram)
NDTM-17 (by Stephen Wolfram)
NDTM-18 (by Stephen Wolfram)
NDTM-19-MA (by Stephen Wolfram)
NDTM-20-summary (by Stephen Wolfram)
NDTM-21-tapes (by Stephen Wolfram)
NDTM-22 (by Stephen Wolfram)
NDTM-23 (by Stephen Wolfram)
NDTM-24 (by Stephen Wolfram)
NDTM-25 (by Stephen Wolfram)
NDTM-26-combinators (by Stephen Wolfram)
NDTM-27-paths (by Stephen Wolfram)
NDTM-28-causal (by Stephen Wolfram)
NDTM-29-beavers (by Stephen Wolfram)
NDTM-30-beavers (by Stephen Wolfram)
NDTM-31-beavers (by Stephen Wolfram)
NDTM-32-branchial (by Stephen Wolfram)
NDTM-33-beavers (by Stephen Wolfram)
NDTM-34-computedfunctions (by Stephen Wolfram)
NDTM-35-beavers (by Stephen Wolfram)
NDTM-35-compiled (by Stephen Wolfram)
Observers-01 (by Stephen Wolfram)
TagSystems-02 (by Stephen Wolfram)
TagSystems-03 (by Stephen Wolfram)
TagSystems-04 (by Stephen Wolfram)
TagSystems-05 (by Stephen Wolfram)
TagSystems-06 (by Stephen Wolfram)
TagSystems-07 (by Stephen Wolfram)
TagSystems-08 (by Stephen Wolfram)
TagSystems-09 (by Stephen Wolfram)
TagSystems-10 (by Stephen Wolfram)
TagSystems-11 (by Stephen Wolfram)
TagSystems-12 (by Stephen Wolfram)
TagSystems-13 (by Stephen Wolfram)
Video work logs
January 5, 2021
January 9, 2021
January 10, 2021
January 11, 2021
January 18, 2021
January 23, 2021
January 25, 2021
January 28, 2021
Related tweets
At the edge of undecidability: what Turing machine survives longest before halting (the "busy beaver" problem)? I just started to look at the (rather interesting) nondeterministic generalizations… pic.twitter.com/Q1ywJL8Qut
— Stephen Wolfram (@stephen_wolfram) February 4, 2021
We got the simplest universal ordinary Turing machine in 2007 (2 states; 3 colors). Now what about the simplest universal nondeterministic (i.e. multiway) Turing machine? Could this be it? pic.twitter.com/KRJxoIxg9F
— Stephen Wolfram (@stephen_wolfram) February 4, 2021
Just had a lot of fun exploring the simplest multiway (i.e. nondeterministic) Turing machines. As elsewhere in the computational universe, turns out they can do more than you’d ever imagine. (Oh, and they give me new intuition about quantum observers) https://t.co/8lg1d04LEd pic.twitter.com/bJwDBf2sc9
— Stephen Wolfram (@stephen_wolfram) February 4, 2021
Invented in 1992 for A New Kind of Science, "multiway systems" took off in 2020—as we realized our universe is one!https://t.co/fk4OOJoiGZ pic.twitter.com/JOEGhGRRCM
— Stephen Wolfram (@stephen_wolfram) January 26, 2021
#WolframPhysicsLive Non-deterministic Turing machines in the wild: yet another simple system with complex behavior … and more raw material for thinking about quantum mechanics & quantum measurement…https://t.co/WdHJCa2fVX pic.twitter.com/4JwZJuJ7Fi
— WolframPhysics (@wolframphysics) December 31, 2020
Over the years I’ve studied the simplest ordinary Turing machines quite a bit, but I’ve barely looked at multiway Turing machines (also known as nondeterministic Turing machines or NDTMs). Recently, though, I realized that multiway Turing machines can be thought of as “maximally minimal” models both of concurrent computing and of the way we think about quantum mechanics in our Physics Project. So now this piece is my attempt to “do the obvious explorations” of multiway Turing machines. And as I’ve found so often in the computational universe, even cases with some of the very simplest possible rules yield some significant surprises….
Ordinary vs. Multiway Turing Machines
An ordinary Turing machine has a rule such as
✕
that specifies a unique successor for each configuration of the system (here shown going down the page starting from an initial condition consisting of a blank tape):
✕
In a multiway Turing machine more than one possible outcome can be...