Multiway Turing Machines

Through the years I’ve studied the only ordinary Turing machines quite a bit, however I’ve barely checked out multiway Turing machines (often known as nondeterministic Turing machines or NDTMs). Lately, although, I spotted that multiway Turing machines will be considered “maximally minimal” fashions each of concurrent computing and of the best way we take into consideration quantum mechanics in our Physics Project. So now this piece is my try and “do the apparent explorations” of multiway Turing machines. And as I’ve found so often in the computational universe, even instances with among the very easiest doable guidelines yield some important surprises….

Atypical vs. Multiway Turing Machines

An ordinary Turing machine has a rule such as

RulePlot

&#10005

RulePlot[TuringMachine[2506]]

that specifies a singular successor for every configuration of the system (right here shown happening the web page ranging from an preliminary situation consisting of a clean tape):

RulePlot

&#10005

RulePlot[TuringMachine[2506], {{1, 6}, Desk[0, 10]}, 20, 
 Mesh -> True, Body -> False]

In a multiway Turing machine multiple doable consequence will be specified for a selected case within the rule:

CloudGet

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; TuringMachinePlot[
 Flatten[{{{1, 1} -> {2, 0, -1}}, {{1, 0} -> {2, 1, 1}}, {{1, 
      0} -> {2, 0, -1}}, {{2, 1} -> {1, 0, 1}}, {{2, 0} -> {1, 
      1, -1}}}], 2, 2, "RulePlot"]

The result’s that there will be many doable paths of evolution for the system—as represented by a multiway graph that connects successive doable configurations:

With

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; With[{t = 3}, 
 MultiwayTuringMachine[{{{1, 1} -> {2, 0, -1}}, {{1, 0} -> {2, 1, 
      1}}, {{1, 0} -> {2, 0, -1}}, {{2, 1} -> {1, 0, 1}}, {{2, 
      0} -> {1, 1, -1}}}, {{1, t + 1}, Table[0, 2 t + 1]}, t, 
  "StatesGraph", VertexSize -> .8 {1, .2}, 
  GraphLayout -> "LayeredDigraphEmbedding", 
  PerformanceGoal -> "High quality"]]

The evolution in response to the odd Turing machine rule corresponds to a selected path within the multiway graph:

With

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; With[{g = 
   With[{t = 5}, 
    MultiwayTuringMachine[{{{1, 1} -> {2, 0, -1}}, {{1, 0} -> {2, 1, 
         1}}, {{1, 0} -> {2, 0, -1}}, {{2, 1} -> {1, 0, 1}}, {{2, 
         0} -> {1, 1, -1}}}, {{1, t + 1}, Table[0, 2 t + 1]}, t, 
     "StatesGraph", VertexSize -> .8 {1, .2}, 
     GraphLayout -> "LayeredDigraphEmbedding", 
     PerformanceGoal -> "High quality"]]}, 
 HighlightGraph[g, 
  Style[Subgraph[g, 
    ToString[Take[First[#], 2], Final[#]] & /@ 
     With[{t = 5}, 
      TuringMachine[
       [email protected]{{{1, 1} -> {2, 0, -1}}, {{1, 0} -> {2, 1, 1}}, {{1, 
            0} -> {2, 0, -1}}, {{2, 1} -> {1, 0, 1}}, {{2, 0} -> {1, 
            1, -1}}}, {{1, t + 1}, Table[0, 2 t + 1]}, t]]], Thick, 
   Crimson]]]

Persevering with for a couple of extra steps, one begins to see a reasonably complicated sample of branching and merging within the multiway graph:

With

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; With[{t = 15}, 
 MultiwayTuringMachine[{{{1, 1} -> {2, 0, -1}}, {{1, 0} -> {2, 1, 
      1}}, {{1, 0} -> {2, 0, -1}}, {{2, 1} -> {1, 0, 1}}, {{2, 
      0} -> {1, 1, -1}}}, {{1, t + 1}, Table[0, 2 t + 1]}, t, 
  "StatesGraphStructure", GraphLayout -> "LayeredDigraphEmbedding", 
  PerformanceGoal -> "High quality", AspectRatio -> 1]]

My goal right here is to discover what multiway Turing machines with easy guidelines can do.

The fundamental setup for my multiway Turing machines is similar as for what are often known as “nondeterministic Turing machines” (NDTMs), however in NDTMs one is often inquisitive about whether or not single paths have specific properties, whereas we shall be within the full multiway construction of all doable paths. (And by utilizing “multiway” moderately than “nondeterministic” we keep away from the confusion that we is perhaps fascinated by probabilistic or random paths—and emphasize that we’re learning the construction of all doable paths.)

In our Physics Project, multiway techniques are what lead to quantum mechanics, and our multiway Turing machines right here correspond fairly on to quantum Turing machines, with the magnitudes of quantum amplitudes being decided by path weighting, and their phases being decided by areas within the branchial space that emerges from transverse slices of the multiway graph.

Turing Machines with Easy Guidelines

There are 4096 possible ordinary Turing machines with s = 2 head states and okay = 2 colours. All these machines in the end behave in easy methods, with examples of the most complex behavior being (the last case is a binary counter with logarithmic development):

With

&#10005

With[{t = 10}, 
 Labeled[RulePlot[
     TuringMachine[#], {{1, t + 1, 0}, Desk[0, 2 t + 1]}, 35, 
     Mesh -> False], 
    RulePlot[TuringMachine[#], ImageSize -> 150, 
     FrameStyle -> LightGray]] & /@ {1971, 2506, 1953}]

Issues get solely barely extra complicated with s = 3, okay = 2, however with s = 2, okay = 3 one finds the simplest Turing machine with complex behavior (and this habits happens even with a clean preliminary tape):

GraphicsRow

&#10005

GraphicsRow[
 RulePlot[TuringMachine[{596440, 2, 3}], #] & /@ 
  Partition[TuringMachine[{596440, 2, 3}, {1, {{}, 0}}, 80 5], 80]]
RulePlot

&#10005

RulePlot[TuringMachine[{596440, 2, 3}]]

As recommended by the Principle of Computational Equivalence, this Turing machine turns out be computation universal (making it the very simplest possible universal Turing machine).

So what this implies is that the edge for universality in odd Turing machines is s = 2, okay = 3: i.e. guidelines through which there are 6 instances specified. However one query we will then ask is: what’s the threshold for universality in multiway Turing machines?

To say that our s = 2, okay = 3 odd Turing machine is common is to say that with applicable preliminary circumstances the evolution of this Turing machine can emulate the evolution of every other Turing machine (at the very least with an appropriate encoding, implementable by a bounded computation).

The closest analogous definition of computation universality for multiway Turing machines is to say that with applicable preliminary circumstances the multiway evolution of a Turing machine can emulate (as much as appropriate encoding) the multiway evolution of every other Turing machine. (As we are going to talk about later, nonetheless, the “nondeterministic interpretation” suggests a nominally totally different definition based mostly on whether or not preliminary circumstances will be set as much as make corresponding particular person paths with specific figuring out options exist.)

To specify the rule for an odd Turing machine, one usually simply defines the result for every of the s okay doable “inputs” reminiscent of

Flatten

&#10005

Flatten[Table[
  RulePlot[TuringMachine[{0, 2, 2}], {{s, 1}, {i}}, 0, 
   ImageSize -> 20], {s, 1, 2}, {i, 1, 0, -1}]]

or:

Flatten

&#10005

Flatten[Table[
  RulePlot[TuringMachine[{0, 2, 3}], {{s, 1}, {i}}, 0, 
   ImageSize -> 20], {s, 1, 2}, {i, 2, 0, -1}]]

However what if one omits a few of these inputs? In analogy to our standard therapy of string or hypergraph rewriting systems it’s pure to only say that if one of many omitted inputs is reached within the evolution of the system, then no rewrite is carried out, or—in commonplace Turing machine phrases—the system “halts”.

With s = 2, okay = 2, the longest that machines that can finally halt survive (ranging from a clean tape) is simply 6 steps—and there are 8 distinct machines (as much as reflection) which do that, 3 with solely 2 instances out of 4 of their guidelines, and 5 with 3 instances:

CloudGet

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; Grid[
 TakeList[Labeled[
     RulePlot[TuringMachine[#], {{1, 4}, Desk[0, 7]}, 6, 
      Mesh -> True, Body -> None, ImageSize -> 100], 
     TuringMachinePlot[DeleteCases[#, _ -> {_, _, 0}], 2, 2, 
      "RulePlot", 
      ImageSize -> ]] & /@ {{{1, 1} -> {1, 1, 1}, {1, 
       0} -> {2, 1, -1}, {2, 1} -> {2, 1, 0}, {2, 0} -> {1, 1, 
       0}}, {{1, 1} -> {2, 0, 0}, {1, 0} -> {2, 1, -1}, {2, 1} -> {2, 
       1, 0}, {2, 0} -> {1, 1, 1}}, {{1, 1} -> {2, 0, 1}, {1, 
       0} -> {1, 1, 0}, {2, 1} -> {2, 1, 0}, {2, 0} -> {1, 
       1, -1}}, {{1, 1} -> {1, 1, 0}, {1, 0} -> {2, 0, 1}, {2, 
       1} -> {2, 1, 1}, {2, 0} -> {1, 1, -1}}, {{1, 1} -> {1, 1, 
       0}, {1, 0} -> {2, 1, -1}, {2, 1} -> {1, 1, 1}, {2, 0} -> {2, 0,
        1}}, {{1, 1} -> {1, 1, 0}, {1, 0} -> {2, 1, -1}, {2, 1} -> {1,
        1, 1}, {2, 0} -> {2, 1, 1}}, {{1, 1} -> {2, 0, 1}, {1, 
       0} -> {2, 1, -1}, {2, 1} -> {2, 1, 0}, {2, 0} -> {1, 1, 
       1}}, {{1, 1} -> {2, 1, 1}, {1, 0} -> {2, 1, -1}, {2, 1} -> {2, 
       1, 0}, {2, 0} -> {1, 1, 1}}}, {3, 5}]]

In a way every of those guidelines will be considered utilizing some subset of all 2 s2 okay2 doable rule instances, which for okay = 2, s = 2 is:

CloudGet

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; Row[
 TuringMachinePlot[{#}, 2, 2, "RulePlot", ImageSize -> 40] & /@ 
  Flatten[Table[{s0, c0} -> {s1, c1, d}, {s0, 1, 2}, {c0, 1, 
     0, -1}, {s1, 1, 2}, {c1, 1, 0, -1}, {d, {-1, 1}}], 4], Spacer[1]]

And generally any multiway Turing machine rule corresponds to some such subset. If all doable inputs seem precisely as soon as, one will get an odd Turing machine that doesn’t halt. If inputs seem at most as soon as, however some don’t seem in any respect, the Turing machine could halt (although if it by no means reaches that enter it received’t halt).

But when any enter seems greater than as soon as, the Turing machine could exhibit nontrivial multiway evolution. If all inputs seem at the very least as soon as, no department of the multiway evolution can halt. But when some inputs seem greater than as soon as, whereas some don’t seem in any respect, some branches of the multiway evolution could halt, whereas others could proceed ceaselessly.

Generally, there are 22s2okay2 doable multiway Turing machine guidelines. In speaking about rulial house and rulial multiway techniques I previously discussed the actual instance of the (“rulial”) multiway Turing machine rule through which each single case is included (i.e. all 32 instances for s = 2, okay = 2), in order that the Turing machine is in a way “as multiway as doable”. However right here we’re involved with multiway Turing machines whose guidelines are as an alternative so simple as doable—and “removed from the rulial restrict”.

The only nontrivial multiway Turing machines have simply two instances of their guidelines. Generally, there are Binomial[2 s2 k2, 2] such guidelines, or for s = 2, okay = 2, 496—of which 112 have precise multiway habits.

A quite simple instance is the rule

CloudGet

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; TuringMachinePlot[
 [email protected]{{{{1, 0} -> {1, 1, -1}}, {{1, 0} -> {1, 
       0, -1}}}}, 2, 2, "RulePlot"]

which generates tape configurations containing all binary numbers

With

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; With[{t = 3}, 
 MultiwayTuringMachine[{{{1, 0} -> {1, 1, -1}}, {{1, 0} -> {1, 
      0, -1}}}, {{1, t + 1, 0}, Table[0, 2 t + 1]}, t, "StatesGraph", 
  AspectRatio -> .3, GraphLayout -> "LayeredDigraphEmbedding", 
  VertexSize -> .17 {2 t + 1, 1}, PerformanceGoal -> "High quality"]]

and provides a multiway system which kinds an infinite binary tree:

With

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; With[{t = 5}, 
 MultiwayTuringMachine[{{{1, 0} -> {1, 1, -1}}, {{1, 0} -> {1, 
      0, -1}}}, {{1, t + 1, 0}, Table[0, 2 t + 1]}, t, 
  "StatesGraphStructure", AspectRatio -> .4, 
  GraphLayout -> "LayeredDigraphEmbedding", 
  PerformanceGoal -> "High quality"]]

A barely much less trivial instance is the rule

CloudGet

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; TuringMachinePlot[
 [email protected]{{{1, 0} -> {1, 1, -1}}, {{1, 0} -> {1, 1, 
      1}}}, 2, 2, "RulePlot"]

which produces a multiway graph through which branches cease as quickly as the top is on a non-blank cell:

With

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; With[{t = 4}, 
 MultiwayTuringMachine[{{{1, 0} -> {1, 1, -1}}, {{1, 0} -> {1, 1, 
      1}}}, {{1, t + 1, 0}, Table[0, 2 t + 1]}, t, "StatesGraph", 
  AspectRatio -> .4, GraphLayout -> "LayeredDigraphEmbedding", 
  VertexSize -> .1 {2 t + 1, 1}, PerformanceGoal -> "High quality"]]

Persevering with this, the general construction of the multiway graph is (the place halting states are indicated by pink dots):

CloudGet

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; TMAppliesGraph[{{{1, 
     0} -> {1, 1, -1}}, {{1, 0} -> {1, 1, 1}}}, 8]

As one other instance, contemplate the rule:

CloudGet

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; TuringMachinePlot[
 [email protected]{{{1, 0} -> {1, 0, -1}}, {{1, 0} -> {1, 1, 
      1}}}, 2, 2, "RulePlot"]
MultiwayTuringMachine

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; With[{t = 4}, 
 MultiwayTuringMachine[{{{1, 0} -> {1, 0, -1}}, {{1, 0} -> {1, 1, 
      1}}}, {{1, t + 1, 0}, Table[0, 2 t + 1]}, t, "StatesGraph", 
  AspectRatio -> .4, GraphLayout -> "LayeredDigraphEmbedding", 
  VertexSize -> .15 {2 t + 1, 1}, PerformanceGoal -> "High quality"]]

As soon as once more, the system halts if the top will get onto a non-blank cell, however this occurs in a barely extra elaborate method, giving a barely extra sophisticated multiway graph:

TMAppliesGraph

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; TMAppliesGraph[{{{1, 
     0} -> {1, 0, -1}}, {{1, 0} -> {1, 1, 1}}}, 8]

Within the instance we’ve simply seen, there may be specific halting, within the sense that the Turing machine can attain a state through which none of its guidelines apply. One other factor that may occur is that Turing machines can get into infinite loops—and since in our multiway graphs an identical states are merged, such loops present up as precise loops within the multiway graph, as on this instance:

TuringMachinePlot

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; TuringMachinePlot[
 [email protected]{{{1, 0} -> {1, 0, -1}}, {{1, 0} -> {1, 0, 
      1}}}, 2, 2, "RulePlot"]
MultiwayTuringMachine

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; With[{t = 3}, 
 MultiwayTuringMachine[{{{1, 0} -> {1, 0, -1}}, {{1, 0} -> {1, 0, 
      1}}}, {{1, t + 1, 0}, Table[0, 2 t + 1]}, t, "StatesGraph", 
  AspectRatio -> 2, GraphLayout -> "LayeredDigraphEmbedding", 
  VertexSize -> .12 {2 t + 1, 1}, PerformanceGoal -> "High quality"]]

As quickly as one permits 3 instances within the guidelines, issues quickly get extra sophisticated. Take into account for instance the rule (which may by no means halt):

TuringMachinePlot

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; TuringMachinePlot[
 [email protected]{{{1, 1} -> {1, 0, -1}}, {{1, 0} -> {1, 0, -1}}, {{1, 
      0} -> {1, 1, 1}}}, 2, 2, "RulePlot"]

The primary few steps in its multiway graph are:

MultiwayTuringMachine

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; With[{t = 3}, 
 MultiwayTuringMachine[{{{1, 1} -> {1, 0, -1}}, {{1, 0} -> {1, 
      0, -1}}, {{1, 0} -> {1, 1, 1}}}, {{1, t + 1}, 
   Table[0, 2 t + 1]}, t, "StatesGraph", AspectRatio -> .8, 
  GraphLayout -> "LayeredDigraphEmbedding", 
  VertexSize -> .15 {2 t + 1, 1}, PerformanceGoal -> "High quality"]]

This instance exposes a considerably refined challenge. In our earlier examples, all of the states generated on a selected step may persistently be organized in a single layer within the multiway graph. However right here the state is generated each at step 2 and at step 4—so no such “world layering” is feasible (at the very least, assuming, as we do, that we mix an identical copies of this state).

And a consequence of this lack of worldwide layering is that if we compute for a given variety of steps we will find yourself with “dangling states”—like —that seem in our rendering nicely above the “last layer” proven.

After one other step, the earlier “dangling states” now have successors, however there are new dangling states:

MultiwayTuringMachine

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; With[{t = 4}, 
 MultiwayTuringMachine[{{{1, 1} -> {1, 0, -1}}, {{1, 0} -> {1, 
      0, -1}}, {{1, 0} -> {1, 1, 1}}}, {{1, t + 1, 0}, 
   Table[0, 2 t + 1]}, t, "StatesGraph", AspectRatio -> .8, 
  GraphLayout -> "LayeredDigraphEmbedding", 
  VertexSize -> .15 {2 t + 1, 1}, PerformanceGoal -> "High quality"]]

Persevering with for extra steps, a considerably elaborate however however pretty common multiway begins to develop:

MultiwayTuringMachine

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; With[{t = 8}, 
 MultiwayTuringMachine[{{{1, 1} -> {1, 0, -1}}, {{1, 0} -> {1, 
      0, -1}}, {{1, 0} -> {1, 1, 1}}}, {{1, t + 1, 0}, 
   Table[0, 2 t + 1]}, t, "StatesGraphStructure", AspectRatio -> .8, 
  GraphLayout -> "LayeredDigraphEmbedding", 
  PerformanceGoal -> "High quality"]]

Right here’s one other instance of a multiway Turing machine with 3 instances in its rule:

TuringMachinePlot

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; TuringMachinePlot[
 [email protected]{{{{1, 0} -> {1, 0, 1}}, {{1, 0} -> {1, 1, -1}}, {{1, 
       1} -> {1, 0, -1}}}}, 2, 2, "RulePlot"]

The primary few steps in its multiway graph are:

MultiwayTuringMachine

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; With[{t = 3}, 
 MultiwayTuringMachine[{{{1, 0} -> {1, 0, 1}}, {{1, 0} -> {1, 
      1, -1}}, {{1, 1} -> {1, 0, -1}}}, {{1, t + 1}, 
   Table[0, 2 t + 1]}, t, "StatesGraph", AspectRatio -> 1/2, 
  GraphLayout -> "LayeredDigraphEmbedding", 
  VertexSize -> .15 {2 t + 1, 1}, PerformanceGoal -> "High quality"]]

Persevering with for an additional step, issues get extra sophisticated, and, notably, we see a loop:

MultiwayTuringMachine

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; With[{t = 4}, 
 MultiwayTuringMachine[{{{1, 0} -> {1, 0, 1}}, {{1, 0} -> {1, 
      1, -1}}, {{1, 1} -> {1, 0, -1}}}, {{1, t + 1}, 
   Table[0, 2 t + 1]}, t, "StatesGraph", AspectRatio -> 1/2, 
  GraphLayout -> "LayeredDigraphEmbedding", 
  VertexSize -> .15 {2 t + 1, 1}, PerformanceGoal -> "High quality"]]

Persevering with for a couple of extra steps we get:

TMAppliesGraph

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; Graph[
 TMAppliesGraph[{{{1, 0} -> {1, 0, 1}}, {{1, 0} -> {1, 1, -1}}, {{1, 
      1} -> {1, 0, -1}}}, 9], AspectRatio -> .6, 
 EdgeStyle -> 
  Directive[
   ResourceFunction["WolframPhysicsProjectStyleData"]["StatesGraph"][
    "EdgeStyle"], Arrowheads[Small]]]

(Notice that since on this rule there is no such thing as a halting, the dangling ends seen right here should present further development if the evolution is sustained.)

It’s completely doable to get each speedy development, and halting. Right here’s an instance

TuringMachinePlot

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; TuringMachinePlot[
 [email protected]{{{1, 0} -> {1, 1, -1}}, {{1, 0} -> {1, 0, -1}}, {{1, 
      0} -> {1, 1, 1}}}, 2, 2, "RulePlot"]
TMAppliesStatesGraph

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; TMAppliesStatesGraph[{{{1, 
     0} -> {1, 1, -1}}, {{1, 0} -> {1, 0, -1}}, {{1, 0} -> {1, 1, 
     1}}}, 2, 2, 3]

or, persevering with for longer:

TMAppliesGraph

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; Graph[
 TMAppliesGraph[{{{1, 0} -> {1, 1, -1}}, {{1, 0} -> {1, 0, -1}}, {{1, 
      0} -> {1, 1, 1}}}, 6], AspectRatio -> .6]

Visualization and Multispace

It’s pretty simple to get a way of the habits of an odd Turing machine simply by displaying its successive configurations down the web page. However what about for a multiway Turing machine? The multiway graph exhibits one the relationships outlined by evolution between full configurations (states) of the system:

MultiwayTuringMachine

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; Present[
 With[{t = 5}, 
  MultiwayTuringMachine[{{{1, 1} -> {1, 0, -1}}, {{1, 0} -> {1, 
       0, -1}}, {{1, 0} -> {1, 1, 1}}}, {{1, t + 1}, 
    Table[0, 2 t + 1]}, t, "StatesGraph", AspectRatio -> .8, 
   GraphLayout -> "LayeredDigraphEmbedding", 
   VertexSize -> .15 {2 t + 1, 1}, PerformanceGoal -> "High quality"]], 
 Epilog -> 
  Inset[TuringMachinePlot[
    [email protected]{{{1, 1} -> {1, 0, -1}}, {{1, 0} -> {1, 0, -1}}, {{1, 
         0} -> {1, 1, 1}}}, 2, 2, "RulePlot"], 
   ImageScaled[{0.83, 0.9}], Middle, ]]

However such an image doesn’t clarify the relationships between the detailed types of totally different configurations, and for instance the “spatial movement” of the top. So how can we do that?

One chance is in impact to show all of the totally different doable configurations at a given step “overlaid on prime of one another”. For the machine above the brand new configurations obtained at successive steps are (although be aware that these don’t seem on particular layers within the rendering of the multiway graph above):

TuringMachine

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; 
Map[RulePlot[TuringMachine[{0, 2, 2}], [email protected]#, 0, 
    Mesh -> True, ImageSize -> 80] &, 
  With[{t = 3}, 
   NDTMEvolution[{{{1, 1} -> {1, 0, -1}}, {{1, 0} -> {1, 0, -1}}, {{1,
         0} -> {1, 1, 1}}}, t]], {2}] // Column

Placing these “on prime of one another”, and “averaging colours” we get:

TuringMachinePlot

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; With[{t = 8}, 
 TuringMachinePlot[
  NDTMEvolution[{{{1, 1} -> {1, 0, -1}}, {{1, 0} -> {1, 0, -1}}, {{1, 
       0} -> {1, 1, 1}}}, t], 2, 2, "CoarseGrainedEvolutionPlot", 
  Mesh -> True]]

On this case, such a visualization reveals the “diffusive” character of the habits: the movement of the top in numerous doable evolutions successfully corresponds to all doable paths in an ensemble of random walks, in order that the likelihood to seek out the top at offset x is Binomial[tx]/2t.

We are able to see the lattice of paths extra explicitly if we be part of head positions obtained at successive steps of evolution:

HeadTraceGraphics2X

&#10005

Cell[CellGroupData[{Cell[BoxData[
 RowBox[{
  RowBox[{
  "CloudGet", "[", 
   "\"\<https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl\>\"", "]"}], ";"}]], "Enter"],

Cell[BoxData[
 RowBox[{
  RowBox[{"HeadTraceGraphics2X", "[", 
   RowBox[{"rule_", ",", "t_"}], "]"}], ":=", 
  RowBox[{"With", "[", 
   RowBox[{
    RowBox[{"{", 
     RowBox[{"hh", "=", 
      RowBox[{"Flatten", "[", 
       RowBox[{"MapIndexed", "[", 
        RowBox[{
         RowBox[{
          RowBox[{
           RowBox[{"{", 
            RowBox[{
             RowBox[{"First", "[", "#2", "]"}], ",", 
             RowBox[{"#", "[", 
              RowBox[{"[", 
               RowBox[{"1", ",", "1", ",", "3"}], "]"}], "]"}]}], 
            "}"}], "\[Rule]", 
           RowBox[{"{", 
            RowBox[{
             RowBox[{
              RowBox[{"First", "[", "#2", "]"}], "+", "1"}], ",", 
             RowBox[{"#", "[", 
              RowBox[{"[", 
               RowBox[{"2", ",", "1", ",", "3"}], "]"}], "]"}]}], 
            "}"}]}], "&"}], ",", 
         RowBox[{"Rest", "[", 
          RowBox[{"TracedTMEvolution", "[", 
           RowBox[{
            RowBox[{"Flatten", "@", "rule"}], ",", "t"}], "]"}], 
          "]"}], ",", 
         RowBox[{"{", "2", "}"}]}], "]"}], "]"}]}], "}"}], ",", 
    RowBox[{"Graphics", "[", 
     RowBox[{"{", 
      RowBox[{
       RowBox[{"Opacity", "[", "0.2", "]"}], ",", " ", 
       RowBox[{"PointSize", "[", ".01", "]"}], ",", 
       RowBox[{"hh", "/.", 
        RowBox[{
         RowBox[{"(", 
          RowBox[{
           RowBox[{"{", 
            RowBox[{"t1_", ",", "x1_"}], "}"}], "\[Rule]", 
           RowBox[{"{", 
            RowBox[{"t2_", ",", "x2_"}], "}"}]}], ")"}], "\[Rule]", 
         RowBox[{"{", 
          RowBox[{
           RowBox[{"Point", "/@", 
            RowBox[{"{", 
             RowBox[{
              RowBox[{"{", 
               RowBox[{"x1", ",", 
                RowBox[{"-", "t1"}]}], "}"}], ",", 
              RowBox[{"{", 
               RowBox[{"x2", ",", 
                RowBox[{"-", "t2"}]}], "}"}]}], "}"}]}], ",", 
           RowBox[{"Line", "[", 
            RowBox[{"{", 
             RowBox[{
              RowBox[{"{", 
               RowBox[{"x1", ",", 
                RowBox[{"-", "t1"}]}], "}"}], ",", 
              RowBox[{"{", 
               RowBox[{"x2", ",", 
                RowBox[{"-", "t2"}]}], "}"}]}], "}"}], "]"}]}], 
          "}"}]}]}]}], "}"}], "]"}]}], "]"}]}]], "Enter"],

Cell[BoxData[
 RowBox[{"With", "[", 
  RowBox[{
   RowBox[{"{", 
    RowBox[{
     RowBox[{"rules", " ", "=", 
      RowBox[{"{", 
       RowBox[{
        RowBox[{"{", 
         RowBox[{
          RowBox[{"{", 
           RowBox[{"1", ",", "1"}], "}"}], "\[Rule]", 
          RowBox[{"{", 
           RowBox[{"1", ",", "0", ",", 
            RowBox[{"-", "1"}]}], "}"}]}], "}"}], ",", 
        RowBox[{"{", 
         RowBox[{
          RowBox[{"{", 
           RowBox[{"1", ",", "0"}], "}"}], "\[Rule]", 
          RowBox[{"{", 
           RowBox[{"1", ",", "0", ",", 
            RowBox[{"-", "1"}]}], "}"}]}], "}"}], ",", 
        RowBox[{"{", 
         RowBox[{
          RowBox[{"{", 
           RowBox[{"1", ",", "0"}], "}"}], "\[Rule]", 
          RowBox[{"{", 
           RowBox[{"1", ",", "1", ",", "1"}], "}"}]}], "}"}]}], 
       "}"}]}], ",", " ", 
     RowBox[{"t", "=", "8"}]}], "}"}], ",", 
   RowBox[{"TuringMachinePlot", "[", 
    RowBox[{
     RowBox[{"NDTMEvolution", "[", 
      RowBox[{"rules", ",", "t"}], "]"}], ",", "2", ",", "2", ",", 
     "\"\<CoarseGrainedEvolutionPlot\>\"", ",", 
     RowBox[{"Mesh", "\[Rule]", "True"}], ",", " ", 
     RowBox[{"Epilog", " ", "\[Rule]", " ", 
      RowBox[{"Inset", "[", 
       RowBox[{
        RowBox[{"HeadTraceGraphics2X", "[", 
         RowBox[{"rules", ",", "t"}], "]"}], ",", " ", "Middle", ",", 
        " ", "Middle", ",", " ", 
        RowBox[{"ImageScaled", "[", 
         RowBox[{"{", 
          RowBox[{".95", ",", " ", ".95"}], "}"}], "]"}]}], "]"}]}]}],
     "]"}]}], "]"}]], "Enter"]
}, Open  ]]

What does this method reveal about different multiway Turing machines we’ve mentioned? Right here’s one in all our first examples:

TMSummary2

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; TMSummary2[{{{1, 0} -> {1, 
     1, -1}}, {{1, 0} -> {1, 1, 1}}}, 8]

And right here’s one other of our examples:

TMSummary

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; TMSummary[{{{1, 0} -> {1, 1, 
     1}}, {{1, 0} -> {1, 1, -1}}, {{1, 1} -> {1, 0, 1}}}, 8]

However usually this sort of averaged image just isn’t notably useful. So is there another? Principally we want some option to concurrently visualize each multiway construction, and the detailed types of particular person configurations.

In analogy to our Physics Project, that is primarily the issue of concurrently visualizing each branchial and spatial construction. So the place ought to we begin? Since our on a regular basis expertise is with odd house, not branchial house, it appears probably higher to start out with odd house, after which add within the branchial element. And fascinated by this led to the concept of multispace: a generalization of house in which there’s in impact at each level a stack of multiway potentialities, with these totally different potentialities being related at totally different locations in branchial house.

In our Physics Venture, even visualizing ordinary space itself is difficult, as a result of it’s constructed up from lower-level constructions akin to hypergraphs. However for Turing machines the essential construction of house is constrained to be quite simple: there may be only a one-dimensional tape with a head that may go backwards and forwards on it.

However in understanding multispace, it’s in all probability simpler to start out from the branchial aspect. Let’s for now ignore the values written on the tape of a Turing machine, and contemplate solely the place of the top, say relative to the place it began. Each state within the multiway graph can then be labeled with the place of the top in that configuration of the Turing machine. So for the primary rule above we get:

TMAppliesGraph

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; With[{ggg = 
   TMAppliesGraph[{{{1, 0} -> {1, 1, -1}}, {{1, 0} -> {1, 1, 1}}}, 
    6]}, Graph[ggg, 
  VertexLabels -> (# -> Placed[ToExpression[#][[1, 3]], After] & /@ 
     VertexList[ggg]), ImageSize -> 200]]

However now let’s think about setting this up in 3D, with the timelike route down the web page, the branchlike route throughout the web page, and the spacelike route into the web page:

TMAppliesMultispaceRailed

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; \
TMAppliesMultispaceRailed[{{{1, 0} -> {1, 1, -1}}, {{1, 0} -> {1, 1, 
     1}}}, 6, {.6, 2}, Boxed -> True, Axes -> True, 
 Ticks -> {None, None, None}, 
 AxesLabel -> {"branchlike", "spacelike", "timelike"}, 
 ViewPoint -> {0, -5, 0}, 
 PlotRangePadding -> {Automatic, Automatic, -1.5}]

But when we now rotate this, we will see the interaction of branchial and spatial construction:

Click to copy input and view animation

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; Animate[
 TMAppliesMultispaceRailed[{{{1, 0} -> {1, 1, -1}}, {{1, 0} -> {1, 1, 
      1}}}, 12, {.6, 2}, Boxed -> True, Axes -> True, 
  Ticks -> {None, Automatic, None}, 
  AxesLabel -> {"branchlike", "spacelike", "timelike"}, 
  ViewPoint -> {5 Sin[\[Theta]], -5 Cos[\[Theta]], 0}, 
  PlotRangePadding -> {Automated, 
    Automated, {-1.5, -2.5}}], {\[Theta], 0, Pi/2}, 
 AnimationDirection -> ForwardBackward, AnimationRunning -> False]

On this specific case, we see that the principle branches seen within the multiway system (i.e. within the branchlike route) correspond to progressively extra separated positions of the top within the spacelike route.

Issues are usually not at all times this straightforward. Right here’s the head-position-annotated multiway graph for the Turing machine from the start of this part:

MultiwayTuringMachine

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; With[{t = 5}, 
 With[{ggg = 
    ResourceFunction[
      "MultiwayTuringMachine"][{{{1, 1} -> {1, 0, -1}}, {{1, 0} -> {1,
          0, -1}}, {{1, 0} -> {1, 1, 1}}}, {{1, t + 1, 0}, 
      Table[0, 2 t + 1]}, t, "StatesGraphStructure", AspectRatio -> 1,
      GraphLayout -> "LayeredDigraphEmbedding"]}, 
  Graph[ggg, 
   VertexLabels -> (# -> ToExpression[#][[1, 3]] & /@ 
      VertexList[ggg])]]]

And now right here’s a 3D view of the evolution of this Turing machine in multispace. First we’re successfully projecting into the branchtime aircraft. Notice nonetheless that as a result of connections will be made in 3D, the structure chosen for the rendering is totally different from what will get chosen when the multiway graph is rendered in 2D:

Click to copy input and view animation

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; Animate[
 TMAppliesMultispaceRailed[{{{1, 1} -> {1, 0, -1}}, {{1, 0} -> {1, 
      0, -1}}, {{1, 0} -> {1, 1, 1}}}, 5, {.6, 1.5}, Boxed -> True, 
  Axes -> True, Ticks -> {None, None, None}, 
  AxesLabel -> {"branchlike", "spacelike", "timelike"}, 
  ViewPoint -> {5 Sin[\[Theta]], -5 Cos[\[Theta]], 0}, 
  PlotRangePadding -> {Automated, Automated, {-1.5, -3}}], {\[Theta], 
  0, Pi/2}, AnimationDirection -> ForwardBackward, 
 AnimationRunning -> False]

Rotating in multispace we will see the interaction between branchlike and spacelike construction:

Click to copy input and view animation

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; AnimatedTMMultispace[{{{1, 
     1} -> {1, 0, -1}}, {{1, 0} -> {1, 0, -1}}, {{1, 0} -> {1, 1, 
     1}}}, 5, {.6, 1.5}]

Even for this comparatively easy multiway Turing machine, it’s already fairly tough to inform what’s happening. However persevering with for a couple of extra steps, one can see particular patterns in multispace (the narrowing on the backside displays the truth that that is run just for a finite variety of steps; it could fill in if one ran it for longer):

Click to copy input and view animation

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; AnimatedTMMultispace[{{{1, 
     1} -> {1, 0, -1}}, {{1, 0} -> {1, 0, -1}}, {{1, 0} -> {1, 1, 
     1}}}, 10]

In our Physics Venture, there is no such thing as a intrinsic coordinatization of both bodily house or branchial house—so any coordinatization should be purely emergent. However the fundamental construction of Turing machines implies a direct definition of house and time coordinates—which is what we use within the photos above to position nodes within the spacelike and timelike instructions. (The timelike route is barely refined: we’re assigning a coordinate based mostly on the place a state seems within the layering of the multiway graph, which can or will not be the “time step” at which it first seems.) However in Turing machines there is no such thing as a rapid definition of branchial coordinates—and within the photos above we’re deriving branchial coordinates from the (considerably arbitrary) structure used within the 2D rendering of the multiway graph.

So is there a greater different? In impact, what one has to do is to seek out some good option to coordinatize the entire state of the Turing machine, together with the configuration of its tape. One chance is simply to deal with the configuration of the tape as defining a base-okay quantity—after which for instance to compute a coordinate from the log of this quantity. (One also can think about shifting the quantity in order that its “decimal” level is on the place of the top, however the head place is in a way already “dealt with” by the spatial coordinate.) Right here’s the end result from doing this for the Turing machine above:

Click to copy input and view animation

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; \
AnimatedTMMultispaceIndicator[{{{1, 1} -> {1, 0, -1}}, {{1, 0} -> {1, 
     0, -1}}, {{1, 0} -> {1, 1, 1}}}, 10, {2, 1, 5}]

Listed here are a few different examples:

Click to copy input and view animation

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; Row[{Column[{Show[
     TMAppliesMultispaceIndicator[{{{1, 0} -> {1, 0, -1}}, {{1, 
          0} -> {1, 1, 1}}}, 6], Boxed -> True, Boxed -> True, 
     Axes -> True, Ticks -> , 
     AxesLabel -> {"branchlike", "spacelike", "timelike"}, 
     ViewPoint -> {5 Sin[Pi/4], -5 Cos[Pi/4], 0}, 
     ImageSize -> ], 
    TuringMachinePlot[{{{1, 0} -> {1, 0, -1}}, {{1, 0} -> {1, 1, 
         1}}}, 2, 2, "RulePlot", ImageSize -> {Automatic, 35}]}, 
   Middle], 
  Column[{Show[
     TMAppliesMultispaceIndicator[{{{1, 0} -> {1, 0, 1}}, {{1, 
          0} -> {1, 1, -1}}, {{1, 1} -> {1, 0, -1}}}, 6], 
     Boxed -> True, Boxed -> True, Axes -> True, 
     Ticks -> , 
     AxesLabel -> {"branchlike", "spacelike", "timelike"}, 
     ViewPoint -> {5 Sin[Pi/4], -5 Cos[Pi/4], 0}, 
     ImageSize -> ], 
    TuringMachinePlot[{{{1, 0} -> {1, 0, 1}}, {{1, 0} -> {1, 
         1, -1}}, {{1, 1} -> {1, 0, -1}}}, 2, 2, "RulePlot", 
     ImageSize -> {Automatic, 35}]}, Middle]}]

Interested by tape configurations suggests one other visualization: simply stack up all tape configurations that may be generated on successive steps. Within the case of the rule

TuringMachinePlot

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; TuringMachinePlot[{{{1, 
     0} -> {1, 1, 1}}, {{1, 0} -> {1, 0, 1}}}, 2, 2, "RulePlot"]

one simply will get at step t the binary digits of successive integers 0 by 2t–1 on the tape:

TuringMachinePlot

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; 
TuringMachinePlot[#, 2, 2, "EvolutionPlot", Mesh -> All, 
   MeshStyle -> {Dotted, Directive[{}]}, Body -> None] & /@ 
 Map[ToExpression, 
  With[{t = 5}, 
   MultiwayTuringMachine[{{{1, 0} -> {1, 1, 1}}, {{1, 0} -> {1, 0, 
        1}}}, {{1, t + 1, 0}, Table[0, 2 t + 1]}, t]], {2}]

However even for a rule like

TuringMachinePlot

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; TuringMachinePlot[{{{1, 
     0} -> {1, 1, -1}}, {{1, 0} -> {1, 0, 1}}}, 2, 2, "RulePlot"]

the result’s extra sophisticated

TMAppliesQ

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; With[{t = 9, 
  rules = {{{1, 0} -> {1, 1, -1}}, {{1, 0} -> {1, 0, 1}}}},
 MapIndexed[
  Module[{halted, states},
    halted = 
     Flatten[Position[TMAppliesQ[rules, #] & /@ [email protected]#1, False]];
    states = Size[#1];
    halted = 
     Graphics[
      Append[{Opacity[0.05], Darker[Red, .7]}, 
       Rectangle[{0, states - (# - 1)}, {2 t + 1, states - (#)}] & /@ 
        halted]];
    Present[TuringMachinePlot[[email protected]#1, 2, 2, "EvolutionPlot", 
      Mesh -> If[First[#2] < 7, All, None], 
      Body -> If[First[#2] < 7, None, Automated], 
      MeshStyle -> {Dotted, Directive[{}]}], halted]] &, 
  Map[ToExpression, 
   MultiwayTuringMachine[rules, {{1, t + 1, 0}, Table[0, 2 t + 1]}, 
    t], {2}]
  ]]

the place now the grayed rows correspond to states on which the Turing machine has already halted.

After we assemble a multiway graph—and render it in multispace or elsewhere—we’re immediately representing the evolution of states of one thing like a multiway Turing machine. However notably the research of quantum mechanics in our Physics Venture emphasizes the significance of a complementary view—of wanting not on the evolution of particular person states, however moderately at relationships (or “entanglements”) between states outlined by their frequent ancestry within the multiway graph.

Take into account the rule

TuringMachinePlot

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; TuringMachinePlot[
 [email protected]{{{1, 0} -> {1, 1, 1}}, {{1, 0} -> {1, 1, -1}}, {{1, 
      1} -> {1, 0, 1}}}, 2, 2, "RulePlot"]

that generates a multiway graph:

MultiwayTuringMachine

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; With[{t = 5}, 
 MultiwayTuringMachine[{{{1, 0} -> {1, 1, 1}}, {{1, 0} -> {1, 
      1, -1}}, {{1, 1} -> {1, 0, 1}}}, {{1, t + 1}, 
   Table[0, 2 t + 1]}, t, "StatesGraphStructure", 
  GraphLayout -> "LayeredDigraphEmbedding"]]

Now make a foliation of this graph:

MultiwayTuringMachine

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; Graph[
 With[{t = 5}, 
  MultiwayTuringMachine[{{{1, 0} -> {1, 1, 1}}, {{1, 0} -> {1, 
       1, -1}}, {{1, 1} -> {1, 0, 1}}}, {{1, t + 1, 0}, 
    Table[0, 2 t + 1]}, t, "StatesGraphStructure", 
   GraphLayout -> "LayeredDigraphEmbedding"]], 
 Epilog -> {ResourceFunction["WolframPhysicsProjectStyleData"][
    "BranchialGraph", "EdgeStyle"], AbsoluteThickness[1], 
   Desk[Line[{{-10, i}, {9, i}}], {i, .4, 6, 1}]}]

If we take a look at the final slice right here, there are a number of pairs of nodes which have frequent ancestors—every coming from using totally different instances within the authentic rule. The branchial graph that joins configurations (nodes) with rapid frequent ancestors is, nonetheless, moderately trivial:

MultiwayTuringMachine

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; Framed[
 With[{t = 5}, 
  MultiwayTuringMachine[{{{1, 0} -> {1, 1, 1}}, {{1, 0} -> {1, 1, -1}}, {{1, 1} -> {1, 0, 1}}}, {{1, t + 1, 0}, Table[0, 2 t + 1]}, t, "BranchialGraph", VertexSize -> 4]], 
 FrameStyle -> LightGray]

However even for the rule

TuringMachinePlot

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; TuringMachinePlot[
 [email protected]{{{{1, 0} -> {1, 1, -1}}, {{1, 0} -> {1, 0, -1}}, {{1, 
       0} -> {1, 1, 1}}, {{1, 0} -> {1, 0, 1}}}}, 2, 2, "RulePlot"]

with multiway graph

MultiwayTuringMachine

&#10005

Cell[CellGroupData[{Cell[BoxData[
 RowBox[{
  RowBox[{
  "CloudGet", "[", 
   "\"\<https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl\>\"", "]"}], ";"}]], "Enter"],

Cell[BoxData[
 RowBox[{
  RowBox[{"mwcoords", " ", "=", " ", 
   RowBox[{"{", 
    RowBox[{
     RowBox[{"\"\<{{1, 4}, {0, 0, 0, 0, 0, 0, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "4"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 3}, {0, 0, 0, 0, 0, 0, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "3"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 3}, {0, 0, 0, 1, 0, 0, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "3"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 5}, {0, 0, 0, 0, 0, 0, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "3"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 5}, {0, 0, 0, 1, 0, 0, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "3"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 2}, {0, 0, 0, 0, 0, 0, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "2"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 2}, {0, 0, 0, 1, 0, 0, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "2"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 2}, {0, 0, 1, 0, 0, 0, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "2"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 2}, {0, 0, 1, 1, 0, 0, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "2"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 4}, {0, 0, 0, 0, 1, 0, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "2"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 4}, {0, 0, 0, 1, 0, 0, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "2"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 4}, {0, 0, 0, 1, 1, 0, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "2"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 4}, {0, 0, 1, 0, 0, 0, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "2"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 4}, {0, 0, 1, 1, 0, 0, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "2"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 6}, {0, 0, 0, 0, 0, 0, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "2"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 6}, {0, 0, 0, 0, 1, 0, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "2"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 6}, {0, 0, 0, 1, 0, 0, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "2"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 6}, {0, 0, 0, 1, 1, 0, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "2"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 1}, {0, 0, 0, 0, 0, 0, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "1"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 1}, {0, 0, 0, 1, 0, 0, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "1"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 1}, {0, 0, 1, 0, 0, 0, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "1"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 1}, {0, 0, 1, 1, 0, 0, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "1"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 1}, {0, 1, 0, 0, 0, 0, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "1"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 1}, {0, 1, 0, 1, 0, 0, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "1"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 1}, {0, 1, 1, 0, 0, 0, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "1"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 1}, {0, 1, 1, 1, 0, 0, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "1"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 3}, {0, 0, 0, 0, 1, 0, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "1"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 3}, {0, 0, 0, 1, 1, 0, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "1"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 3}, {0, 0, 1, 0, 0, 0, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "1"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 3}, {0, 0, 1, 1, 0, 0, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "1"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 3}, {0, 1, 0, 0, 0, 0, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "1"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 3}, {0, 1, 0, 1, 0, 0, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "1"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 3}, {0, 1, 1, 0, 0, 0, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "1"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 3}, {0, 1, 1, 1, 0, 0, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "1"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 5}, {0, 0, 0, 0, 0, 1, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "1"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 5}, {0, 0, 0, 0, 1, 0, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "1"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 5}, {0, 0, 0, 0, 1, 1, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "1"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 5}, {0, 0, 0, 1, 0, 1, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "1"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 5}, {0, 0, 0, 1, 1, 0, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "1"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 5}, {0, 0, 0, 1, 1, 1, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "1"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 5}, {0, 0, 1, 0, 0, 0, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "1"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 5}, {0, 0, 1, 1, 0, 0, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "1"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 7}, {0, 0, 0, 0, 0, 0, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "1"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 7}, {0, 0, 0, 0, 0, 1, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "1"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 7}, {0, 0, 0, 0, 1, 0, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "1"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 7}, {0, 0, 0, 0, 1, 1, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "1"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 7}, {0, 0, 0, 1, 0, 0, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "1"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 7}, {0, 0, 0, 1, 0, 1, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "1"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 7}, {0, 0, 0, 1, 1, 0, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "1"}], "}"}]}], ",", 
     RowBox[{"\"\<{{1, 7}, {0, 0, 0, 1, 1, 1, 0}}\>\"", "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"Automatic", ",", "1"}], "}"}]}]}], "}"}]}], 
  ";"}]], "Enter"],

Cell[BoxData[
 RowBox[{"With", "[", 
  RowBox[{
   RowBox[{"{", 
    RowBox[{"t", "=", "3"}], "}"}], ",", " ", 
   RowBox[{"MultiwayTuringMachine", "[", 
    RowBox[{
     RowBox[{"{", 
      RowBox[{
       RowBox[{"{", 
        RowBox[{
         RowBox[{"{", 
          RowBox[{"1", ",", "0"}], "}"}], "\[Rule]", 
         RowBox[{"{", 
          RowBox[{"1", ",", "1", ",", 
           RowBox[{"-", "1"}]}], "}"}]}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{
         RowBox[{"{", 
          RowBox[{"1", ",", "0"}], "}"}], "\[Rule]", 
         RowBox[{"{", 
          RowBox[{"1", ",", "0", ",", 
           RowBox[{"-", "1"}]}], "}"}]}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{
         RowBox[{"{", 
          RowBox[{"1", ",", "0"}], "}"}], "\[Rule]", 
         RowBox[{"{", 
          RowBox[{"1", ",", "1", ",", "1"}], "}"}]}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{
         RowBox[{"{", 
          RowBox[{"1", ",", "0"}], "}"}], "\[Rule]", 
         RowBox[{"{", 
          RowBox[{"1", ",", "0", ",", "1"}], "}"}]}], "}"}]}], "}"}], 
     ",", 
     RowBox[{"{", 
      RowBox[{
       RowBox[{"{", 
        RowBox[{"1", ",", 
         RowBox[{"t", "+", "1"}]}], "}"}], ",", 
       RowBox[{"Table", "[", 
        RowBox[{"0", ",", 
         RowBox[{
          RowBox[{"2", "t"}], "+", "1"}]}], "]"}]}], "}"}], ",", "t", 
     ",", "\"\<StatesGraphStructure\>\"", ",", " ", 
     RowBox[{"GraphLayout", " ", "\[Rule]", " ", 
      RowBox[{"{", 
       RowBox[{"\"\<LayeredDigraphEmbedding\>\"", ",", " ", 
        RowBox[{"\"\<RootVertex\>\"", " ", "\[Rule]", " ", 
         RowBox[{"ToString", "[", 
          RowBox[{"{", 
           RowBox[{
            RowBox[{"{", 
             RowBox[{"1", ",", 
              RowBox[{"t", "+", "1"}]}], "}"}], ",", 
            RowBox[{"Table", "[", 
             RowBox[{"0", ",", 
              RowBox[{
               RowBox[{"2", "t"}], "+", "1"}]}], "]"}]}], "}"}], 
          "]"}]}]}], "}"}]}], ",", " ", 
     RowBox[{"VertexCoordinates", " ", "\[Rule]", "mwcoords"}], ",", 
     " ", 
     RowBox[{"Epilog", " ", "\[Rule]", " ", 
      RowBox[{"{", 
       RowBox[{
        RowBox[{
         RowBox[{
         "ResourceFunction", "[", 
          "\"\<WolframPhysicsProjectStyleData\>\"", "]"}], "[", 
         RowBox[{"\"\<BranchialGraph\>\"", ",", "\"\<EdgeStyle\>\""}],
          "]"}], ",", 
        RowBox[{"AbsoluteThickness", "[", "1.5", "]"}], ",", 
        RowBox[{"Table", "[", 
         RowBox[{
          RowBox[{"Line", "[", 
           RowBox[{"{", 
            RowBox[{
             RowBox[{"{", 
              RowBox[{
               RowBox[{"-", "14"}], ",", "i"}], "}"}], ",", 
             RowBox[{"{", 
              RowBox[{"19", ",", "i"}], "}"}]}], "}"}], "]"}], ",", 
          RowBox[{"{", 
           RowBox[{"i", ",", "1.5", ",", "4", ",", " ", "1"}], 
           "}"}]}], "]"}]}], "}"}]}]}], "]"}]}], "]"}]], "Enter"]
}, Open  ]]

the branchial graphs on successive steps are barely much less easy:

MultiwayTuringMachine

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; Desk[
 Framed[MultiwayTuringMachine[{{{1, 0} -> {1, 1, -1}}, {{1, 0} -> {1, 
       0, -1}}, {{1, 0} -> {1, 1, 1}}, {{1, 0} -> {1, 0, 1}}}, {{1, 
     t + 1, 0}, Table[0, 2 t + 1]}, t, "BranchialGraphStructure", 
   ImageSize -> ], FrameStyle -> LightGray], {t, 1, 
  4}]

One also can assemble “thickened branchial graphs” through which one looks not just at immediate common ancestors, however say at frequent ancestors as much as τ steps again. For τ > 1 the result’s a hypergraph, and even within the first case right here, it may be considerably nontrivial:

WolframModelPlot

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; Desk[
 Framed[ResourceFunction["WolframModelPlot"][
   Select[Union[
     Take[#, UpTo[3]] & /@ 
      ResourceFunction["BranchialHypergraph"][
       IndexGraph[
        MultiwayTuringMachine[{{{1, 0} -> {1, 1, 1}}, {{1, 0} -> {1, 
             1, -1}}, {{1, 1} -> {1, 0, 1}}}, {{1, t + 1, 0}, 
          Table[0, 2 t + 1]}, t, "StatesGraphStructure", 
         AspectRatio -> 1, 
         GraphLayout -> "LayeredDigraphEmbedding"]]]], 
    Size[#] > 1 &], ImageSize -> , 
   Sequence @@ 
    ResourceFunction["WolframPhysicsProjectStyleData"][
      "BranchialGraph"]["Options"]], FrameStyle -> LightGray], {t, 2, 
  4}]

The World of Easy Multiway Turing Machines

Until an odd Turing machine has each at the very least s = 2 states and okay = 2 colours it should at all times have primarily trivial habits. However what about multiway Turing machines? With okay = 1 coloration the system in impact can’t retailer something on the tape, and it should at all times “do the identical dance” at no matter place the top is in.

Take into account for instance the s = 2 rule:

TuringMachinePlot

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; TuringMachinePlot[
 [email protected][{{{{1, 0} -> {1, 0, -1}}, {{1, 0} -> {2, 0, 1}}, {{2, 
        0} -> {1, 0, 1}}}}], 2, 2, "RulePlot"]

The states of this technique will be represented within the kind {σi} the place σ is the top state, and i is the place of the top. The multiway graph for the evolution of the system after 3 steps ranging from a clean tape with the top in head state 1 can then be drawn as (with the coordinates of every state being decided from {σi}):

MultiwayTuringMachine

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; With[{t = 3}, 
 With[{ggg = 
    ResourceFunction["MultiwayTuringMachine"][
     First[{{{{1, 0} -> {1, 0, -1}}, {{1, 0} -> {2, 0, 1}}, {{2, 
           0} -> {1, 0, 1}}}}], {{1, t + 1, 0}, Desk[0, 2 t + 1]}, t,
      "StatesGraphStructure"]}, 
  Graph[ggg, 
   VertexLabels -> (# -> ToString[ToExpression[#][[1, {1, 3}]]] & /@ 
      VertexList[ggg]), 
   VertexCoordinates -> (# -> ToExpression[#][[1, {3, 1}]] & /@ 
      VertexList[ggg])]]]

Persevering with longer we get

MultiwayTuringMachine

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; With[{t = 5}, 
 With[{ggg = 
    ResourceFunction["MultiwayTuringMachine"][
     First[{{{{1, 0} -> {1, 0, -1}}, {{1, 0} -> {2, 0, 1}}, {{2, 
           0} -> {1, 0, 1}}}}], {{1, t + 1, 0}, Desk[0, 2 t + 1]}, t,
      "StatesGraphStructure"]}, 
  Graph[ggg, 
   VertexLabels -> (# -> ToString[ToExpression[#][[1, {1, 3}]]] & /@ 
      VertexList[ggg]), 
   VertexCoordinates -> (# -> ToExpression[#][[1, {3, 1}]] & /@ 
      VertexList[ggg])]]]

and we will see that finally the multiway graph is successfully a repeating braid—although with “barely frayed” ends at any given step. The braid will be constructed from a sequence of “motifs”, right here consisting of three “vectors”, the place every vector is immediately decided by a case within the underlying rule, or on this case:

ruleToMotif

&#10005

Cell[CellGroupData[{Cell[BoxData[
 RowBox[{
  RowBox[{"ruleToMotif", "[", "rule_", "]"}], ":=", 
  RowBox[{"Graphics", "[", 
   RowBox[{"{", 
    RowBox[{
     RowBox[{"Arrowheads", "[", "Large", "]"}], ",", 
     RowBox[{
      RowBox[{"Arrow", "/@", 
       RowBox[{"Map", "[", 
        RowBox[{"Reverse", ",", 
         RowBox[{
          RowBox[{
           RowBox[{"#1", "\[Rule]", 
            RowBox[{"Delete", "[", 
             RowBox[{"#2", ",", "2"}], "]"}]}], "&"}], "@@@", 
          RowBox[{"Flatten", "[", "rule", "]"}]}], ",", 
         RowBox[{"{", "2", "}"}]}], "]"}]}], "/.", 
      RowBox["Rule", "\[Rule]", "Checklist"]}]}], "}"}], 
   "]"}]}]], "Enter"],

Cell[BoxData[
 RowBox[{"ruleToMotif", "[", 
  RowBox[{"{", 
   RowBox[{
    RowBox[{"{", 
     RowBox[{
      RowBox[{"{", 
       RowBox[{"1", ",", "0"}], "}"}], "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"1", ",", "0", ",", 
        RowBox[{"-", "1"}]}], "}"}]}], "}"}], ",", 
    RowBox[{"{", 
     RowBox[{
      RowBox[{"{", 
       RowBox[{"1", ",", "0"}], "}"}], "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"2", ",", "0", ",", "1"}], "}"}]}], "}"}], ",", 
    RowBox[{"{", 
     RowBox[{
      RowBox[{"{", 
       RowBox[{"2", ",", "0"}], "}"}], "\[Rule]", 
      RowBox[{"{", 
       RowBox[{"1", ",", "0", ",", "1"}], "}"}]}], "}"}]}], "}"}], 
  "]"}]], "Enter"]
}, Open  ]]

If we take a look at all s = 2 multiway Turing machines with 3 instances of their guidelines, these are the multiway graph constructions we get:

MultiwayTuringMachine

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; Choose[
 UndirectedGraph[#[[1, 1]], ImageSize -> 80] & /@ 
  GatherBy[ResourceFunction["ParallelMapMonitored"][
    With[{t = 5}, 
       With[{ggg = 
          ResourceFunction["MultiwayTuringMachine"][#, {{1, t + 1, 0},
             Table[0, 2 t + 1]}, t, "StatesGraphStructure"]}, 
        Graph[ggg, 
         VertexCoordinates -> (# -> ToExpression[#][[1, {3, 1}]] & /@ 
            VertexList[ggg])]]] -> # &, 
    Choose[Subsets[List /@ TMRuleCases[2, 1], {3}], 
     [email protected]*TestDeterministic]], #[[1]] &], VertexCount[#] > 1 &]

In all instances, the efficient repetition size for any path is 1, 2 or 4.

With s = 3 doable head states, barely extra elaborate multiway graphs develop into doable. For instance

TuringMachinePlot

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; TuringMachinePlot[
 [email protected]{{{1, 0} -> {2, 0, -1}}, {{1, 0} -> {3, 0, 1}}, {{2, 
      0} -> {1, 0, -1}}, {{3, 0} -> {2, 0, 1}}}, 3, 2, "RulePlot"]

offers the “8-cycle braid”:

TuringMachinePlot

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; With[{t = 8}, 
 With[{ggg = 
    ResourceFunction[
      "MultiwayTuringMachine"][{{{1, 0} -> {2, 0, -1}}, {{1, 0} -> {3,
          0, 1}}, {{2, 0} -> {1, 0, -1}}, {{3, 0} -> {2, 0, 1}}}, {{1,
        t + 1, 0}, Table[0, 2 t + 1]}, t, "StatesGraphStructure"]}, 
  Graph[ggg, 
   VertexLabels -> (# -> ToString[ToExpression[#][[1, {1, 3}]]] & /@ 
      VertexList[ggg]), 
   VertexCoordinates -> (# -> ToExpression[#][[1, {3, 1}]] & /@ 
      VertexList[ggg])]]]

To get past “pure-braid” multiway graphs, we should contemplate okay ≥ 2 colours. However what occurs if we use only one head state s = 1 (so we principally have a “mobile automaton” with guidelines of vary 0)?

For s = 1, okay = 2, there are 8 doable instances that may happen within the rule

TuringMachinePlot

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; Row[
 TuringMachinePlot[{#}, 2, 2, "RulePlot", ImageSize -> 50] & /@ 
  TMRuleCasesSorted[1, 2], Spacer[1]]

and thus 256 doable multiway Turing machines, of which 231 are usually not “purely deterministic”.

If we permit solely p = 2 doable instances within the rule, there are 28 doable machines, of which 12 are usually not purely deterministic, and the distinct doable nontrivial types of multiway graphs that we will get are simply (the place within the first rule the second coloration just isn’t used):

CloudGet

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; 
Labeled[Show[TMAppliesGraphUntil[#, 30], 
    ImageSize -> ], 
   TuringMachinePlot[#, 2, 2, "RulePlot", 
    ImageSize -> {Automatic, 40}]] & /@ {{{{1, 0} -> {1, 0, -1}}, {{1,
       0} -> {1, 0, 1}}}, {{{1, 0} -> {1, 1, -1}}, {{1, 0} -> {1, 
      0, -1}}}, {{{1, 0} -> {1, 1, -1}}, {{1, 0} -> {1, 1, 1}}}, {{{1,
       0} -> {1, 1, -1}}, {{1, 0} -> {1, 0, 1}}}}

With p = 3 doable instances within the rule, there are 56 doable machines, none purely deterministic. The distinct multiway graphs they generate are:

TMAppliesGraphUntil

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; 
ResourceFunction["ParallelMapMonitored"][
 Labeled[Show[TMAppliesGraphUntil[#, 200], 
    ImageSize -> ], 
   TuringMachinePlot[#, 2, 2, "RulePlot", 
    ImageSize -> {Automatic, 30}]] &, {{{{1, 1} -> {1, 1, -1}}, {{1, 
      0} -> {1, 1, -1}}, {{1, 0} -> {1, 1, 1}}}, {{{1, 1} -> {1, 
      1, -1}}, {{1, 0} -> {1, 1, -1}}, {{1, 0} -> {1, 0, 1}}}, {{{1, 
      1} -> {1, 1, -1}}, {{1, 0} -> {1, 0, -1}}, {{1, 0} -> {1, 1, 
      1}}}, {{{1, 1} -> {1, 0, -1}}, {{1, 0} -> {1, 1, -1}}, {{1, 
      0} -> {1, 1, 1}}}, {{{1, 1} -> {1, 0, -1}}, {{1, 0} -> {1, 
      1, -1}}, {{1, 0} -> {1, 0, 1}}}, {{{1, 1} -> {1, 0, -1}}, {{1, 
      0} -> {1, 0, -1}}, {{1, 0} -> {1, 1, 1}}}, {{{1, 1} -> {1, 1, 
      1}}, {{1, 0} -> {1, 1, -1}}, {{1, 0} -> {1, 1, 1}}}, {{{1, 
      1} -> {1, 1, 1}}, {{1, 0} -> {1, 0, -1}}, {{1, 0} -> {1, 1, 
      1}}}, {{{1, 1} -> {1, 0, 1}}, {{1, 0} -> {1, 1, -1}}, {{1, 
      0} -> {1, 0, 1}}}, {{{1, 1} -> {1, 0, 1}}, {{1, 0} -> {1, 
      0, -1}}, {{1, 0} -> {1, 1, 1}}}, {{{1, 0} -> {1, 1, -1}}, {{1, 
      0} -> {1, 0, -1}}, {{1, 0} -> {1, 1, 1}}}, {{{1, 0} -> {1, 
      1, -1}}, {{1, 0} -> {1, 0, -1}}, {{1, 0} -> {1, 0, 1}}}}]

A few of these we’ve already seen above. However it’s exceptional how complicated these graphs seem like.

Laying the graphs out in multispace, nonetheless, some present very clear regularities:

TMAppliesMultispaceIndicatorUntil

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; Grid[
 Partition[
  ResourceFunction["ParallelMapMonitored"][
   Column[{Show[
       Graph3D[TMAppliesMultispaceIndicatorUntil[#, 50], 
        EdgeShapeFunction -> "Line"], Lighting -> "Impartial", 
       Boxed -> True, ViewProjection -> "Orthographic"], 
      TuringMachinePlot[#, 2, 2, "RulePlot", 
       ImageSize -> {Automatic, 30}]}, Middle, ItemSize -> 15, 
     Spacings -> 
      None] &, {{{{1, 1} -> {1, 1, -1}}, {{1, 0} -> {1, 1, -1}}, {{1, 
        0} -> {1, 1, 1}}}, {{{1, 1} -> {1, 1, -1}}, {{1, 0} -> {1, 
        1, -1}}, {{1, 0} -> {1, 0, 1}}}, {{{1, 1} -> {1, 1, -1}}, {{1,
         0} -> {1, 0, -1}}, {{1, 0} -> {1, 1, 1}}}, {{{1, 1} -> {1, 
        0, -1}}, {{1, 0} -> {1, 1, -1}}, {{1, 0} -> {1, 1, 1}}}, {{{1,
         1} -> {1, 0, -1}}, {{1, 0} -> {1, 1, -1}}, {{1, 0} -> {1, 0, 
        1}}}, {{{1, 1} -> {1, 0, -1}}, {{1, 0} -> {1, 0, -1}}, {{1, 
        0} -> {1, 1, 1}}}, {{{1, 1} -> {1, 1, 1}}, {{1, 0} -> {1, 
        1, -1}}, {{1, 0} -> {1, 1, 1}}}, {{{1, 1} -> {1, 1, 1}}, {{1, 
        0} -> {1, 0, -1}}, {{1, 0} -> {1, 1, 1}}}, {{{1, 1} -> {1, 0, 
        1}}, {{1, 0} -> {1, 1, -1}}, {{1, 0} -> {1, 0, 1}}}, {{{1, 
        1} -> {1, 0, 1}}, {{1, 0} -> {1, 0, -1}}, {{1, 0} -> {1, 1, 
        1}}}, {{{1, 0} -> {1, 1, -1}}, {{1, 0} -> {1, 0, -1}}, {{1, 
        0} -> {1, 1, 1}}}, {{{1, 0} -> {1, 1, -1}}, {{1, 0} -> {1, 
        0, -1}}, {{1, 0} -> {1, 0, 1}}}}], 4], Spacings -> {-1, 1}]

If we take a look at the sophisticated instances for extra steps, we nonetheless see appreciable complexity:

CloudGet

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; Grid[{ResourceFunction[
    "ParallelMapMonitored"][
   Column[{Labeled[
       Magnify[Show[
         TMAppliesMultispaceIndicatorUntil[#, 300, {1, 1, 6}, 
          PlotTheme -> "LargeGraph"], Lighting -> "Impartial", 
         ViewProjection -> "Orthographic", Boxed -> True], 1.2], 
       TuringMachinePlot[#, 2, 2, "RulePlot", 
        ImageSize -> {Automatic, 30}]]}, Middle, 
     Spacings -> 
      None] &, {{{{1, 1} -> {1, 0, -1}}, {{1, 0} -> {1, 1, -1}}, {{1, 
        0} -> {1, 1, 1}}}, {{{1, 1} -> {1, 0, -1}}, {{1, 0} -> {1, 
        1, -1}}, {{1, 0} -> {1, 0, 1}}}, {{{1, 1} -> {1, 0, 1}}, {{1, 
        0} -> {1, 0, -1}}, {{1, 0} -> {1, 1, 1}}}}]}, 
 Spacings -> {0.05, 0}]

The variety of states reached at successive steps for the primary rule is

MultiwayTuringMachine

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; With[{t = 15}, 
 MultiwayTuringMachine[{{{1, 1} -> {1, 0, -1}}, {{1, 0} -> {1, 1, -1}}, {{1, 0} -> {1, 1, 1}}}, {{1, t + 1}, 
   Table[0, 2 t + 1]}, t, "StatesCountsList"]]

whereas for the opposite two it’s:

MultiwayTuringMachine

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; With[{t = 15}, 
 MultiwayTuringMachine[{{{1, 1} -> {1, 0, -1}}, {{1, 0} -> {1, 
      1, -1}}, {{1, 0} -> {1, 0, 1}}}, {{1, t + 1}, 
   Table[0, 2 t + 1]}, t, "StatesCountsList"]]

Each of those seem to develop exponentially, however with barely totally different bases, each close to 1.46.

Wanting on the collections of states generated additionally doesn’t give rapid perception into the habits:

TuringMachine

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; 
Labeled[RulePlot[TuringMachine[{0, 2, 2}], 
    [email protected][
      Last[With[{t = 7}, 
        MultiwayTuringMachine[#, {{1, t + 1, 0}, Table[0, 2 t + 1]}, 
         t]]]], ImageSize -> Automated, 400], 
   TuringMachinePlot[#, 1, 2, "RulePlot", 
    ImageSize -> {Automatic, 30}]] & /@ {{{{1, 1} -> {1, 0, -1}}, {{1,
       0} -> {1, 1, -1}}, {{1, 0} -> {1, 1, 1}}}, {{{1, 1} -> {1, 
      0, -1}}, {{1, 0} -> {1, 1, -1}}, {{1, 0} -> {1, 0, 1}}}, {{{1, 
      1} -> {1, 0, 1}}, {{1, 0} -> {1, 0, -1}}, {{1, 0} -> {1, 1, 
      1}}}}

So what occurs if we permit p > 3 instances within the rule? With p = 4 instances, there are 70 doable machines, none purely deterministic. Listed here are some examples of the extra sophisticated habits that’s seen:

CloudGet

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; 
ResourceFunction["ParallelMapMonitored"][
 Labeled[Show[TMAppliesGraphUntil[#, 200], 
    ImageSize -> ], 
   TuringMachinePlot[#, 2, 2, "RulePlot", 
    ImageSize -> {Automatic, 30}]] &, {{{{1, 1} -> {1, 0, -1}}, {{1, 
      1} -> {1, 1, 1}}, {{1, 0} -> {1, 0, -1}}, {{1, 0} -> {1, 1, 
      1}}}, {{{1, 1} -> {1, 0, -1}}, {{1, 1} -> {1, 0, 1}}, {{1, 
      0} -> {1, 1, -1}}, {{1, 0} -> {1, 0, 1}}}, {{{1, 1} -> {1, 0, 
      1}}, {{1, 0} -> {1, 1, -1}}, {{1, 0} -> {1, 0, -1}}, {{1, 
      0} -> {1, 0, 1}}}, {{{1, 1} -> {1, 0, 1}}, {{1, 0} -> {1, 
      0, -1}}, {{1, 0} -> {1, 1, 1}}, {{1, 0} -> {1, 0, 1}}}}]

We are able to go on and take a look at machines with bigger p. Listed here are examples with p = 5:

CloudGet

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; 
ResourceFunction["ParallelMapMonitored"][
 Labeled[Show[TMAppliesGraphUntil[#, 200], 
    ImageSize -> ], 
   TuringMachinePlot[#, 2, 2, "RulePlot", 
    ImageSize -> {Automatic, 30}]] &, {{{{1, 1} -> {1, 1, -1}}, {{1, 
      1} -> {1, 1, 1}}, {{1, 1} -> {1, 0, 1}}, {{1, 0} -> {1, 
      1, -1}}, {{1, 0} -> {1, 0, 1}}}, {{{1, 1} -> {1, 0, -1}}, {{1, 
      0} -> {1, 1, -1}}, {{1, 0} -> {1, 0, -1}}, {{1, 0} -> {1, 1, 
      1}}, {{1, 0} -> {1, 0, 1}}}, {{{1, 1} -> {1, 0, -1}}, {{1, 
      1} -> {1, 0, 1}}, {{1, 0} -> {1, 1, -1}}, {{1, 0} -> {1, 
      0, -1}}, {{1, 0} -> {1, 1, 1}}}, {{{1, 1} -> {1, 1, -1}}, {{1, 
      0} -> {1, 1, -1}}, {{1, 0} -> {1, 0, -1}}, {{1, 0} -> {1, 1, 
      1}}, {{1, 0} -> {1, 0, 1}}}}]

We are able to additionally ask what occurs if we permit s = 2 as an alternative of s = 1, with okay = 2. With p = 3 instances within the rule, probably the most sophisticated multiway graphs are simply:

TMAppliesGraphUntil

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; 
ResourceFunction["ParallelMapMonitored"][
 Labeled[Show[TMAppliesGraphUntil[#, 150], 
    ImageSize -> ], 
   TuringMachinePlot[#, 2, 2, "RulePlot", 
    ImageSize -> {Automatic, 30}]] &, {{{{2, 1} -> {1, 0, 1}}, {{1, 
      0} -> {1, 1, -1}}, {{1, 0} -> {2, 1, 1}}}, {{{2, 1} -> {2, 
      1, -1}}, {{1, 0} -> {1, 1, 1}}, {{1, 0} -> {2, 1, -1}}}, {{{2, 
      1} -> {2, 0, 1}}, {{1, 0} -> {1, 1, -1}}, {{1, 0} -> {2, 1, 
      1}}}}]

With p = 4 instances within the rule, the habits will be barely extra sophisticated, however doesn’t seem to transcend what we already noticed with a single head state s = 1:

CloudGet

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; 
ResourceFunction["ParallelMapMonitored"][
 Labeled[Show[TMAppliesGraphUntil[#, 100], 
    ImageSize -> ], 
   TuringMachinePlot[#, 2, 2, "RulePlot", 
    ImageSize -> {Automatic, 30}]] &, {{{{1, 1} -> {1, 0, -1}}, {{1, 
      0} -> {1, 0, -1}}, {{1, 0} -> {2, 0, 1}}, {{2, 0} -> {1, 1, 
      1}}}, {{{1, 1} -> {1, 0, -1}}, {{1, 0} -> {2, 0, -1}}, {{2, 
      0} -> {1, 0, -1}}, {{2, 0} -> {2, 1, 1}}}, {{{1, 1} -> {1, 
      0, -1}}, {{2, 1} -> {1, 1, -1}}, {{1, 0} -> {1, 1, -1}}, {{1, 
      0} -> {1, 0, 1}}}, {{{1, 1} -> {2, 0, -1}}, {{2, 1} -> {1, 0, 
      1}}, {{1, 0} -> {1, 1, -1}}, {{1, 0} -> {1, 1, 1}}}, {{{2, 
      1} -> {1, 0, -1}}, {{2, 1} -> {2, 0, 1}}, {{1, 0} -> {1, 
      1, -1}}, {{1, 0} -> {2, 0, 1}}}, {{{1, 1} -> {2, 0, 1}}, {{1, 
      0} -> {1, 0, -1}}, {{1, 0} -> {1, 1, 1}}, {{2, 0} -> {1, 
      0, -1}}}, {{{1, 1} -> {1, 0, 1}}, {{2, 1} -> {1, 1, -1}}, {{1, 
      0} -> {1, 0, -1}}, {{1, 0} -> {1, 1, 1}}}, {{{2, 1} -> {2, 
      0, -1}}, {{1, 0} -> {1, 1, 1}}, {{1, 0} -> {2, 1, -1}}, {{1, 
      0} -> {2, 0, -1}}}}]

What Is the Easiest Common Multiway Turing Machine?

We’d have assumed that to get sophisticated habits in a multiway Turing machine it could want sophisticated guidelines, and that as the principles obtained extra sophisticated the habits would one way or the other get correspondingly extra sophisticated. However that’s not what we noticed within the earlier part. As an alternative, even multiway Turing machines with quite simple guidelines have been already able to apparently complicated habits, and the habits didn’t appear to get basically extra sophisticated as the principles obtained extra sophisticated.

This may appear stunning. Nevertheless it’s truly very a lot the identical as we’ve seen all over the computational universe—and certainly it’s simply what my Principle of Computational Equivalence implies ought to occur. As a result of what the precept says is that as quickly as one goes past techniques with clearly easy habits, one will get to techniques which are equal within the sophistication of the computations they carry out. Or, in different phrases, that above a really low threshold, one sees techniques that every one obtain a maximal stage of computational sophistication that’s at all times the identical.

The Precept of Computational Equivalence talks about “typical computations” {that a} system does, and implies, for instance, that these computations will are usually computationally irreducible, within the sense that one can’t decide their outcomes besides by computations which are primarily simply so long as those the system itself is performing. However one other consequence of the Precept of Computational Equivalence is that as quickly because the habits of a system just isn’t clearly easy, it’s prone to be computation universal. Or, in different phrases, as soon as a system can exhibit sophisticated habits, it’s primarily at all times doable to discover a specific preliminary situation that can make it emulate every other system—at the very least as much as a translation given by some form of bounded computation.

And we’ve good proof that that is how things work in simple cellular automata, and in odd, deterministic Turing machines. With s = 2, okay = 2 such Turing machines always show simple, highly regular behavior, and no such machines are able to common computation. However with s = 2, okay = 3 there are a couple of machines that present extra complicated habits. And we know that these machines are indeed computation universal, establishing that amongst odd Turing machines the edge of universality is in a way as little as it could possibly be.

So what about multiway Turing machines? The place may the edge for universality for such machines be? Primarily based on our expertise with odd Turing machines (and lots of other forms of techniques) the ends in the earlier part may are inclined to recommend that s = 1, okay = 2, p = 3 would already be adequate. With odd Turing machines, universality is achieved when s = 2, okay = 3, corresponding to six instances within the rule. Right here universality appears doable even with simply 3 instances within the rule—and with s = 1, okay = 2.

Maybe probably the most stunning a part of that is the implication that universality is perhaps doable even with only a single head state s = 1. And this means that we don’t even have to have a Turing machine with any head states in any respect; we will simply use a mobile automaton, and really one with “radius 0” (i.e. with guidelines that aren’t immediately affected by any neighbors)—that we will indicate for example as:

TuringMachinePlot

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; TuringMachinePlot[
 [email protected]{{{1, 1} -> {1, 0, -1}}, {{1, 0} -> {1, 1, -1}}, {{1, 
      0} -> {1, 1, 1}}}, 1, 2, "RulePlot"]

Turing machines are sometimes seen as extensions of finite automata, through which a tape is added to offer probably infinite reminiscence. Atypical deterministic Turing machines are then extensions of deterministic finite automata (DFAs), and multiway Turing machines of nondeterministic finite automata (NDFAs). And finite automata with only a single state s = 1 are at all times trivial—whether or not they’re deterministic or nondeterministic. We additionally know that odd deterministic Turing machines with s = 1 are at all times trivial, no matter what number of tape colours okay they’ve; s = 2 is the minimum to achieve nontrivial behavior (and certainly we all know that s = 2, okay = 3 is sufficient to achieve in a sense maximally complex behavior).

However what we noticed above is that multiway Turing machines can present nontrivial habits even when s = 1. Fairly probably there’s a direct development that may present how an s = 1 multiway Turing machine can emulate an s > 1 one. However right here is a few instinct about why this is perhaps doable. In an odd Turing machine, the top strikes “in house” alongside the tape, and the top state carries state data with it. However in a multiway Turing machine, there may be in impact movement not solely in house, but in addition in branchial house. And although with out a number of head states the top could not be capable to carry data in odd house, the gathering of close by configurations in branchial house can probably carry data in branchial house. In different phrases, in branchial house one can probably consider there being a “cloud” of close by configurations that characterize some form of “tremendous head” that may in impact assume a number of doable head states.

Essential to this image is the truth that multiway techniques are set as much as merge an identical states. If it weren’t for this merging, the multiway graph for a multiway Turing machine would simply be a tree. However the merging “knits collectively” branchial house, and permits one to make sense of ideas like distance and movement in it.

In an odd Turing machine, one can consider the evolution as progressively remodeling the state of the system. In a multiway Turing machine it could be higher to think about the evolution as knitting collectively elementary items of the multiway graph—with the end result that it issues much less what the person states of the Turing machine are like, and extra how totally different states are associated in branchial house, or within the multiway system.

However what precisely can we imply by universality anyway? In an odd deterministic system the essential definition is {that a} common system—if given applicable preliminary circumstances—should be capable to emulate every other computational system (say any Turing machine). Inevitably, there shall be encoding and decoding required. Given a specification of the system one is attempting to emulate (say, the principles for a Turing machine), one will need to have a process for organising applicable preliminary circumstances—or, in impact, for “compiling” the principles to the suitable “code” for the common machine. Then when one runs the common machine, one will need to have a method of “decoding” its evolution to determine the steps within the evolution of the system one is emulating.

For the thought of universality to be significant, it’s essential in fact that the processes of encoding and decoding don’t do an excessive amount of computation. Specifically, the quantity of computation they should do should be bounded: so even when the “predominant computation” is computationally irreducible and must run progressively longer, these don’t. Or, put one other method, any function of the encoding and decoding must be decidable, whereas the principle computation can present computational irreducibility, and undecidability.

We now have talked right here about universality being a narrative of 1 machine emulating one other. And in the end that is what it’s about. However in conventional computation concept (which was developed earlier than precise digital computer systems have been commonplace) there are sometimes two further options of the setup. First, one usually thinks concerning the Turing machine as simply “computing a operate”, in order that when fed sure enter it offers sure output—and we don’t ask “what it’s doing inside”. And second, one thinks of the Turing machine as “halting” when it has produced its reply. However notably when one needs to get instinct about computational processes, it’s essential to have the ability to “see the method”. And in step with the operation of recent digital computer systems, one is less concerning with “halting”, and extra simply with realizing tips on how to decode the habits (say by on the lookout for “indicators” that point out that one thing must be “thought-about to be a end result”).

(Even past this, Turing machines are typically considered purely as “choice machines”: given a selected enter they finally give the end result “true” or “false”, moderately than producing totally different types of end result.)

In learning multiway Turing machines I feel one of the best ways to outline universality is the one that’s most immediately analogous to what I’ve used for odd Turing machines: the common machine should be capable to emulate the multiway graph for every other machine. In different phrases, given a common multiway Turing machine there should be a option to arrange the preliminary circumstances in order that the multiway graph it generates will be “decoded” to be the multiway graph for every other system (or, specifically, for every other multiway Turing machine).

It’s price realizing that the “preliminary circumstances” right here could not simply be a single Turing machine configuration; they are often an ensemble of configurations. In an odd deterministic Turing machine one offers preliminary circumstances that are “unfold out in house”, within the sense that they specify colours of cells at totally different positions on the tape. In a multiway Turing machine one also can give preliminary circumstances that are “unfold out in branchial house”, i.e. contain totally different configurations that can provoke totally different branches (which could merge) within the multiway system. In an odd Turing machine—in physics phrases—it’s as if one specifies one’s preliminary information on a “spacelike hypersurface”. In a multiway Turing machine, one additionally specifies one’s preliminary information on a “branchlike hypersurface”.

By the best way, for sure, a common deterministic Turing machine can at all times emulate a multiway Turing machine (which is why we will run multiway Turing machines on sensible computer systems). However at the very least in the obvious method it will probably probably require exponentially many steps of the odd Turing machine to observe all of the branches of the multiway graph for the multiway Turing machine.

However what’s the multiway analog of an odd Turing machine “computing a operate”? Essentially the most direct chance is {that a} multiway Turing machine defines a mapping from some set of configurations to another set. (There may be some subtlety to this, related to the foliation of the multiway graph—and specifying simply what set of configurations must be thought-about to be “the end result”.) However then we simply require that with applicable encoding and decoding a common multiway Turing machine ought to be capable to compute any operate that any multiway Turing machine can compute.

There may be one other chance, nonetheless, recommended by the time period “nondeterministic Turing machine”: require simply that there exists some department of the multiway system that has the output one needs. For instance, if one is attempting to find out the reply to a call downside, simply see if there may be any “sure” department, and, if that’s the case, conclude that the reply is sure.

As a easy analog, contemplate the string substitution with transformations →“”,”()”“|”” class=”synonym”>”. One can compute whether or not a given sequence of parentheses is balanced by seeing whether or not its evolution will finally generate an empty string (“”) state—however even when this state is generated, all kinds of “irrelevant” states may even be generated:

ResourceFunction["MultiwaySystem"]

&#10005

With[g = 
   ResourceFunction["MultiwaySystem"][", 
    "((()(())))", 5, "StatesGraph"], 
 HighlightGraph[g, 
  Style[Subgraph[g, FindShortestPath[g, "((()(())))", ""]], Crimson]]]

There may be presumably at all times a option to translate the idea of universality from our “emulate the entire multiway evolution” to the “see if there’s any path that results in some particular configuration”. However for the needs of instinct and empirical investigation, it appears a lot better to take a look at the entire evolution, which may for instance be visualized as a graph.

So what’s the easiest common multiway Turing machine? I’m not sure, however I feel it fairly probably that it has s = 1, okay = 2, p = 3. Two candidates are:

TuringMachinePlot

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; 
TuringMachinePlot[#, 2, 2, "RulePlot", 
    ImageSize -> {Automatic, 
      50}] & /@ {{{{1, 1} -> {1, 0, -1}}, {{1, 0} -> {1, 1, -1}}, {{1,
        0} -> {1, 1, 1}}}, {{{1, 1} -> {1, 0, -1}}, {{1, 0} -> {1, 
       1, -1}}, {{1, 0} -> {1, 0, 1}}}} // Column

To show universality one must present that there exists a process for organising preliminary circumstances that can make a selected rule right here yield a multiway graph that corresponds (after decoding) to the multiway graph for every other specified system, say every other multiway Turing machine. To get some sense of how this is perhaps doable, listed below are the considerably numerous multispace graphs generated by the primary rule above, ranging from a single preliminary configuration whose tape comprises the digits of successive binary numbers:

TMAppliesMultispaceIndicatorUntilInit

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; Grid[
 Partition[
  ResourceFunction["ParallelMapMonitored"][
   Show[TimeConstrained[
      TMAppliesMultispaceIndicatorUntilInit[{{{1, 1} -> {1, 
           0, -1}}, {{1, 0} -> {1, 1, -1}}, {{1, 0} -> {1, 1, 
           1}}}, {{1, 4, 0}, CenterArray[IntegerDigits[#, 2], 7]}, 
       50, {1, 1, 6}, PlotTheme -> "LargeGraph"], 3], 
     ImageSize -> 80, Boxed -> True, Lighting -> "Impartial", 
     ViewProjection -> "Orthographic"] &, Vary[0, 20]], 7], 
 Spacings -> 1]

The Halting Downside and Busy Beavers

If a system is computation common, it’s inevitable that there shall be computational irreducibility related to figuring out its habits, and that to reply questions on what it should do after an arbitrarily very long time could require unbounded quantities of computation, and should subsequently generally be thought-about formally undecidable. A traditional instance is the halting problem—of asking whether or not a Turing machine ranging from a selected preliminary situation will ever attain a selected “halt” state.

Most frequently, this query is formulated for odd deterministic Turing machines, and one asks whether or not these machines can attain a particular “halting” head state. However within the context of multiway Turing machines, a extra pure model of this query is simply to ask, as we’ve achieved above, whether or not the multiway system will attain a configuration the place none of its doable guidelines apply.

And within the easiest case, we will contemplate “deterministic however incomplete guidelines”, in which there’s by no means multiple doable successor for a given state, however there could also be no successor in any respect. An instance is the rule

TuringMachinePlot

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; TuringMachinePlot[{{1, 
    1} -> {2, 1, 1}, {1, 0} -> {2, 1, -1}, {2, 0} -> {1, 1, 
    1}}, 2, 2, "RulePlot"]

which comprises no case for . Beginning this rule from a clean tape it will probably evolve for five steps, however then reaches a state the place none of its guidelines apply:

RulePlot

&#10005

RulePlot[TuringMachine[{{1, 1} -> {2, 1, 1}, {1, 0} -> {2, 1, -1}, {2,
      1} -> {2, 1, 0}, {2, 0} -> {1, 1, 1}}], {{1, 4}, 
  Desk[0, 7]}, 6, Mesh -> True, Body -> None, ImageSize -> 100]

As we noticed above, for s = 2, okay = 2 guidelines, 6 steps is the longest any ordinary Turing machine rule will “survive” ranging from a clean tape. For s = 3, okay = 2 it’s 21 steps, for s = 2, okay = 3 it’s 38 and for s = 4, okay = 2 it’s 107:

TuringMachine

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; GraphicsRow[{RulePlot[
   TuringMachine[{{1, 1} -> {1, 1, 0}, {1, 0} -> {2, 1, 1}, {2, 
       1} -> {3, 0, 1}, {2, 0} -> {2, 1, -1}, {3, 1} -> {1, 
       1, -1}, {3, 0} -> {3, 1, -1}}], {{1}, {{}, 0}}, 21, 
   Mesh -> True, Body -> False], 
  RulePlot[TuringMachine[{{1, 0} -> {2, 1, 1}, {2, 0} -> {1, 
       2, -1}, {1, 1} -> {2, 2, -1}, {2, 1} -> {2, 2, 1}, {1, 
       2} -> {1, 2, 0}, {2, 2} -> {2, 1, -1}}], {{1}, {{}, 0}}, 38, 
   Mesh -> True, Body -> False], 
  RulePlot[TuringMachine[{{1, 1} -> {2, 1, -1}, {1, 0} -> {2, 1, 
       1}, {2, 1} -> {3, 0, -1}, {2, 0} -> {1, 1, -1}, {3, 1} -> {4, 
       1, -1}, {3, 0} -> {3, 0, 0}, {4, 1} -> {1, 0, 1}, {4, 0} -> {4,
        1, 1}}], {{1}, {{}, 0}}, 107], 
  GraphicsColumn[{TuringMachinePlot[{{1, 0} -> {2, 1, 1}, {2, 
        1} -> {3, 0, 1}, {2, 0} -> {2, 1, -1}, {3, 1} -> {1, 
        1, -1}, {3, 0} -> {3, 1, -1}}, 3, 2, "RulePlot", 
     ImageSize -> {Automatic, 70}], 
    TuringMachinePlot[{{1, 0} -> {2, 1, 1}, {2, 0} -> {1, 2, -1}, {1, 
        1} -> {2, 2, -1}, {2, 1} -> {2, 2, 1}, {2, 2} -> {2, 1, -1}}, 
     2, 3, "RulePlot", ImageSize -> {Automatic, 70}], 
    TuringMachinePlot[{{1, 1} -> {2, 1, -1}, {1, 0} -> {2, 1, 1}, {2, 
        1} -> {3, 0, -1}, {2, 0} -> {1, 1, -1}, {3, 1} -> {4, 
        1, -1}, {4, 1} -> {1, 0, 1}, {4, 0} -> {4, 1, 1}}, 4, 2, 
     "RulePlot", ImageSize -> {Automatic, 70}]}]}]

For bigger s and okay the survival occasions for the best-known “busy beaver” machines quickly develop into very lengthy; for s = 3, okay = 3 it’s identified to be at the very least 1017.

So what about multiway Turing machines generally—the place we permit multiple successor for a given state (resulting in branching within the multiway graph)? For s = 1 or okay = 1 the outcomes are at all times trivial. However for s = 2, okay = 2 issues begin to be extra fascinating.

With solely p = 2 doable instances within the rule, the longest halting time is achieved by the deterministic rule

TuringMachinePlot

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; TuringMachinePlot[
 Flatten[{{{1, 0} -> {2, 0, -1}}, {{2, 0} -> {1, 1, 
      1}}}], 2, 2, "RulePlot"]

which halts in 4 steps

RulePlot

&#10005

RulePlot[TuringMachine[{{1, 0} -> {2, 0, -1}, {2, 0} -> {1, 1, 1}, {1,
      1} -> {1, 1, 0}, {2, 1} -> {2, 1, 0}}], {{1, 4}, 
  Desk[0, 6]}, 4, Mesh -> True, Body -> False]

as represented by the (single-path) multiway graph:

TMAppliesStatesGraph

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; Graph[
 TMAppliesStatesGraph[{{{1, 0} -> {2, 0, -1}}, {{2, 0} -> {1, 1, 1}}},
   2, 2, 4], GraphLayout -> "LayeredDigraphEmbedding", 
 VertexSize -> .2 {9, 1}]

The p = 3 case consists of commonplace deterministic s = 2, okay = 2 Turing machines with a single halt state, and the longest halting time is achieved by the deterministic machine we noticed above:

TMAppliesStatesGraph

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; GraphicsRow[
 [email protected]{Graph[
    TMAppliesStatesGraph[{{{1, 1} -> {2, 1, -1}}, {{1, 0} -> {2, 1, 
         1}}, {{2, 0} -> {1, 1, -1}}}, 2, 2, 5], 
    GraphLayout -> "LayeredDigraphEmbedding", 
    VertexSize -> .2 {9, 1}], 
   TuringMachinePlot[
    Flatten[{{{1, 1} -> {2, 1, -1}}, {{1, 0} -> {2, 1, 1}}, {{2, 
         0} -> {1, 1, -1}}}], 2, 2, "RulePlot"]}, Spacings -> 100]

But when we take a look at barely shorter halting occasions, we begin seeing branching within the multiway graph:

TuringMachinePlot

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; \
GraphicsRow[{TuringMachinePlot[
   Flatten[{{{1, 0} -> {2, 1, -1}}, {{1, 0} -> {2, 0, -1}}, {{2, 
        0} -> {1, 1, 1}}}], 2, 2, "RulePlot", 
   ImageSize -> ], 
  Graph[TMAppliesStatesGraph[{{{1, 0} -> {2, 1, -1}}, {{1, 0} -> {2, 
        0, -1}}, {{2, 0} -> {1, 1, 1}}}, 2, 2, 4], 
   VertexSize -> .06 {9, 1}, AspectRatio -> .7, 
   GraphLayout -> "LayeredDigraphEmbedding"]}]

After we assume by way of multiway graphs, it’s not so pure to differentiate “no-rule-applies” halting from different conditions that result in finite multiway graphs. An instance is

TuringMachinePlot

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; \
GraphicsRow[{TuringMachinePlot[
   Flatten[{{{2, 1} -> {1, 1, -1}}, {{1, 0} -> {2, 0, 1}}, {{2, 
        0} -> {1, 1, -1}}}], 2, 2, "RulePlot", 
   ImageSize -> ], 
  Graph[TMAppliesStatesGraph[{{{2, 1} -> {1, 1, -1}}, {{1, 0} -> {2, 
        0, 1}}, {{2, 0} -> {1, 1, -1}}}, 2, 2, 4], 
   VertexSize -> .06 {9, 1}, AspectRatio -> .7, 
   GraphLayout -> "LayeredDigraphEmbedding"]}]

which is a deterministic machine that after 4 steps results in a loop:

TuringMachine

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; RulePlot[
 TuringMachine[
  Flatten[{{{2, 1} -> {1, 1, -1}}, {{1, 0} -> {2, 0, 1}}, {{2, 
       0} -> {1, 1, -1}}, {{1, 1} -> {1, 1, 0}}}]], {{1, 4}, 
  Desk[0, 8]}, 7, Mesh -> True, Body -> None]

With p = 4 whole instances within the rule we will have a “full deterministic s = 2, okay = 2 Turing machine”, with no doable instances omitted. The longest “halting time” (of 8 steps) is achieved by a machine which enters a loop:

TMAppliesStatesGraphInit

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; Row[{Column[{Show[
     Graph[TMAppliesStatesGraphInit[{{{1, 1} -> {2, 1, -1}}, {{2, 
           1} -> {1, 1, 1}}, {{1, 0} -> {2, 1, 1}}, {{2, 0} -> {1, 
           1, -1}}}, {{1, 6, 0}, Table[0, 11]}, 2, 2, 8], 
      VertexSize -> .04 {8, 0.7}, AspectRatio -> .7, 
      GraphLayout -> "LayeredDigraphEmbedding"], 
     ImageSize -> Automated, 185], 
    RulePlot[
     TuringMachine[
      [email protected]{{{1, 1} -> {2, 1, -1}}, {{2, 1} -> {1, 1, 1}}, {{1, 
           0} -> {2, 1, 1}}, {{2, 0} -> {1, 1, -1}}}], 
     ImageSize -> ]}, Middle], 
  RulePlot[TuringMachine[
    [email protected]{{{1, 1} -> {2, 1, -1}}, {{2, 1} -> {1, 1, 1}}, {{1, 
         0} -> {2, 1, 1}}, {{2, 0} -> {1, 1, -1}}}], {{1, 4}, 
    Desk[0, 6]}, 11, Mesh -> True, Body -> None, 
   ImageSize -> ]}]

But when we contemplate shorter maximal halting occasions, then we get each “real halting” and branching within the multiway system:

TMAppliesStatesGraphInit

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; Grid[
 Partition[
  Labeled[Framed[
      Graph[TMAppliesStatesGraphInit[#, {{1, 4, 0}, Table[0, 8]}, 2, 
        2, 6], VertexSize -> 0.25 {0.85, 0.18}, AspectRatio -> .7, 
       ImageSize -> {UpTo[300], UpTo[300]}, 
       GraphLayout -> {"LayeredDigraphEmbedding", 
         "RootVertex" -> ToString[{{1, 4, 0}, Table[0, 8]}]}], 
      FrameStyle -> LightGray], 
     TuringMachinePlot[Flatten[#], 2, 2, "RulePlot", 
      ImageSize -> ]] & /@ {{{{1, 1} -> {1, 
        1, -1}}, {{1, 1} -> {2, 1, -1}}, {{1, 0} -> {2, 1, 1}}, {{2, 
        0} -> {1, 1, -1}}}, {{{1, 1} -> {2, 1, -1}}, {{1, 0} -> {2, 1,
         1}}, {{1, 0} -> {2, 0, 1}}, {{2, 0} -> {1, 1, -1}}}, {{{1, 
        1} -> {2, 0, -1}}, {{1, 0} -> {2, 1, -1}}, {{2, 0} -> {1, 1, 
        1}}, {{2, 0} -> {1, 0, 1}}}, {{{2, 1} -> {1, 1, 1}}, {{2, 
        1} -> {2, 1, -1}}, {{1, 0} -> {2, 1, -1}}, {{2, 0} -> {2, 0, 
        1}}}}, 2]]

Notice that in contrast to within the deterministic case the place there’s a single, particular halting time from a given preliminary state, a multiway Turing machine can have totally different halting occasions on totally different branches in its multiway evolution. So which means that there are a number of methods to outline the multiway analog of the busy beaver downside for deterministic Turing machines.

One method maybe the closest to the spirit of the deterministic case is to ask for machines that maximize the maximal finite halting time obtained by following any department. However one also can ask for machines which maximize the minimal halting time. Or one can ask for machines that give multiway graphs that contain as many states as doable whereas nonetheless being finite (as a result of all their branches both halt or cycle). (One more criterion could possibly be to ask for the utmost finite variety of distinct halting states.)

For the p = 2 case, the maximum-halting-time and maximum-states standards transform happy by the identical deterministic machine proven above (with 4 whole states). For p = 3, although, the maximum-halting-time criterion is happy by the primary machine we confirmed, which evolves by 6 states, whereas the maximum-states-criterion is as an alternative happy by the second machine, which has 7 states in its multiway graph.

For the okay = 2, s = 2, p = 4 case above the maximum-halting-time machine is once more deterministic (and goes by 7 states), however maximum-states machines have 11 states:

TMAppliesStatesGraphInit

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; 
Labeled[Framed[
    Graph[TMAppliesStatesGraphInit[
      List /@ Flatten[#], {{1, 4, 0}, Desk[0, 8]}, 2, 2, 6], 
     VertexSize -> 0.25 {0.85, 0.18}, AspectRatio -> .7, 
     ImageSize -> {UpTo[300], UpTo[300]}, 
     GraphLayout -> "LayeredDigraphEmbedding"], 
    FrameStyle -> LightGray], 
   TuringMachinePlot[Flatten[#], 2, 2, "RulePlot", 
    ImageSize -> ]] & /@ 
 [email protected]{{{1, 1} -> {2, 1, -1}, {1, 0} -> {2, 1, 1}, {1, 0} -> {2, 0,
       1}, {2, 0} -> {1, 1, -1}}, {{2, 1} -> {2, 1, -1}, {1, 0} -> {2,
       1, -1}, {1, 0} -> {2, 0, -1}, {2, 0} -> {1, 1, 1}}}

Even for odd deterministic Turing machines, discovering busy beavers includes direct confrontation with the halting downside, and computational irreducibility. Let’s say a machine has been working for some time. If it halts, nicely, then one is aware of it halts. However what if it doesn’t halt? If its habits is sufficiently easy, then one might be able to acknowledge—or one way or the other show—that it will probably by no means halt. But when the habits is extra complicated one could merely not be capable to inform what’s going to occur. And the issue is even worse for a multiway Turing machine. As a result of now it’s not only a query of evolving one configuration; as an alternative there could also be a complete, probably rising, multiway graph of configurations one has to contemplate.

Normally when the multiway graph will get large, it has a easy sufficient construction that one can readily decide that it’ll by no means “terminate”, and simply develop ceaselessly. However when the multiway graph will get complicated it may be extraordinarily tough to make certain what’s going to finally occur. Nonetheless, at the very least usually, one will be pretty sure of the outcomes.

With p = 5, the rule whose habits permits the longest halting (or, on this case, biking) time (8 steps) is:

TMAppliesStatesGraphInit

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; Labeled[
 Show[TMAppliesStatesGraphInit[{{{1, 1} -> {2, 0, -1}}, {{2, 1} -> {1,
        1, 1}}, {{2, 1} -> {1, 0, 1}}, {{1, 0} -> {2, 1, -1}}, {{2, 
       0} -> {1, 1, 1}}}, {{1, 3, 0}, Table[0, 7]}, 2, 2, 10, 
   VertexSize -> .17 {1.25, .25}], ImageSize -> 600, Automated], 
 TuringMachinePlot[
  Flatten[{{{1, 1} -> {2, 0, -1}}, {{2, 1} -> {1, 1, 1}}, {{2, 
       1} -> {1, 0, 1}}, {{1, 0} -> {2, 1, -1}}, {{2, 0} -> {1, 1, 
       1}}}], 2, 2, "RulePlot", ImageSize -> ], High, 
 Spacings -> ]

With p = 5, many different sorts of “finite habits” also can happen, reminiscent of:

TMAppliesGraph

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; 
Framed[Graph[TMAppliesGraph[List /@ Flatten[#], 8], 
    ImageSize -> Automated, 90], 
   FrameStyle -> 
    LightGray] & /@ {{{{2, 1} -> {1, 1, -1}}, {{2, 1} -> {2, 1, 
      1}}, {{1, 0} -> {2, 1, 1}}, {{2, 0} -> {1, 1, -1}}, {{2, 
      0} -> {2, 
      0, -1}}}, {{{{1, 1} -> {1, 1, -1}}, {{1, 1} -> {2, 1, -1}}, {{1,
        1} -> {2, 0, -1}}, {{1, 0} -> {2, 1, 1}}, {{2, 0} -> {1, 
       1, -1}}}}, {{{{1, 1} -> {1, 1, -1}}, {{1, 1} -> {2, 
       1, -1}}, {{1, 0} -> {2, 1, 1}}, {{1, 0} -> {2, 0, 1}}, {{2, 
       0} -> {1, 1, -1}}}}, {{{{1, 1} -> {2, 1, -1}}, {{1, 1} -> {2, 
       1, 1}}, {{1, 0} -> {2, 1, 1}}, {{1, 0} -> {2, 0, 1}}, {{2, 
       0} -> {1, 1, -1}}}}, {{{{1, 1} -> {2, 0, -1}}, {{2, 1} -> {1, 
       1, 1}}, {{2, 1} -> {2, 1, -1}}, {{1, 0} -> {2, 1, -1}}, {{2, 
       0} -> {2, 0, 1}}}}, {{{{1, 1} -> {2, 0, -1}}, {{2, 1} -> {1, 1,
        1}}, {{1, 0} -> {2, 1, -1}}, {{2, 0} -> {1, 1, 1}}, {{2, 
       0} -> {1, 0, 1}}}}, {{{{1, 1} -> {2, 0, -1}}, {{2, 1} -> {1, 0,
        1}}, {{1, 0} -> {2, 1, -1}}, {{2, 0} -> {1, 1, 1}}, {{2, 
       0} -> {1, 0, 1}}}}, {{{{2, 1} -> {1, 0, 1}}, {{2, 1} -> {2, 
       1, -1}}, {{1, 0} -> {2, 1, -1}}, {{1, 0} -> {2, 0, -1}}, {{2, 
       0} -> {1, 1, 1}}}}}

With p = 6 there may be principally simply extra of the identical—with no extension within the most halting time, although with bigger whole numbers of states:

TMAppliesGraph

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; 
Framed[Graph[TMAppliesGraph[List /@ Flatten[#], 8], 
    ImageSize -> ], FrameStyle -> LightGray] & /@ 
 Be a part of[{{{{1, 1} -> {2, 1, 1}}, {{2, 1} -> {1, 1, -1}}, {{2, 1} -> {2, 
       1, 1}}, {{1, 0} -> {2, 1, 1}}, {{2, 0} -> {1, 0, -1}}, {{2, 
       0} -> {2, 0, -1}}}, {{{2, 1} -> {1, 1, -1}}, {{2, 1} -> {2, 1, 
       1}}, {{1, 0} -> {2, 1, 1}}, {{2, 0} -> {1, 1, -1}}, {{2, 
       0} -> {1, 0, -1}}, {{2, 0} -> {2, 0, -1}}}}, {{{{1, 1} -> {1, 
       1, -1}}, {{1, 1} -> {2, 1, -1}}, {{1, 1} -> {2, 0, -1}}, {{1, 
       0} -> {2, 1, 1}}, {{1, 0} -> {2, 0, 1}}, {{2, 0} -> {1, 
       1, -1}}}, {{{1, 1} -> {1, 1, 1}}, {{1, 1} -> {2, 1, -1}}, {{1, 
       1} -> {2, 0, 1}}, {{1, 0} -> {2, 1, -1}}, {{1, 0} -> {2, 
       0, -1}}, {{2, 0} -> {1, 1, 1}}}, {{{1, 1} -> {1, 1, 1}}, {{1, 
       1} -> {2, 1, -1}}, {{1, 1} -> {2, 1, 1}}, {{1, 1} -> {2, 0, 
       1}}, {{1, 0} -> {2, 1, -1}}, {{2, 0} -> {1, 1, 1}}}, {{{1, 
       1} -> {2, 0, -1}}, {{1, 1} -> {2, 1, 1}}, {{1, 1} -> {2, 0, 
       1}}, {{1, 0} -> {2, 1, 1}}, {{1, 0} -> {2, 0, 1}}, {{2, 
       0} -> {1, 1, -1}}}, {{{2, 1} -> {1, 1, 1}}, {{2, 1} -> {1, 0, 
       1}}, {{2, 1} -> {2, 1, -1}}, {{1, 0} -> {2, 1, -1}}, {{1, 
       0} -> {2, 0, -1}}, {{2, 0} -> {1, 1, 1}}}, {{{2, 1} -> {1, 1, 
       1}}, {{1, 0} -> {2, 1, -1}}, {{2, 0} -> {1, 1, 1}}, {{2, 
       0} -> {1, 0, 1}}, {{2, 0} -> {2, 1, 1}}, {{2, 0} -> {2, 0, 
       1}}}, {{{2, 1} -> {1, 1, 1}}, {{2, 1} -> {1, 0, 1}}, {{2, 
       1} -> {2, 1, -1}}, {{1, 0} -> {2, 0, -1}}, {{2, 0} -> {1, 1, 
       1}}, {{2, 0} -> {1, 0, 1}}}, {{{2, 1} -> {1, 0, 1}}, {{2, 
       1} -> {2, 1, -1}}, {{1, 0} -> {2, 1, -1}}, {{1, 0} -> {2, 
       0, -1}}, {{2, 0} -> {1, 1, 1}}, {{2, 0} -> {1, 0, 1}}}, {{{1, 
       1} -> {2, 0, -1}}, {{2, 1} -> {1, 1, 1}}, {{2, 1} -> {1, 0, 
       1}}, {{1, 0} -> {2, 1, -1}}, {{2, 0} -> {1, 1, 1}}, {{2, 
       0} -> {1, 0, 1}}}, {{{1, 1} -> {2, 1, -1}}, {{1, 1} -> {2, 
       0, -1}}, {{2, 1} -> {1, 1, 1}}, {{2, 1} -> {1, 0, 1}}, {{1, 
       0} -> {2, 1, -1}}, {{2, 0} -> {1, 1, 1}}}}]

The utmost halting occasions and finite numbers of states reached by s = 2, okay = 2 machines with p instances is as follows

Table

&#10005

Textual content[Grid[
  Prepend[Table[{t, {2, 4, 6, 7, 8, 7, 6}[[
      t]], {2, 4, 7, 11, 15, 18, 18}[[t]]}, {t, 7}], 
   Fashion[#, Italic] & /@ {"p", "steps", "states"}], Body -> All, 
  FrameStyle -> GrayLevel[.7], 
  Background -> {{GrayLevel[0.9]}, {GrayLevel[0.9]}}]]

and the distributions of halting occasions and finite numbers of steps (for p for up 7) are:

BarChart

&#10005

Cell[CellGroupData[{Cell[BoxData[
 RowBox[{
  RowBox[{
  "CloudGet", "[", 
   "\"\<https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl\>\"", "]"}], ";"}]], "Enter"],

Cell[BoxData[
 RowBox[{
  RowBox[{"belems", "[", 
   RowBox[{"assoc_", ",", "min_", ",", "max_"}], "]"}], ":=", 
  RowBox[{
   RowBox[{"Append", "[", 
    RowBox[{
     RowBox[{"Table", "[", 
      RowBox[{
       RowBox[{"Lookup", "[", 
        RowBox[{"assoc", ",", "i", ",", "0"}], "]"}], ",", 
       RowBox[{"{", 
        RowBox[{"i", ",", "min", ",", "max"}], "}"}]}], "]"}], ",", 
     RowBox[{
      RowBox[{"assoc", "[", "None", "]"}], "+", 
      RowBox[{"Lookup", "[", 
       RowBox[{"assoc", ",", "\"\<NotFound\>\"", ",", "0"}], 
       "]"}]}]}], "]"}], "https://writings.stephenwolfram.com/", 
   RowBox[{"Total", "[", "assoc", "]"}]}]}]], "Enter"],

Cell[BoxData[
 RowBox[{"GraphicsRow", "[", 
  RowBox[{"{", 
   RowBox[{
    RowBox[{"BarChart", "[", 
     RowBox[{
      RowBox[{"Transpose", "[", 
       RowBox[{
        RowBox[{
         RowBox[{"belems", "[", 
          RowBox[{"#", ",", "2", ",", "9"}], "]"}], "&"}], "/@", 
        RowBox[{"{", 
         RowBox[{
          RowBox[{"\[LeftAssociation]", 
           RowBox[{
            RowBox[{"None", "\[Rule]", "28"}], ",", 
            RowBox[{"2", "\[Rule]", "4"}]}], "\[RightAssociation]"}], 
          ",", 
          RowBox[{"\[LeftAssociation]", 
           RowBox[{
            RowBox[{"None", "\[Rule]", "412"}], ",", 
            RowBox[{"2", "\[Rule]", "72"}], ",", 
            RowBox[{"\"\<NotFound\>\"", "\[Rule]", "2"}], ",", 
            RowBox[{"3", "\[Rule]", "8"}], ",", 
            RowBox[{"4", "\[Rule]", "2"}]}], "\[RightAssociation]"}], 
          ",", 
          RowBox[{"\[LeftAssociation]", 
           RowBox[{
            RowBox[{"None", "\[Rule]", "4152"}], ",", 
            RowBox[{"2", "\[Rule]", "612"}], ",", 
            RowBox[{"\"\<NotFound\>\"", "\[Rule]", "66"}], ",", 
            RowBox[{"3", "\[Rule]", "82"}], ",", 
            RowBox[{"4", "\[Rule]", "34"}], ",", 
            RowBox[{"5", "\[Rule]", "4"}], ",", 
            RowBox[{"6", "\[Rule]", "10"}]}], "\[RightAssociation]"}],
           ",", 
          RowBox[{"\[LeftAssociation]", 
           RowBox[{
            RowBox[{"None", "\[Rule]", "29524"}], ",", 
            RowBox[{"2", "\[Rule]", "3265"}], ",", 
            RowBox[{"\"\<NotFound\>\"", "\[Rule]", "2599"}], ",", 
            RowBox[{"3", "\[Rule]", "324"}], ",", 
            RowBox[{"4", "\[Rule]", "166"}], ",", 
            RowBox[{"6", "\[Rule]", "54"}], ",", 
            RowBox[{"5", "\[Rule]", "26"}], ",", 
            RowBox[{"7", "\[Rule]", "2"}]}], "\[RightAssociation]"}], 
          ",", 
          RowBox[{"\[LeftAssociation]", 
           RowBox[{
            RowBox[{"None", "\[Rule]", "152530"}], ",", 
            RowBox[{"2", "\[Rule]", "12256"}], ",", 
            RowBox[{"\"\<NotFound\>\"", "\[Rule]", "35232"}], ",", 
            RowBox[{"3", "\[Rule]", "770"}], ",", 
            RowBox[{"4", "\[Rule]", "440"}], ",", 
            RowBox[{"6", "\[Rule]", "92"}], ",", 
            RowBox[{"5", "\[Rule]", "48"}], ",", 
            RowBox[{"7", "\[Rule]", "6"}], ",", 
            RowBox[{"8", "\[Rule]", "2"}]}], "\[RightAssociation]"}], 
          ",", 
          RowBox[{"\[LeftAssociation]", 
           RowBox[{
            RowBox[{"None", "\[Rule]", "566633"}], ",", 
            RowBox[{"2", "\[Rule]", "34392"}], ",", 
            RowBox[{"\"\<NotFound\>\"", "\[Rule]", "302961"}], ",", 
            RowBox[{"3", "\[Rule]", "1248"}], ",", 
            RowBox[{"4", "\[Rule]", "850"}], ",", 
            RowBox[{"6", "\[Rule]", "68"}], ",", 
            RowBox[{"5", "\[Rule]", "36"}], ",", 
            RowBox[{"7", "\[Rule]", "4"}]}], "\[RightAssociation]"}], 
          ",", 
          RowBox[{"\[LeftAssociation]", 
           RowBox[{
            RowBox[{"None", "\[Rule]", "1610690"}], ",", 
            RowBox[{"2", "\[Rule]", "74816"}], ",", 
            RowBox[{"\"\<NotFound\>\"", "\[Rule]", "1677708"}], ",", 
            RowBox[{"3", "\[Rule]", "1428"}], ",", 
            RowBox[{"4", "\[Rule]", "1184"}], ",", 
            RowBox[{"6", "\[Rule]", "20"}], ",", 
            RowBox[{"5", "\[Rule]", "10"}]}], 
           "\[RightAssociation]"}]}], "}"}]}], "]"}], ",", 
      RowBox[{"ScalingFunctions", "\[Rule]", "\"\<Log\>\""}], ",", 
      RowBox[{"Frame", "\[Rule]", "True"}], ",", 
      RowBox[{"ChartLabels", "\[Rule]", 
       RowBox[{"{", 
        RowBox[{
         RowBox[{"Placed", "[", 
          RowBox[{
           RowBox[{"Join", "[", 
            RowBox[{
             RowBox[{
              RowBox[{"Range", "[", "7", "]"}], "+", "1"}], ",", 
             RowBox[{"{", 
              RowBox[{"\"\<\>\"", ",", "Infinity"}], "}"}]}], "]"}], 
           ",", "Under"}], "]"}], ",", "None"}], "}"}]}]}], "]"}], 
    ",", 
    RowBox[{"BarChart", "[", 
     RowBox[{
      RowBox[{"Transpose", "[", 
       RowBox[{
        RowBox[{
         RowBox[{"belems", "[", 
          RowBox[{"#", ",", "1", ",", "19"}], "]"}], "&"}], "/@", 
        RowBox[{"{", 
         RowBox[{
          RowBox[{"\[LeftAssociation]", 
           RowBox[{
            RowBox[{"1", "\[Rule]", "24"}], ",", 
            RowBox[{"None", "\[Rule]", "4"}], ",", 
            RowBox[{"2", "\[Rule]", "4"}]}], "\[RightAssociation]"}], 
          ",", 
          RowBox[{"\[LeftAssociation]", 
           RowBox[{
            RowBox[{"1", "\[Rule]", "276"}], ",", 
            RowBox[{"None", "\[Rule]", "136"}], ",", 
            RowBox[{"2", "\[Rule]", "66"}], ",", 
            RowBox[{"TooBig", "\[Rule]", "2"}], ",", 
            RowBox[{"3", "\[Rule]", "14"}], ",", 
            RowBox[{"4", "\[Rule]", "2"}]}], "\[RightAssociation]"}], 
          ",", 
          RowBox[{"\[LeftAssociation]", 
           RowBox[{
            RowBox[{"1", "\[Rule]", "2024"}], ",", 
            RowBox[{"None", "\[Rule]", "2128"}], ",", 
            RowBox[{"2", "\[Rule]", "512"}], ",", 
            RowBox[{"TooBig", "\[Rule]", "66"}], ",", 
            RowBox[{"3", "\[Rule]", "164"}], ",", 
            RowBox[{"4", "\[Rule]", "50"}], ",", 
            RowBox[{"5", "\[Rule]", "4"}], ",", 
            RowBox[{"6", "\[Rule]", "10"}], ",", 
            RowBox[{"7", "\[Rule]", "2"}]}], "\[RightAssociation]"}], 
          ",", 
          RowBox[{"\[LeftAssociation]", 
           RowBox[{
            RowBox[{"1", "\[Rule]", "10626"}], ",", 
            RowBox[{"None", "\[Rule]", "20418"}], ",", 
            RowBox[{"2", "\[Rule]", "2480"}], ",", 
            RowBox[{"TooBig", "\[Rule]", "1079"}], ",", 
            RowBox[{"3", "\[Rule]", "976"}], ",", 
            RowBox[{"4", "\[Rule]", "260"}], ",", 
            RowBox[{"8", "\[Rule]", "16"}], ",", 
            RowBox[{"6", "\[Rule]", "28"}], ",", 
            RowBox[{"5", "\[Rule]", "35"}], ",", 
            RowBox[{"10", "\[Rule]", "4"}], ",", 
            RowBox[{"7", "\[Rule]", "30"}], ",", 
            RowBox[{"9", "\[Rule]", "2"}], ",", 
            RowBox[{"11", "\[Rule]", "6"}]}], "\[RightAssociation]"}],
           ",", 
          RowBox[{"\[LeftAssociation]", 
           RowBox[{
            RowBox[{"1", "\[Rule]", "42504"}], ",", 
            RowBox[{"None", "\[Rule]", "133494"}], ",", 
            RowBox[{"2", "\[Rule]", "8400"}], ",", 
            RowBox[{"TooBig", "\[Rule]", "11764"}], ",", 
            RowBox[{"3", "\[Rule]", "3920"}], ",", 
            RowBox[{"4", "\[Rule]", "1086"}], ",", 
            RowBox[{"11", "\[Rule]", "16"}], ",", 
            RowBox[{"9", "\[Rule]", "26"}], ",", 
            RowBox[{"14", "\[Rule]", "8"}], ",", 
            RowBox[{"7", "\[Rule]", "36"}], ",", 
            RowBox[{"6", "\[Rule]", "36"}], ",", 
            RowBox[{"10", "\[Rule]", "18"}], ",", 
            RowBox[{"12", "\[Rule]", "4"}], ",", 
            RowBox[{"5", "\[Rule]", "26"}], ",", 
            RowBox[{"8", "\[Rule]", "36"}], ",", 
            RowBox[{"15", "\[Rule]", "2"}]}], "\[RightAssociation]"}],
           ",", 
          RowBox[{"\[LeftAssociation]", 
           RowBox[{
            RowBox[{"1", "\[Rule]", "134596"}], ",", 
            RowBox[{"2", "\[Rule]", "21112"}], ",", 
            RowBox[{"3", "\[Rule]", "11704"}], ",", 
            RowBox[{"4", "\[Rule]", "3532"}], ",", 
            RowBox[{"5", "\[Rule]", "122"}], ",", 
            RowBox[{"7", "\[Rule]", "16"}], ",", 
            RowBox[{"8", "\[Rule]", "34"}], ",", 
            RowBox[{"9", "\[Rule]", "6"}], ",", 
            RowBox[{"10", "\[Rule]", "22"}], ",", 
            RowBox[{"11", "\[Rule]", "14"}], ",", 
            RowBox[{"12", "\[Rule]", "12"}], ",", 
            RowBox[{"14", "\[Rule]", "18"}], ",", 
            RowBox[{"15", "\[Rule]", "4"}], ",", 
            RowBox[{"18", "\[Rule]", "2"}], ",", 
            RowBox[{"None", "\[Rule]", "637328"}], ",", 
            RowBox[{"TooBig", "\[Rule]", "97670"}]}], 
           "\[RightAssociation]"}], ",", 
          RowBox[{"\[LeftAssociation]", 
           RowBox[{
            RowBox[{"1", "\[Rule]", "346104"}], ",", 
            RowBox[{"2", "\[Rule]", "40768"}], ",", 
            RowBox[{"3", "\[Rule]", "26936"}], ",", 
            RowBox[{"4", "\[Rule]", "9156"}], ",", 
            RowBox[{"5", "\[Rule]", "560"}], ",", 
            RowBox[{"8", "\[Rule]", "12"}], ",", 
            RowBox[{"9", "\[Rule]", "2"}], ",", 
            RowBox[{"11", "\[Rule]", "2"}], ",", 
            RowBox[{"12", "\[Rule]", "2"}], ",", 
            RowBox[{"13", "\[Rule]", "4"}], ",", 
            RowBox[{"14", "\[Rule]", "10"}], ",", 
            RowBox[{"15", "\[Rule]", "2"}], ",", 
            RowBox[{"18", "\[Rule]", "4"}], ",", 
            RowBox[{"None", "\[Rule]", "2292116"}], ",", 
            RowBox[{"TooBig", "\[Rule]", "650178"}]}], 
           "\[RightAssociation]"}]}], "}"}]}], "]"}], ",", 
      RowBox[{"ScalingFunctions", "\[Rule]", "\"\<Log\>\""}], ",", 
      RowBox[{"Frame", "\[Rule]", "True"}], ",", 
      RowBox[{"ChartLabels", "\[Rule]", 
       RowBox[{"{", 
        RowBox[{
         RowBox[{"Placed", "[", 
          RowBox[{
           RowBox[{"Join", "[", 
            RowBox[{
             RowBox[{"Range", "[", "18", "]"}], ",", 
             RowBox[{"{", 
              RowBox[{"\"\<\>\"", ",", "Infinity"}], "}"}]}], "]"}], 
           ",", "Under"}], "]"}], ",", "None"}], "}"}]}]}], "]"}]}], 
   "}"}], "]"}]], "Enter"]
}, Open  ]]

What if one considers, say, s = 3, okay = 2? For p = 2 and p = 3 there are usually not sufficient instances within the rule to pattern the rule vary of head states, so the longest-surviving guidelines are principally the identical as for s = 2, okay = 2. In the meantime, for p = 5 one has the 21-step “deterministic” busy beaver proven above, whereas for p = 4 there’s a 17-step-halting-time rule:

RulePlot

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; GraphicsRow[{RulePlot[
   TuringMachine[
    TMFixer[{{2, 1} -> {1, 0, -1}, {1, 0} -> {3, 1, 1}, {2, 0} -> {2, 
        1, -1}, {3, 0} -> {2, 0, 1}}, 3, 2]], {{1}, {{}, 0}}, 18, 
   Mesh -> True, Body -> False], 
  TuringMachinePlot[{{2, 1} -> {1, 0, -1}, {1, 0} -> {3, 1, 1}, {2, 
      0} -> {2, 1, -1}, {3, 0} -> {2, 0, 1}}, 3, 2, "RulePlot", 
   ImageSize -> {Automatic, 50}]}, Spacings -> 50]

Within the p = 5 case, the maximum-state machine is the next, with 30 states:

TMAppliesGraph

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; Labeled[Framed[
  TMAppliesGraph[
   List /@ Flatten[{{2, 1} -> {1, 1, -1}, {2, 1} -> {3, 1, 1}, {3, 
        1} -> {2, 0, 1}, {1, 0} -> {2, 1, 1}, {2, 0} -> {2, 1, -1}}], 
   25], FrameStyle -> LightGray], 
 TuringMachinePlot[{{2, 1} -> {1, 1, -1}, {2, 1} -> {3, 1, 1}, {3, 
     1} -> {2, 0, 1}, {1, 0} -> {2, 1, 1}, {2, 0} -> {2, 1, -1}}, 3, 
  2, "RulePlot"]]

There are a number of fascinating potential variants of the issues we’ve mentioned right here. For instance, as an alternative of contemplating multiway Turing machines the place all branches halt (or cycle), we will contemplate ones the place some branches proceed, even perhaps branching ceaselessly—however the place both, say, one or all the branches that do halt survive longest.

We are able to additionally contemplate Turing machines that begin from non-blank tapes. And—in analogy to what one may research in computational complexity concept—we will ask how the quantity (or dimension of area) of non-blank cells impacts halting occasions. (We are able to additionally research the “functions” computed by Turing machines by wanting on the transformations they suggest between preliminary tapes and last outputs.)

Causal Graphs

Our predominant concern right here thus far has been in mapping out the successions of states that may be obtained within the evolution of multiway Turing machines. However one of many discoveries of our Physics Project is that there’s a complementary option to perceive the behaviors of techniques, by wanting not at successions of states however at causal relationships between occasions that replace these states. And it’s the causal graph of those relationships that’s of most relevance if one needs to know what observers embedded inside a system can understand.

In our multiway Turing machines, we will consider every software of a Turing machine rule as an “occasion”. Every such occasion takes sure “enter” (the state of the top and the colour of the cell beneath it), and generates sure “output” (the brand new state of the top, the colour beneath it, and its place). The causal graph maps out what outputs from different occasions the enter to a given occasion requires, or, in different phrases, what the causal dependence is of 1 occasion on others.

For instance, for the odd Turing machine evolution

RulePlot

&#10005

RulePlot[TuringMachine[2506], {{1, 6}, Desk[0, 10]}, 20, 
 Mesh -> True, Body -> False]

the community of causal relationships between updating occasions is simply

TuringMachineCausalPlot

&#10005

Cell[CellGroupData[{Cell[BoxData[
 RowBox[{
  RowBox[{
  "CloudGet", "[", 
   "\"\<https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl\>\"", "]"}], ";"}]], "Enter"],

Cell[BoxData[
 RowBox[{
  RowBox[{"TuringMachineCausalPlot", "[", 
   RowBox[{"evol_", ",", " ", "s_", ",", " ", "k_"}], "]"}], " ", ":=",
   " ", 
  RowBox[{"Show", "[", 
   RowBox[{
    RowBox[{"TuringMachinePlot", "[", 
     RowBox[{
     "evol", ",", " ", "s", ",", " ", "k", ",", " ", 
      "\"\<EvolutionPlot\>\"", ",", " ", 
      RowBox[{"Mesh", "\[Rule]", " ", "True"}], ",", " ", 
      RowBox[{"Frame", "\[Rule]", " ", "False"}], ",", 
      RowBox[{"ColorRules", "\[Rule]", 
       RowBox[{"{", 
        RowBox[{
         RowBox[{"1", "\[Rule]", 
          RowBox[{"Lighter", "[", 
           RowBox[{
            InterpretationBox[
             ButtonBox[
              TooltipBox[
               GraphicsBox[{
                 {GrayLevel[0], RectangleBox[{0, 0}]}, 
                 {GrayLevel[0], RectangleBox[{1, -1}]}, 
                 {RGBColor[
                  0.9725464475844933, 0.6784269769073398, 
                   0.09019512441887687], 
                  RectangleBox[{0, -1}, {2, 1}]}},
                AspectRatio->1,
                DefaultBaseStyle->"ColorSwatchGraphics",
                Body->True,
                
                FrameStyle->RGBColor[
                 0.6483642983896623, 0.45228465127155987`, 
                  0.060130082945917915`],
                FrameTicks->None,
                
                ImageSize->
                 Dynamic[{
                  Automatic, 
                   1.35 (CurrentValue["FontCapHeight"]/
                    AbsoluteCurrentValue[Magnification])}],
                PlotRangePadding->None],
               StyleBox[
                RowBox[{"RGBColor", "[", 
                  
                  RowBox[{
                   "0.9725464475844933`", ",", "0.6784269769073398`", 
                    ",", "0.09019512441887687`"}], "]"}], NumberMarks -> 
                False]],
              Look->None,
              BaseStyle->{},
              BaselinePosition->Baseline,
              ButtonFunction:>With[{Typeset`box$ = EvaluationBox[]}, 
                If[
                 Not[
                  AbsoluteCurrentValue["Deployed"]], 
                 SelectionMove[Typeset`box$, All, Expression]; 
                 FrontEnd`Personal`$ColorSelectorInitialAlpha = 1; 
                 FrontEnd`Personal`$ColorSelectorInitialColor = 
                  RGBColor[
                   0.9725464475844933, 0.6784269769073398, 
                    0.09019512441887687]; 
                 FrontEnd`Personal`$ColorSelectorUseMakeBoxes = True; 
                 MathLink`CallFrontEnd[
                   FrontEnd`AttachCell[Typeset`box$, 
                    FrontEndResource["RGBColorValueSelector"], {
                    0, }, Left, High, 
                    "ClosingActions" -> {
                    "SelectionDeparture", "ParentChanged", 
                    "EvaluatorQuit"}]]]],
              DefaultBaseStyle->{},
              Evaluator->Automated,
              Methodology->"Preemptive"],
             RGBColor[
             0.9725464475844933, 0.6784269769073398, 
              0.09019512441887687],
             Editable->False,
             Selectable->False], ",", ".5"}], "]"}]}], ",", 
         RowBox[{"0", "\[Rule]", "White"}]}], "}"}]}]}], "]"}], ",", 
    " ", 
    RowBox[{"MapIndexed", "[", 
     RowBox[{
      RowBox[{
       RowBox[{"Graphics", "[", 
        RowBox[{"{", 
         RowBox[{
          RowBox[{"FaceForm", "[", 
           RowBox[{"Opacity", "[", 
            RowBox[{".8", ",", "Yellow"}], "]"}], "]"}], ",", " ", 
          RowBox[{"EdgeForm", "[", 
           RowBox[{"Directive", "[", " ", "Orange", "]"}], "]"}], ",",
           " ", 
          RowBox[{"Rectangle", "[", 
           RowBox[{
            RowBox[{"{", 
             RowBox[{
              RowBox[{"#1", "-", "1"}], ",", " ", 
              RowBox[{"First", "[", 
               RowBox[{
                RowBox[{"Length", "[", "evol", "]"}], "-", "#2", "+", 
                "1"}], "]"}]}], "}"}], ",", " ", 
            RowBox[{"{", 
             RowBox[{"#1", ",", " ", 
              RowBox[{"First", "[", 
               RowBox[{
                RowBox[{"Length", "[", "evol", "]"}], "-", "#2"}], 
               "]"}]}], "}"}]}], "]"}]}], "}"}], "]"}], "&"}], ",", 
      " ", 
      RowBox[{"evol", "[", 
       RowBox[{"[", 
        RowBox[{"All", ",", " ", "1", ",", " ", "2"}], "]"}], "]"}]}],
      "]"}], ",", " ", 
    RowBox[{"Drop", "[", 
     RowBox[{
      RowBox[{"MapIndexed", "[", 
       RowBox[{
        RowBox[{
         RowBox[{"Graphics", "[", 
          RowBox[{"{", 
           RowBox[{
            RowBox[{"FaceForm", "[", 
             RowBox[{"Opacity", "[", 
              RowBox[{".8", ",", "Yellow"}], "]"}], "]"}], ",", " ", 
            RowBox[{"EdgeForm", "[", 
             RowBox[{"Directive", "[", "Orange", "]"}], "]"}], ",", 
            " ", 
            RowBox[{"Rectangle", "[", 
             RowBox[{
              RowBox[{"{", 
               RowBox[{
                RowBox[{"#1", "-", "1"}], ",", " ", 
                RowBox[{"First", "[", 
                 RowBox[{
                  RowBox[{"Length", "[", "evol", "]"}], "-", "#2", 
                  "-", "1"}], "]"}]}], "}"}], ",", " ", 
              RowBox[{"{", 
               RowBox[{"#1", ",", " ", 
                RowBox[{"First", "[", 
                 RowBox[{
                  RowBox[{"Length", "[", "evol", "]"}], "-", "#2"}], 
                 "]"}]}], "}"}]}], "]"}]}], "}"}], "]"}], "&"}], ",", 
        " ", 
        RowBox[{"evol", "[", 
         RowBox[{"[", 
          RowBox[{"All", ",", " ", "1", ",", " ", "2"}], "]"}], 
         "]"}]}], "]"}], ",", " ", 
      RowBox[{"-", "1"}]}], "]"}], ",", " ", "\[IndentingNewLine]", 
    RowBox[{"Module", "[", 
     RowBox[{
      RowBox[{"{", 
       RowBox[{"coords", " ", "=", " ", 
        RowBox[{"Select", "[", 
         RowBox[{
          RowBox[{"GroupBy", "[", 
           RowBox[{"evol", ",", " ", 
            RowBox[{
             RowBox[{
              RowBox[{"First", "[", "#", "]"}], "[", 
              RowBox[{"[", "2", "]"}], "]"}], "&"}]}], "]"}], ",", 
          " ", 
          RowBox[{
           RowBox[{
            RowBox[{"Length", "[", "#", "]"}], ">", "1"}], "&"}]}], 
         "]"}]}], "}"}], ",", "\[IndentingNewLine]", 
      RowBox[{
       RowBox[{"coords", " ", "=", " ", 
        RowBox[{"AssociationMap", "[", 
         RowBox[{
          RowBox[{
           RowBox[{"Flatten", "[", 
            RowBox[{
             RowBox[{
              RowBox[{"Position", "[", 
               RowBox[{"evol", ",", " ", "#"}], "]"}], "&"}], "/@", 
             " ", 
             RowBox[{"coords", "[", "#", "]"}]}], "]"}], "&"}], ",", 
          " ", 
          RowBox[{"Keys", "[", "coords", "]"}]}], "]"}]}], ";", 
       "\[IndentingNewLine]", 
       RowBox[{"Table", "[", 
        RowBox[{
         RowBox[{"Graphics", "[", 
          RowBox[{"{", 
           RowBox[{
            RowBox[{
             RowBox[{
              RowBox[{
              "ResourceFunction", "[", 
               "\"\<WolframPhysicsProjectStyleData\>\"", "]"}], "[", 
              "\"\<CausalGraph\>\"", "]"}], "[", "\"\<EdgeStyle\>\"", 
             "]"}], ",", 
            RowBox[{"Thickness", "[", ".02", "]"}], ",", " ", 
            RowBox[{"Arrowheads", "[", ".07", "]"}], ",", 
            RowBox[{"MapIndexed", "[", 
             RowBox[{
              RowBox[{
               RowBox[{"Arrow", "[", 
                RowBox[{"{", 
                 RowBox[{
                  RowBox[{"{", 
                   RowBox[{
                    RowBox[{
                    RowBox[{
                    RowBox[{"Keys", "[", "coords", "]"}], "[", 
                    RowBox[{"[", "n", "]"}], "]"}], "-", "0.5"}], ",", 
                    RowBox[{
                    RowBox[{"Length", "[", "evol", "]"}], "-", 
                    "#"}]}], "}"}], ",", " ", 
                  RowBox[{"{", 
                   RowBox[{
                    RowBox[{
                    RowBox[{
                    RowBox[{"Keys", "[", "coords", "]"}], "[", 
                    RowBox[{"[", "n", "]"}], "]"}], "-", "0.5"}], ",", 
                    RowBox[{"First", "[", 
                    RowBox[{
                    RowBox[{"Length", "[", "evol", "]"}], "-", "#", 
                    "-", 
                    RowBox[{"(", 
                    RowBox[{
                    RowBox[{
                    RowBox[{
                    RowBox[{"Values", "[", "coords", "]"}], "[", 
                    RowBox[{"[", "n", "]"}], "]"}], "[", 
                    RowBox[{"[", 
                    RowBox[{"#2", "+", "1"}], "]"}], "]"}], "-", "#", 
                    "-", "1"}], ")"}]}], "]"}]}], "}"}]}], "}"}], 
                "]"}], "&"}], ",", 
              RowBox[{"Drop", "[", 
               RowBox[{
                RowBox[{
                 RowBox[{"Values", "[", "coords", "]"}], "[", 
                 RowBox[{"[", "n", "]"}], "]"}], ",", " ", 
                RowBox[{"-", "1"}]}], "]"}]}], "]"}]}], "}"}], "]"}], 
         ",", " ", 
         RowBox[{"{", 
          RowBox[{"n", ",", " ", 
           RowBox[{"Length", "[", "coords", "]"}]}], "}"}]}], 
        "]"}]}]}], "]"}]}], "]"}]}]], "Enter"],

Cell[BoxData[
 RowBox[{"TuringMachineCausalPlot", "[", 
  RowBox[{
   RowBox[{"TuringMachine", "[", 
    RowBox[{"2506", ",", 
     RowBox[{"{", 
      RowBox[{
       RowBox[{"{", 
        RowBox[{"1", ",", "6"}], "}"}], ",", 
       RowBox[{"Table", "[", 
        RowBox[{"0", ",", "10"}], "]"}]}], "}"}], ",", "20"}], "]"}], 
   ",", " ", "2", ",", " ", "2"}], "]"}]], "Enter"]
}, Open  ]]

yielding the causal graph:

TuringMachineCausalGraph

&#10005

ResourceFunction["TuringMachineCausalGraph"][2506, {{1, 6}, 
  Table[0, 10]}, 20, AspectRatio -> 1.2]

Persevering with longer offers

TuringMachineCausalGraph

&#10005

ResourceFunction[
  "TuringMachineCausalGraph"][2506, {{1}, {{}, 0}}, 100, 
 GraphLayout -> "LayeredDigraphEmbedding", AspectRatio -> 1.5]

or with a distinct graph rendering simply:

TuringMachineCausalGraph

&#10005

ResourceFunction[
  "TuringMachineCausalGraph"][2506, {{1}, {{}, 0}}, 100]

One also can outline causal graphs for multiway Turing machines. For example, take a look at a rule we thought-about above:

TuringMachinePlot

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; TuringMachinePlot[{{{1, 
     1} -> {1, 0, -1}}, {{1, 0} -> {1, 0, -1}}, {{1, 0} -> {1, 1, 
     1}}}, 2, 2, "RulePlot", ImageSize -> {Automatic, 50}]

The multiway graph that describes doable successions of states on this case is:

MultiwayTuringMachine

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; With[{t = 3}, 
 MultiwayTuringMachine[{{{1, 1} -> {1, 0, -1}}, {{1, 0} -> {1, 
      0, -1}}, {{1, 0} -> {1, 1, 1}}}, {{1, t + 1}, 
   Table[0, 2 t + 1]}, t, "StatesGraph", 
  GraphLayout -> "LayeredDigraphEmbedding", 
  VertexSize -> .17 {2 t + 1, 1}, PerformanceGoal -> "High quality", 
  AspectRatio -> 1.2]]

Now let’s explicitly present the replace occasion that transforms every state to its successor:

HackCausalGraph

&#10005

Cell[CellGroupData[{Cell[BoxData[
 RowBox[{
  RowBox[{
  "CloudGet", "[", 
   "\"\<https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl\>\"", "]"}], ";"}]], "Enter"],

Cell[BoxData[
 RowBox[{
  RowBox[{"HackCausalGraph", "[", "g_", "]"}], ":=", 
  RowBox[{"VertexDelete", "[", 
   RowBox[{"g", ",", 
    RowBox[{"Cases", "[", 
     RowBox[{
      RowBox[{"VertexList", "[", "g", "]"}], ",", 
      RowBox[{"{", 
       RowBox[{
        RowBox[{"\"\<\>\"", "\[Rule]", "\"\<\>\""}], ",", "___"}], 
       "}"}]}], "]"}]}], "]"}]}]], "Enter"],

Cell[BoxData[
 RowBox[{
  RowBox[{"HackCausalGraphStates", "[", 
   RowBox[{"g_", ",", "size_"}], "]"}], ":=", 
  RowBox[{"With", "[", 
   RowBox[{
    RowBox[{"{", 
     RowBox[{"gg", "=", 
      RowBox[{"VertexDelete", "[", 
       RowBox[{"g", ",", 
        RowBox[{"Cases", "[", 
         RowBox[{
          RowBox[{"VertexList", "[", "g", "]"}], ",", 
          RowBox[{"{", 
           RowBox[{
            RowBox[{"\"\<\>\"", "\[Rule]", "\"\<\>\""}], ",", "___"}],
            "}"}]}], "]"}]}], "]"}]}], "}"}], ",", 
    RowBox[{"Graph", "[", 
     RowBox[{"gg", ",", 
      RowBox[{"VertexSize", "\[Rule]", 
       RowBox[{"(", 
        RowBox[{
         RowBox[{
          RowBox[{"(", 
           RowBox[{"#", "\[Rule]", 
            RowBox[{"If", "[", 
             RowBox[{
              RowBox[{
               RowBox[{"Head", "[", "#", "]"}], "===", "String"}], 
              ",", 
              RowBox[{"size", "*", 
               RowBox[{"{", 
                RowBox[{"1", ",", " ", "0.25"}], "}"}]}], ",", 
              RowBox[{"size", "*", 
               RowBox[{"{", 
                RowBox[{"1", ",", "0.5"}], "}"}]}]}], "]"}]}], ")"}], 
          "&"}], "/@", 
         RowBox[{"VertexList", "[", "gg", "]"}]}], ")"}]}]}], "]"}]}],
    "]"}]}]], "Enter"],

Cell[BoxData[
 RowBox[{"With", "[", 
  RowBox[{
   RowBox[{"{", 
    RowBox[{"t", "=", "3"}], "}"}], ",", 
   RowBox[{"HackCausalGraphStates", "[", 
    RowBox[{
     RowBox[{"MultiwayTuringMachine", "[", 
      RowBox[{
       RowBox[{"{", 
        RowBox[{
         RowBox[{"{", 
          RowBox[{
           RowBox[{"{", 
            RowBox[{"1", ",", "1"}], "}"}], "\[Rule]", 
           RowBox[{"{", 
            RowBox[{"1", ",", "0", ",", 
             RowBox[{"-", "1"}]}], "}"}]}], "}"}], ",", 
         RowBox[{"{", 
          RowBox[{
           RowBox[{"{", 
            RowBox[{"1", ",", "0"}], "}"}], "\[Rule]", 
           RowBox[{"{", 
            RowBox[{"1", ",", "0", ",", 
             RowBox[{"-", "1"}]}], "}"}]}], "}"}], ",", 
         RowBox[{"{", 
          RowBox[{
           RowBox[{"{", 
            RowBox[{"1", ",", "0"}], "}"}], "\[Rule]", 
           RowBox[{"{", 
            RowBox[{"1", ",", "1", ",", "1"}], "}"}]}], "}"}]}], 
        "}"}], ",", 
       RowBox[{"{", 
        RowBox[{
         RowBox[{"{", 
          RowBox[{"1", ",", 
           RowBox[{"t", "+", "1"}]}], "}"}], ",", 
         RowBox[{"Table", "[", 
          RowBox[{"0", ",", 
           RowBox[{
            RowBox[{"2", " ", "t"}], "+", "1"}]}], "]"}]}], "}"}], 
       ",", "t", ",", "\"\<EvolutionEventsGraph\>\"", ",", 
       RowBox[{
       "GraphLayout", "\[Rule]", "\"\<LayeredDigraphEmbedding\>\""}], 
       ",", 
       RowBox["PerformanceGoal", "\[Rule]", "\"\<High quality\>\""], ",", 
       RowBox[{"AspectRatio", "\[Rule]", "1"}]}], "]"}], ",", 
     RowBox[{".17", "t"}]}], "]"}]}], "]"}]], "Enter"]
}, Open  ]]

Simply as for the deterministic case, we will determine the causal relationships between these replace occasions, right here indicated by orange edges:

HackCausalGraphStates

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; With[{t = 3}, 
 HackCausalGraphStates[
  MultiwayTuringMachine[{{{1, 1} -> {1, 0, -1}}, {{1, 0} -> {1, 
       0, -1}}, {{1, 0} -> {1, 1, 1}}}, {{1, t + 1}, 
    Table[0, 2 t + 1]}, t, "EvolutionCausalGraph", 
   GraphLayout -> "LayeredDigraphEmbedding", 
   PerformanceGoal -> "High quality", AspectRatio -> 1], .3 t]]

Conserving solely the occasions and their causal relationships we get the ultimate multiway causal graph:

MultiwayTuringMachine

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; With[{t = 3}, 
 MultiwayTuringMachine[{{{1, 1} -> {1, 0, -1}}, {{1, 0} -> {1, 
      0, -1}}, {{1, 0} -> {1, 1, 1}}}, {{1, t + 1}, 
   Table[0, 2 t + 1]}, t, "CausalGraph", 
  GraphLayout -> "LayeredDigraphEmbedding", VertexSize -> t {.2, .1}, 
  PerformanceGoal -> "High quality"]]

Persevering with for extra steps we get:

MultiwayTuringMachine

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; SimpleGraph[
 With[{t = 7}, 
  MultiwayTuringMachine[{{{1, 1} -> {1, 0, -1}}, {{1, 0} -> {1, 
       0, -1}}, {{1, 0} -> {1, 1, 1}}}, {{1, t + 1}, 
    Table[0, 2 t + 1]}, t, "CausalGraphStructure", 
   GraphLayout -> "LayeredDigraphEmbedding", 
   PerformanceGoal -> "High quality"]], AspectRatio -> 1]

Knowledgeable by our Physics Venture, we will consider every edge within the causal graph as representing a causal relationship between two occasions which observe one another in time. Within the causal graph for an odd “single-way” Turing machine these two occasions may additionally be separated in house, in order that in impact the causal graph defines how house and time are knitted collectively. Within the (multiway) causal graph for a multiway Turing machine, occasions will be separated not solely in house, but in addition in branchial house (or, in different phrases, they’ll happen on totally different branches within the evolution)—so the multiway causal graph will be considered defining how house, branchial house and time are knitted collectively.

We mentioned above how states in a multiway graph will be considered being specified by “multispace” which incorporates each odd house and branchial house coordinates. One can do kind of the identical for occasions in a multiway causal graph—suggesting a “multispace rendering of a multiway causal graph”:

TMCausalMultispaceIndicatorInit

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; Present[
 With[{t = 7}, 
  TMCausalMultispaceIndicatorInit[{{{1, 1} -> {1, 0, -1}}, {{1, 
       0} -> {1, 0, -1}}, {{1, 0} -> {1, 1, 1}}}, {{1, t + 1, 0}, 
    Table[0, 2 t + 1]}, t, {1, 4, 1}]], Boxed -> True, Axes -> True, 
 Ticks -> {None, None, None}, 
 AxesLabel -> {"branchlike", "spacelike", "timelike"}]

Completely different multiway Turing machines can have fairly totally different multiway causal graphs. Listed here are some samples for varied guidelines we thought-about above:

MultiwayTuringMachine

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; 
ResourceFunction["ParallelMapMonitored"][
 Labeled[Framed[
    Show[With[{t = 7}, 
      [email protected]
       MultiwayTuringMachine[#, {{1, t + 1}, Table[0, 2 t + 1]}, t, 
        "CausalGraphStructure", 
        GraphLayout -> "LayeredDigraphEmbedding", 
        PerformanceGoal -> "High quality"]], AspectRatio -> 1, 
     ImageSize -> ], FrameStyle -> LightGray], 
   TuringMachinePlot[#, 2, 2, "RulePlot", 
    ImageSize -> {Automatic, 30}]] &, {{{{1, 0} -> {1, 0, -1}}, {{1, 
      0} -> {1, 0, 1}}}, {{{1, 0} -> {1, 1, -1}}, {{1, 0} -> {1, 1, 
      1}}}, {{{1, 0} -> {1, 1, -1}}, {{1, 0} -> {1, 0, 1}}}, {{{1, 
      1} -> {1, 1, -1}}, {{1, 0} -> {1, 1, -1}}, {{1, 0} -> {1, 1, 
      1}}}, {{{1, 1} -> {1, 0, -1}}, {{1, 0} -> {1, 1, -1}}, {{1, 
      0} -> {1, 1, 1}}}, {{{1, 1} -> {1, 0, -1}}, {{1, 0} -> {1, 
      1, -1}}, {{1, 0} -> {1, 0, 1}}}, {{{1, 1} -> {1, 0, -1}}, {{1, 
      0} -> {1, 0, -1}}, {{1, 0} -> {1, 1, 1}}}, {{{1, 1} -> {1, 0, 
      1}}, {{1, 0} -> {1, 0, -1}}, {{1, 0} -> {1, 1, 1}}}}]

These multiway causal graphs in a way seize all causal relationships inside and between totally different doable paths adopted within the multiway graph. If we choose a selected path within the multiway graph (akin to a selected sequence of selections about which case within the multiway Turing machine rule to use at every step) then this may yield a “deterministic” evolution. And this evolution can have a corresponding causal graph—that should at all times be a subgraph of the complete multiway causal graph.

Causal Invariance

Each time there may be multiple doable successor for a given state within the evolution of a multiway Turing machine, this may result in a number of branches within the multiway graph. Completely different doable “paths of historical past” (with totally different selections about which case within the rule to use at every step) then correspond to following totally different branches. And in a case like this

MultiwayTuringMachine

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; Row[{With[{t = 5}, 
   MultiwayTuringMachine[{{{1, 0} -> {1, 1, -1}}, {{1, 0} -> {1, 
        0, -1}}}, {{1, t + 1, 0}, Table[0, 2 t + 1]}, t, 
    "StatesGraphStructure", AspectRatio -> .4, 
    GraphLayout -> "LayeredDigraphEmbedding", 
    PerformanceGoal -> "High quality", ImageSize -> ]], 
  TuringMachinePlot[
   [email protected]{{{1, 0} -> {1, 1, -1}}, {{1, 0} -> {1, 0, -1}}}, 2, 2, 
   "RulePlot", ImageSize -> {Automatic, 30}]}, Spacer[30]]

as soon as one has picked a department one is “dedicated”: one can by no means subsequently attain every other branches—and paths that diverge by no means converge once more.

However in a case like this it’s a distinct story

MultiwayTuringMachine

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; Row[{With[{t = 6}, 
   MultiwayTuringMachine[{{{1, 1} -> {1, 0, -1}}, {{1, 0} -> {1, 
        0, -1}}, {{1, 0} -> {1, 1, 1}}}, {{1, t + 1}, 
     Table[0, 2 t + 1]}, t, "StatesGraphStructure", AspectRatio -> .6,
     GraphLayout -> "LayeredDigraphEmbedding", 
    PerformanceGoal -> "High quality", ImageSize -> Automated, 170]], 
  TuringMachinePlot[
   [email protected]{{{1, 1} -> {1, 0, -1}}, {{1, 0} -> {1, 0, -1}}, {{1, 
        0} -> {1, 1, 1}}}, 2, 2, "RulePlot", 
   ImageSize -> {Automatic, 30}]}, Spacer[20]]

as a result of right here—at the very least if one goes far sufficient in producing the multiway graph—each pair of paths that diverge should finally converge once more. In different phrases, if one takes a “mistaken flip”, one can at all times recuperate. Or, put one other method, no matter sequence of guidelines one applies, it’s at all times doable to succeed in eventual consistency within the outcomes one will get.

This property is intently associated to a property that’s essential in our Physics Venture: causal invariance. When causal invariance is current, it implies that the causal graphs generated by following any doable path should at all times be the identical. In different phrases, although the multiway system in a way permits many doable histories, the community of causal relationships obtained in every case will at all times be the identical—in order that with respect to causal relationships there may be primarily only one “goal actuality” about how the system behaves.

(By the best way, the multiway causal graph comprises extra data than the person causal graphs, as a result of it additionally describes how all of the causal graphs—from all doable histories—“knit collectively” throughout house, time and branchial house.

There’s a subtlety which we won’t discover intimately right here. Whether or not one considers branches within the multiway graph to have converged will depend on how one defines equivalence of states. Within the multiway graphs we’ve drawn, we’ve achieved this simply by taking a look at whether or not the instantaneous states of Turing machines are the identical. And in doing this, the merging of branches is expounded to a property usually known as confluence. However to make sure that we get full causal invariance we will as an alternative contemplate states to be equal if along with having the identical tape configurations, the causal graphs that result in them are isomorphic (in order that in a way we’re contemplating a “causal multiway graph”).

So what multiway Turing machines are causal invariant (or at the very least confluent)? If a multiway Turing machine has guidelines that make it deterministic (with out halting), and thus successfully “single method”, then it’s trivially causal invariant. If a multiway Turing machine has a number of halting states it’s inevitably not causal invariant—as a result of if it “falls into” any one of many halting states, then it will probably by no means “get out” and attain one other. However, if there may be only a single halting state, and all doable histories result in it, then a multiway Turing machine will at the very least be confluent (and by way of its computation will be considered at all times “reaching a last distinctive reply”, or “regular kind”). Lastly, within the “rulial limit” the place the multiway Turing machine can use any doable rule, causal invariance is inevitable.

Generally, causal invariance just isn’t notably uncommon amongst multiway Turing machines. For s = 1, okay = 1 guidelines, it’s inevitable. For s = 1, okay = 2 guidelines listed below are some examples of multiway graphs and multiway causal graphs for guidelines that seem like at the very least confluent

MultiwayTuringMachine

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; Grid[Partition[
  ResourceFunction["ParallelMapMonitored"][
   With[{t = 6}, 
     Row[{MultiwayTuringMachine[#, {{1, t + 1}, Table[0, 2 t + 1]}, t,
         "StatesGraphStructure", AspectRatio -> 1, 
        ImageSize -> {120, 120}, 
        GraphLayout -> "LayeredDigraphEmbedding"], 
       SimpleGraph[
        MultiwayTuringMachine[#, {{1, t + 1}, Table[0, 2 t + 1]}, t, 
         "CausalGraphStructure", AspectRatio -> 1, 
         ImageSize -> {120, 120}, 
         GraphLayout -> "LayeredDigraphEmbedding"]]}, Body -> True, 
      FrameStyle -> 
       LightGray]] &, {{{{1, 1} -> {1, 0, -1}}, {{1, 1} -> {1, 
        1, -1}}, {{1, 0} -> {1, 0, 1}}}, {{{1, 0} -> {1, 0, -1}}, {{1,
         0} -> {1, 0, 1}}}, {{{1, 1} -> {1, 0, -1}}, {{1, 0} -> {1, 
        0, -1}}, {{1, 0} -> {1, 1, 1}}}, {{{1, 1} -> {1, 0, 1}}, {{1, 
        0} -> {1, 0, -1}}, {{1, 0} -> {1, 1, 1}}}}], 2]]

and ones that don’t:

MultiwayTuringMachine

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; Grid[Partition[
  ResourceFunction["ParallelMapMonitored"][
   With[{t = 6}, 
     Row[{MultiwayTuringMachine[#, {{1, t + 1}, Table[0, 2 t + 1]}, t,
         "StatesGraphStructure", AspectRatio -> 1, 
        ImageSize -> {120, 120}, 
        GraphLayout -> "LayeredDigraphEmbedding"], 
       SimpleGraph[
        MultiwayTuringMachine[#, {{1, t + 1}, Table[0, 2 t + 1]}, t, 
         "CausalGraphStructure", AspectRatio -> 1, 
         ImageSize -> {120, 120}, 
         GraphLayout -> "LayeredDigraphEmbedding"]]}, Body -> True, 
      FrameStyle -> 
       LightGray]] &, {{{{1, 0} -> {1, 1, -1}}, {{1, 0} -> {1, 1, 
        1}}}, {{{1, 0} -> {1, 1, -1}}, {{1, 0} -> {1, 0, 1}}}, {{{1, 
        1} -> {1, 1, -1}}, {{1, 0} -> {1, 1, -1}}, {{1, 0} -> {1, 1, 
        1}}}, {{{1, 1} -> {1, 0, -1}}, {{1, 0} -> {1, 1, -1}}, {{1, 
        0} -> {1, 1, 1}}}}], 2]]

(Notice that generally it may be undecidable if a given multiway Turing machine is causal invariant—or confluent—or not. For even when two branches finally merge, there is no such thing as a a priori higher certain on what number of steps this may take—although in observe for easy guidelines it sometimes appears to resolve fairly shortly.)

Finite Tapes

Up to now we’ve at all times assumed that the tapes in our Turing machines are unbounded. However simply as we did in our earlier venture of studying the rulial space of Turing machines, we will additionally contemplate the case of Turing machines with bounded—say cyclic—tapes with a finite variety of “cells” n.

Such a Turing machine has a complete of n s okayn doable full states—and for a given n we will assemble an entire state transition graph. For an odd deterministic Turing machine, these graphs at all times have a single outgoing edge from every state node (although probably a number of incoming edges). So, for instance, with the rule

RulePlot

&#10005

RulePlot[TuringMachine[192]]

the state transition graph for a length-3 tape is:

CyclicTMSTG1

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; With[{g = 
   CyclicTMSTG1[ResourceFunction["TuringMachineFromNumber"][192], 1, 
    2, 3]}, Graph[g, 
  VertexLabels -> (# -> TMStatePlot[#, ImageSize -> 30] & /@ 
     VertexList[g])]]

Listed here are another s = 2, okay = 2 examples (all for n = 3):

CyclicTMSTG1

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; 
Labeled[Framed[
    Graph[CyclicTMSTG1[ResourceFunction["TuringMachineFromNumber"][#],
       1, 2, 3], ImageSize -> {120, 120}], FrameStyle -> LightGray], 
   RulePlot[TuringMachine[#], ImageSize -> 140]] & /@ {128, 256, 512, 
  1088}

In all instances, what we see are sure cycles of states which are visited repeatedly, fed by transients containing different states.

For multiway Turing machines reminiscent of

TuringMachinePlot

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; TuringMachinePlot[
 [email protected]{{{{1, 1} -> {1, 0, -1}}, {{1, 1} -> {1, 0, 
       1}}}}, 2, 2, "RulePlot"]

the construction of the state transition graph will be totally different, with nodes having each kind of than 1 outgoing edge:

CyclicTMSTG1

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; With[{g = 
   CyclicTMSTG1[
    [email protected]{{{{1, 1} -> {1, 0, -1}}, {{1, 1} -> {1, 0, 1}}}}, 1, 2, 
    3]}, Graph[g, 
  VertexLabels -> (# -> TMStatePlot[#, ImageSize -> 30] & /@ 
     VertexList[g])]]

Ranging from the node akin to a selected state, the subgraph reached from that state is the multiway graph akin to the evolution from that state. Halting happens when there may be outdegree 0 at a node—and the three nodes on the backside of the picture correspond to states the place the Turing machine has instantly halted.

Listed here are outcomes for another multiway Turing machines, right here with tape dimension n = 5, indicating halting states in pink:

CyclicTMSTG1

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; 
With[{rules = #}, Labeled[Framed[
     HighlightGraph[
      Graph[CyclicTMSTG1[[email protected], 1, 2, 5], 
       ImageSize -> {140, 140}], 
      Choose[VertexList[
        CyclicTMSTG1[[email protected], 1, 2, 5]], ! 
         TMAppliesQ[rules, #] &], VertexSize -> 0.75], 
     FrameStyle -> LightGray], 
    TuringMachinePlot[[email protected]#, 2, 2, "RulePlot", 
     ImageSize -> {Automatic, 40}]]] & /@ {{{{1, 1} -> {1, 
      0, -1}}, {{1, 1} -> {1, 0, 1}}}, {{{1, 1} -> {1, 1, -1}}, {{1, 
      1} -> {1, 0, 1}}}, {{{1, 1} -> {1, 1, -1}}, {{1, 1} -> {1, 
      0, -1}}, {{1, 0} -> {1, 1, -1}}}, {{{1, 1} -> {1, 0, 1}}, {{1, 
      0} -> {1, 0, -1}}, {{1, 0} -> {1, 0, 1}}}, {{{1, 0} -> {1, 
      1, -1}}, {{1, 0} -> {1, 0, -1}}, {{1, 0} -> {1, 0, 1}}}, {{{1, 
      0} -> {1, 1, -1}}, {{1, 0} -> {1, 1, 1}}, {{1, 0} -> {1, 0, 
      1}}}}

What occurs when there are extra instances p within the multiway Turing machine rule? If all doable instances are allowed, in order that p = 2 s2 okay2, then we get the complete rulial multiway graph. For dimension n = 3 that is

NeighboringConfigurations

&#10005

Cell[CellGroupData[{Cell[BoxData[
 RowBox[{
  RowBox[{
  "CloudGet", "[", 
   "\"\<https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl\>\"", "]"}], ";"}]], "Enter"],

Cell[BoxData[
 RowBox[{
  RowBox[{"NeighboringConfigurations", "[", 
   RowBox[{
    RowBox[{"{", 
     RowBox[{
      RowBox[{"{", 
       RowBox[{"s0_Integer", ",", "pos0_Integer"}], "}"}], ",", 
      "tape0_List"}], "}"}], ",", 
    RowBox[{"{", 
     RowBox[{"s_Integer", ",", "k_Integer"}], "}"}], ",", 
    RowBox[{"offs_", ":", 
     RowBox[{"{", 
      RowBox[{
       RowBox[{"-", "1"}], ",", "1"}], "}"}]}]}], "]"}], ":=", 
  RowBox[{"Flatten", "[", 
   RowBox[{
    RowBox[{"Table", "[", 
     RowBox[{
      RowBox[{"{", 
       RowBox[{
        RowBox[{"{", 
         RowBox[{"s1", ",", 
          RowBox[{"Mod", "[", 
           RowBox[{
            RowBox[{"pos0", "+", "pos1"}], ",", 
            RowBox[{"Length", "[", "tape0", "]"}], ",", "1"}], 
           "]"}]}], "}"}], ",", "tape1"}], "}"}], ",", 
      RowBox[{"{", 
       RowBox[{"s1", ",", "s"}], "}"}], ",", 
      RowBox[{"{", 
       RowBox[{"pos1", ",", "offs"}], "}"}], ",", 
      RowBox[{"{", 
       RowBox[{"tape1", ",", 
        RowBox[{"Table", "[", 
         RowBox[{
          RowBox[{"ReplacePart", "[", 
           RowBox[{"tape0", ",", 
            RowBox[{"pos0", "\[Rule]", "i"}]}], "]"}], ",", 
          RowBox[{"{", 
           RowBox[{"i", ",", "0", ",", 
            RowBox[{"k", "-", "1"}]}], "}"}]}], "]"}]}], "}"}]}], 
     "]"}], ",", "2"}], "]"}]}]], "Enter"],

Cell[BoxData[
 RowBox[{
  RowBox[{"TMNCGraphX", "[", 
   RowBox[{"tlen_Integer", ",", 
    RowBox[{"{", 
     RowBox[{"s_Integer", ",", "k_Integer"}], "}"}], ",", 
    RowBox[{"offs_", ":", 
     RowBox[{"{", 
      RowBox[{
       RowBox[{"-", "1"}], ",", "1"}], "}"}]}]}], "]"}], ":=", 
  RowBox[{"Graph", "[", 
   RowBox[{
    RowBox[{"Flatten", "[", 
     RowBox[{"Table", "[", 
      RowBox[{
       RowBox[{
        RowBox[{
         RowBox[{
          RowBox[{"{", 
           RowBox[{
            RowBox[{"{", 
             RowBox[{"s0", ",", "pos0"}], "}"}], ",", "tape0"}], 
           "}"}], "\[DirectedEdge]", "#"}], "&"}], "/@", 
        RowBox[{"NeighboringConfigurations", "[", 
         RowBox[{
          RowBox[{"{", 
           RowBox[{
            RowBox[{"{", 
             RowBox[{"s0", ",", "pos0"}], "}"}], ",", "tape0"}], 
           "}"}], ",", 
          RowBox[{"{", 
           RowBox[{"s", ",", "k"}], "}"}], ",", "offs"}], "]"}]}], 
       ",", 
       RowBox[{"{", 
        RowBox[{"s0", ",", "s"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"pos0", ",", "tlen"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"tape0", ",", 
         RowBox[{"Tuples", "[", 
          RowBox[{
           RowBox[{"Range", "[", 
            RowBox[{"0", ",", 
             RowBox[{"k", "-", "1"}]}], "]"}], ",", "tlen"}], "]"}]}],
         "}"}]}], "]"}], "]"}], ",", 
    RowBox[{"VertexShapeFunction", "\[Rule]", 
     RowBox[{"(", 
      RowBox[{
       RowBox[{"Inset", "[", 
        RowBox[{
         RowBox[{"Framed", "[", 
          RowBox[{
           RowBox[{"RulePlot", "[", 
            RowBox[{
             RowBox[{"TuringMachine", "[", 
              RowBox[{"{", 
               RowBox[{"0", ",", 
                RowBox[{"Max", "[", 
                 RowBox[{"s", ",", "2"}], "]"}], ",", 
                RowBox[{"Max", "[", 
                 RowBox[{"k", ",", "2"}], "]"}]}], "}"}], "]"}], ",", 
             
             RowBox[{"{", 
              RowBox[{
               RowBox[{"{", 
                RowBox[{"1", ",", 
                 RowBox[{"#2", "[", 
                  RowBox[{"[", 
                   RowBox[{"1", ",", "2"}], "]"}], "]"}]}], "}"}], 
               ",", 
               RowBox[{"#2", "[", 
                RowBox[{"[", "2", "]"}], "]"}]}], "}"}], ",", "0", 
             ",", 
             RowBox[{"Mesh", "\[Rule]", "All"}], ",", 
             RowBox[{"Frame", "\[Rule]", "False"}], ",", 
             RowBox[{"ImageSize", "\[Rule]", "40"}]}], "]"}], ",", 
           RowBox[{"Background", "\[Rule]", 
            RowBox[{"Directive", "[", 
             RowBox[{
              RowBox[{"Opacity", "[", "0.2", "]"}], ",", 
              RowBox[{"Hue", "[", 
               RowBox[{"0.62", ",", "0.45", ",", "0.87"}], "]"}]}], 
             "]"}]}], ",", 
           RowBox[{"FrameMargins", "\[Rule]", 
            RowBox[{"{", 
             RowBox[{
              RowBox[{"{", 
               RowBox[{"2", ",", "2"}], "}"}], ",", 
              RowBox[{"{", 
               RowBox[{"0", ",", "0"}], "}"}]}], "}"}]}], ",", 
           RowBox[{"RoundingRadius", "\[Rule]", "0"}], ",", 
           RowBox[{"FrameStyle", "\[Rule]", 
            RowBox[{"Directive", "[", 
             RowBox[{
              RowBox[{"Opacity", "[", "0.5", "]"}], ",", 
              RowBox[{"Hue", "[", 
               RowBox[{"0.62", ",", "0.52", ",", "0.82"}], "]"}]}], 
             "]"}]}]}], "]"}], ",", "#1"}], "]"}], "&"}], ")"}]}], 
    ",", 
    RowBox[{"EdgeStyle", "\[Rule]", 
     RowBox[{
      RowBox[{
       RowBox[{
       "ResourceFunction", "[", 
        "\"\<WolframPhysicsProjectStyleData\>\"", "]"}], "[", 
       "\"\<StatesGraph\>\"", "]"}], "[", "\"\<EdgeStyle\>\"", 
      "]"}]}]}], "]"}]}]], "Enter"],

Cell[BoxData[
 RowBox[{"TMNCGraphX", "[", 
  RowBox[{"3", ",", 
   RowBox[{"{", 
    RowBox[{"1", ",", "2"}], "}"}]}], "]"}]], "Enter"]
}, Open  ]]

whereas for n = 5 it’s:

NeighboringConfigurations

&#10005

Cell[CellGroupData[{Cell[BoxData[
 RowBox[{
  RowBox[{
  "CloudGet", "[", 
   "\"\<https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl\>\"", "]"}], ";"}]], "Enter"],

Cell[BoxData[
 RowBox[{
  RowBox[{"NeighboringConfigurations", "[", 
   RowBox[{
    RowBox[{"{", 
     RowBox[{
      RowBox[{"{", 
       RowBox[{"s0_Integer", ",", "pos0_Integer"}], "}"}], ",", 
      "tape0_List"}], "}"}], ",", 
    RowBox[{"{", 
     RowBox[{"s_Integer", ",", "k_Integer"}], "}"}], ",", 
    RowBox[{"offs_", ":", 
     RowBox[{"{", 
      RowBox[{
       RowBox[{"-", "1"}], ",", "1"}], "}"}]}]}], "]"}], ":=", 
  RowBox[{"Flatten", "[", 
   RowBox[{
    RowBox[{"Table", "[", 
     RowBox[{
      RowBox[{"{", 
       RowBox[{
        RowBox[{"{", 
         RowBox[{"s1", ",", 
          RowBox[{"Mod", "[", 
           RowBox[{
            RowBox[{"pos0", "+", "pos1"}], ",", 
            RowBox[{"Length", "[", "tape0", "]"}], ",", "1"}], 
           "]"}]}], "}"}], ",", "tape1"}], "}"}], ",", 
      RowBox[{"{", 
       RowBox[{"s1", ",", "s"}], "}"}], ",", 
      RowBox[{"{", 
       RowBox[{"pos1", ",", "offs"}], "}"}], ",", 
      RowBox[{"{", 
       RowBox[{"tape1", ",", 
        RowBox[{"Table", "[", 
         RowBox[{
          RowBox[{"ReplacePart", "[", 
           RowBox[{"tape0", ",", 
            RowBox[{"pos0", "\[Rule]", "i"}]}], "]"}], ",", 
          RowBox[{"{", 
           RowBox[{"i", ",", "0", ",", 
            RowBox[{"k", "-", "1"}]}], "}"}]}], "]"}]}], "}"}]}], 
     "]"}], ",", "2"}], "]"}]}]], "Enter"],

Cell[BoxData[
 RowBox[{
  RowBox[{"TMNCGraph", "[", 
   RowBox[{"tlen_Integer", ",", 
    RowBox[{"{", 
     RowBox[{"s_Integer", ",", "k_Integer"}], "}"}], ",", 
    RowBox[{"offs_", ":", 
     RowBox[{"{", 
      RowBox[{
       RowBox[{"-", "1"}], ",", "1"}], "}"}]}]}], "]"}], ":=", 
  RowBox[{"Graph", "[", 
   RowBox[{
    RowBox[{"Flatten", "[", 
     RowBox[{"Table", "[", 
      RowBox[{
       RowBox[{
        RowBox[{
         RowBox[{
          RowBox[{"{", 
           RowBox[{
            RowBox[{"{", 
             RowBox[{"s0", ",", "pos0"}], "}"}], ",", "tape0"}], 
           "}"}], "\[DirectedEdge]", "#"}], "&"}], "/@", 
        RowBox[{"NeighboringConfigurations", "[", 
         RowBox[{
          RowBox[{"{", 
           RowBox[{
            RowBox[{"{", 
             RowBox[{"s0", ",", "pos0"}], "}"}], ",", "tape0"}], 
           "}"}], ",", 
          RowBox[{"{", 
           RowBox[{"s", ",", "k"}], "}"}], ",", "offs"}], "]"}]}], 
       ",", 
       RowBox[{"{", 
        RowBox[{"s0", ",", "s"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"pos0", ",", "tlen"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"tape0", ",", 
         RowBox[{"Tuples", "[", 
          RowBox[{
           RowBox[{"Range", "[", 
            RowBox[{"0", ",", 
             RowBox[{"k", "-", "1"}]}], "]"}], ",", "tlen"}], "]"}]}],
         "}"}]}], "]"}], "]"}], ",", 
    RowBox[{"EdgeStyle", "\[Rule]", 
     RowBox[{
      RowBox[{
       RowBox[{
       "ResourceFunction", "[", 
        "\"\<WolframPhysicsProjectStyleData\>\"", "]"}], "[", 
       "\"\<StatesGraph\>\"", "]"}], "[", "\"\<EdgeStyle\>\"", 
      "]"}]}], ",", 
    RowBox[{"VertexStyle", "\[Rule]", 
     RowBox[{
      RowBox[{
       RowBox[{
       "ResourceFunction", "[", 
        "\"\<WolframPhysicsProjectStyleData\>\"", "]"}], "[", 
       "\"\<StatesGraph\>\"", "]"}], "[", "\"\<VertexStyle\>\"", 
      "]"}]}]}], "]"}]}]], "Enter"],

Cell[BoxData[
 RowBox[{"Graph", "[", 
  RowBox[{"TMNCGraph", "[", 
   RowBox[{"5", ",", 
    RowBox[{"{", 
     RowBox[{"1", ",", "2"}], "}"}]}], "]"}], "]"}]], "Enter"]
}, Open  ]]

This “rulial-limit” multiway graph has the property that it’s in a way fully uniform: the graph is vertex transitive, in order that the neighborhood of each node is similar. (The graph corresponds to the Cayley graph of a finite “Turing machine group”, right here \!\(
\*SubsuperscriptBox[\(TM\), \(1, 2\), \(n\)]\ = \ \(
\*SubscriptBox[\(\[DoubleStruckCapitalZ]\), \(n\)]\ ⋉\
\*SuperscriptBox[\((
\*SubscriptBox[\(\[DoubleStruckCapitalZ]\), \(2\)])\), \(n\)]\)\)
.)

However whereas this “rulial-limit” graph in a way includes maximal nondeterminism and maximal branching, it additionally exhibits maximal merging, and actually ranging from any node, paths that department should at all times be capable to merge once more—as on this instance for the n = 3 case (right here proven with two totally different graph renderings):

NeighboringConfigurations

&#10005

Cell[CellGroupData[{Cell[BoxData[
 RowBox[{
  RowBox[{
  "CloudGet", "[", 
   "\"\<https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl\>\"", "]"}], ";"}]], "Enter"],

Cell[BoxData[
 RowBox[{
  RowBox[{"NeighboringConfigurations", "[", 
   RowBox[{
    RowBox[{"{", 
     RowBox[{
      RowBox[{"{", 
       RowBox[{"s0_Integer", ",", "pos0_Integer"}], "}"}], ",", 
      "tape0_List"}], "}"}], ",", 
    RowBox[{"{", 
     RowBox[{"s_Integer", ",", "k_Integer"}], "}"}], ",", 
    RowBox[{"offs_", ":", 
     RowBox[{"{", 
      RowBox[{
       RowBox[{"-", "1"}], ",", "1"}], "}"}]}]}], "]"}], ":=", 
  RowBox[{"Flatten", "[", 
   RowBox[{
    RowBox[{"Table", "[", 
     RowBox[{
      RowBox[{"{", 
       RowBox[{
        RowBox[{"{", 
         RowBox[{"s1", ",", 
          RowBox[{"Mod", "[", 
           RowBox[{
            RowBox[{"pos0", "+", "pos1"}], ",", 
            RowBox[{"Length", "[", "tape0", "]"}], ",", "1"}], 
           "]"}]}], "}"}], ",", "tape1"}], "}"}], ",", 
      RowBox[{"{", 
       RowBox[{"s1", ",", "s"}], "}"}], ",", 
      RowBox[{"{", 
       RowBox[{"pos1", ",", "offs"}], "}"}], ",", 
      RowBox[{"{", 
       RowBox[{"tape1", ",", 
        RowBox[{"Table", "[", 
         RowBox[{
          RowBox[{"ReplacePart", "[", 
           RowBox[{"tape0", ",", 
            RowBox[{"pos0", "\[Rule]", "i"}]}], "]"}], ",", 
          RowBox[{"{", 
           RowBox[{"i", ",", "0", ",", 
            RowBox[{"k", "-", "1"}]}], "}"}]}], "]"}]}], "}"}]}], 
     "]"}], ",", "2"}], "]"}]}]], "Enter"],

Cell[BoxData[
 RowBox[{
  RowBox[{"TMNCGraph", "[", 
   RowBox[{"tlen_Integer", ",", 
    RowBox[{"{", 
     RowBox[{"s_Integer", ",", "k_Integer"}], "}"}], ",", 
    RowBox[{"offs_", ":", 
     RowBox[{"{", 
      RowBox[{
       RowBox[{"-", "1"}], ",", "1"}], "}"}]}]}], "]"}], ":=", 
  RowBox[{"Graph", "[", 
   RowBox[{
    RowBox[{"Flatten", "[", 
     RowBox[{"Table", "[", 
      RowBox[{
       RowBox[{
        RowBox[{
         RowBox[{
          RowBox[{"{", 
           RowBox[{
            RowBox[{"{", 
             RowBox[{"s0", ",", "pos0"}], "}"}], ",", "tape0"}], 
           "}"}], "\[DirectedEdge]", "#"}], "&"}], "/@", 
        RowBox[{"NeighboringConfigurations", "[", 
         RowBox[{
          RowBox[{"{", 
           RowBox[{
            RowBox[{"{", 
             RowBox[{"s0", ",", "pos0"}], "}"}], ",", "tape0"}], 
           "}"}], ",", 
          RowBox[{"{", 
           RowBox[{"s", ",", "k"}], "}"}], ",", "offs"}], "]"}]}], 
       ",", 
       RowBox[{"{", 
        RowBox[{"s0", ",", "s"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"pos0", ",", "tlen"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{"tape0", ",", 
         RowBox[{"Tuples", "[", 
          RowBox[{
           RowBox[{"Range", "[", 
            RowBox[{"0", ",", 
             RowBox[{"k", "-", "1"}]}], "]"}], ",", "tlen"}], "]"}]}],
         "}"}]}], "]"}], "]"}], ",", 
    RowBox[{"EdgeStyle", "\[Rule]", 
     RowBox[{
      RowBox[{
       RowBox[{
       "ResourceFunction", "[", 
        "\"\<WolframPhysicsProjectStyleData\>\"", "]"}], "[", 
       "\"\<StatesGraph\>\"", "]"}], "[", "\"\<EdgeStyle\>\"", 
      "]"}]}], ",", 
    RowBox[{"VertexStyle", "\[Rule]", 
     RowBox[{
      RowBox[{
       RowBox[{
       "ResourceFunction", "[", 
        "\"\<WolframPhysicsProjectStyleData\>\"", "]"}], "[", 
       "\"\<StatesGraph\>\"", "]"}], "[", "\"\<VertexStyle\>\"", 
      "]"}]}]}], "]"}]}]], "Enter"],

Cell[BoxData[
 RowBox[{
  RowBox[{"gx", "=", 
   RowBox[{"IndexGraph", "[", 
    RowBox[{"Graph", "[", 
     RowBox[{"TMNCGraph", "[", 
      RowBox[{"3", ",", 
       RowBox[{"{", 
        RowBox[{"1", ",", "2"}], "}"}]}], "]"}], "]"}], "]"}]}], 
  ";"}]], "Enter"],

Cell[BoxData[
 RowBox[{
  RowBox[{
   RowBox[{"{", 
    RowBox[{"#", ",", 
     RowBox[{"LayeredGraphPlot", "[", "#", "]"}]}], "}"}], "&"}], "[", 
  RowBox[{"With", "[", 
   RowBox[{
    RowBox[{"{", 
     RowBox[{
      RowBox[{"i", "=", "1"}], ",", 
      RowBox[{"j", "=", "24"}]}], "}"}], ",", "\[IndentingNewLine]", 
    RowBox[{"Module", "[", 
     RowBox[{
      RowBox[{"{", 
       RowBox[{"sg", " ", "=", " ", 
        RowBox[{
         RowBox[{
          RowBox[{
           RowBox[{
            RowBox[{"Subgraph", "[", 
             RowBox[{"gx", ",", 
              RowBox[{"PathGraph", "[", "#", "]"}]}], "]"}], "&"}], "/@", 
           RowBox[{"{", 
            RowBox[{
             RowBox[{"First", "[", "#", "]"}], ",", 
             RowBox[{"FirstCase", "[", 
              RowBox[{"#", ",", 
               RowBox[{"{", 
                RowBox[{
                 RowBox[{"#", "[", 
                  RowBox[{"[", 
                   RowBox[{"1", ",", "1"}], "]"}], "]"}], ",", 
                 RowBox[{"Except", "[", 
                  RowBox[{"#", "[", 
                   RowBox[{"[", 
                    RowBox[{"1", ",", "2"}], "]"}], "]"}], "]"}], ",",
                  "___"}], "}"}]}], "]"}]}], "}"}]}], "&"}], "[", 
         RowBox[{"SortBy", "[", 
          RowBox[{
           RowBox[{"FindPath", "[", 
            RowBox[{"gx", ",", "i", ",", "j", ",", 
             RowBox[{"{", 
              RowBox[{"1", ",", "10"}], "}"}], ",", "All"}], "]"}], 
           ",", "Size"}], "]"}], "]"}]}], "}"}], ",", " ", 
      RowBox[{"HighlightGraph", "[", 
       RowBox[{
        RowBox[{"HighlightGraph", "[", 
         RowBox[{"gx", ",", "sg"}], "]"}], ",", " ", 
        RowBox[{
         RowBox[{
          RowBox[{"Style", "[", 
           RowBox[{"#", ",", " ", 
            RowBox[{"Thickness", "[", "0.01", "]"}]}], "]"}], "&"}], "/@", 
         RowBox[{"Map", "[", 
          RowBox[{"EdgeList", ",", " ", "sg", ",", " ", 
           RowBox[{"{", "2", "}"}]}], "]"}]}]}], "]"}]}], "]"}]}], 
   "]"}], "]"}]], "Enter"]
}, Open  ]]

So what this implies is that—simply as within the infinite-tape case mentioned above—multiway Turing machines should at all times be causal invariant within the rulial restrict.

So what about “under the rulial restrict”? When is there causal invariance? For s = 1, okay = 1 it’s inevitable:

CyclicTMSTG1

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; Labeled[
 Framed[With[{g = 
     CyclicTMSTG1[[email protected][Subsets[List /@ TMRuleCases[1, 1]]], 1,
       1, 5]}, 
   Graph[g, 
    VertexLabels -> (# -> TMStatePlot[#, ImageSize -> 50] & /@ 
       VertexList[g])]], FrameStyle -> LightGray], 
 TuringMachinePlot[Last[Subsets[List /@ TMRuleCases[1, 1]]], 2, 2, 
  "RulePlot", ImageSize -> 80], Left]

For s = 1, okay = 2 it’s considerably rarer; right here is an instance the place paths can department and never merge:

CyclicTMSTG1

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; With[{ru = {{{1, 1} -> {1, 
       1, -1}}, {{1, 1} -> {1, 0, -1}}, {{1, 0} -> {1, 0, -1}}}}, 
 Labeled[Framed[With[{g = CyclicTMSTG1[[email protected], 1, 2, 3]},
    Module[{out = 
       DirectedEdge[{{1, 2}, {0, 1, 0}}, #] & /@ 
        VertexOutComponent[g, {{1, 2}, {0, 1, 0}}, {1}], 
      sg = With[{sub = VertexOutComponent[g, #]}, 
          If[Length[sub] > 3, 
           EdgeAdd[DirectedGraph[PathGraph[sub], "Acyclic"], 
            DirectedEdge[{{1, 2}, {0, 1, 0}}, sub[[1]]]], 
           Graph[Catenate[{Table[
               DirectedEdge[sub[[n]], sub[[n + 1]]], {n, 
                2}], {DirectedEdge[sub[[3]], sub[[1]]], 
               DirectedEdge[{{1, 2}, {0, 1, 0}}, sub[[1]]]}}]]]] & /@ 
        VertexOutComponent[g, {{1, 2}, {0, 1, 0}}, {1}]}, 
     HighlightGraph[
      HighlightGraph[
       Graph[g, 
        VertexLabels -> (# -> TMStatePlot[#, ImageSize -> 30] & /@ 
           VertexList[g]), 
        EdgeStyle -> 
         Directive[
          ResourceFunction["WolframPhysicsProjectStyleData"][
            "StatesGraph"]["EdgeStyle"], Arrowheads[0.04]]], sg], 
      Fashion[#, Thickness[0.01]] & /@ Append[Map[EdgeList, sg], out]]
     ]], FrameStyle -> LightGray], 
  TuringMachinePlot[ru, 2, 2, "RulePlot", ImageSize -> 120], Left]]

After we mentioned causal invariance (and confluence) within the case of infinite tapes, we did so within the context of ranging from a selected configuration (reminiscent of a clean tape), after which seeing whether or not all paths from this node within the multiway graph finally merge. We are able to do one thing related within the case of finite tapes, say asking about paths ranging from the node akin to a clean tape. Doing this for tapes of sizes between 2 and 4, we get the next outcomes for the variety of s = 1, okay = 2 guidelines (excluding purely deterministic ones) that exhibit confluence as a operate of the variety of instances p within the rule:

Table

&#10005

Cell[CellGroupData[{Cell[BoxData[
 RowBox[{
  RowBox[{
  "CloudGet", "[", 
   "\"\<https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl\>\"", "]"}], ";"}]], "Enter"],

Cell[BoxData[
 RowBox[{"Table", "[", 
  RowBox[{
   RowBox[{"RemoteBatchSubmit", "[", 
    RowBox[{"env", ",", 
     RowBox[{"Monitor", "[", 
      RowBox[{
       RowBox[{"Table", "[", 
        RowBox[{
         RowBox[{"Counts", "[", 
          RowBox[{"ParallelMap", "[", 
           RowBox[{
            RowBox[{
             RowBox[{"CyclicTMCausalInvariantQ", "[", 
              RowBox[{
               RowBox[{"List", "/@", "#"}], ",", 
               RowBox[{"{", 
                RowBox[{"First", "[", 
                 RowBox[{"TMAllStates", "[", 
                  RowBox[{"1", ",", "2", ",", "n"}], "]"}], "]"}], 
                "}"}], ",", 
               RowBox[{"Length", "[", 
                RowBox[{"TMAllStates", "[", 
                 RowBox[{"1", ",", "2", ",", "n"}], "]"}], "]"}]}], 
              "]"}], "&"}], ",", 
            RowBox[{"Select", "[", 
             RowBox[{
              RowBox[{"Subsets", "[", 
               RowBox[{
                RowBox[{"TMRuleCases", "[", 
                 RowBox[{"1", ",", "2"}], "]"}], ",", 
                RowBox[{"{", "p", "}"}]}], "]"}], ",", 
              RowBox[{"Not", "@*", "TestDeterministic"}]}], "]"}]}], 
           "]"}], "]"}], ",", 
         RowBox[{"{", 
          RowBox[{"p", ",", "8"}], "}"}]}], "]"}], ",", "p"}], "]"}], 
     ",", 
     RowBox[{"RemoteProviderSettings", "\[Rule]", 
      RowBox[{"<|", 
       RowBox[{"\"\<VCPUCount\>\"", "\[Rule]", "70"}], "|>"}]}]}], 
    "]"}], ",", 
   RowBox[{"{", 
    RowBox[{"n", ",", "3", ",", "5"}], "}"}]}], "]"}]], "Enter"],

Cell[BoxData[
 RowBox[{
  RowBox[{"data", "=", 
   RowBox[{"{", 
    RowBox[{
     RowBox[{"{", 
      RowBox[{
       RowBox[{"\[LeftAssociation]", "\[RightAssociation]"}], ",", 
       RowBox[{"\[LeftAssociation]", 
        RowBox[{
         RowBox[{"True", "\[Rule]", "8"}], ",", 
         RowBox[{"False", "\[Rule]", "4"}]}], "\[RightAssociation]"}],
        ",", 
       RowBox[{"\[LeftAssociation]", 
        RowBox[{
         RowBox[{"True", "\[Rule]", "52"}], ",", 
         RowBox[{"False", "\[Rule]", "4"}]}], "\[RightAssociation]"}],
        ",", 
       RowBox[{"\[LeftAssociation]", 
        RowBox[{
         RowBox[{"True", "\[Rule]", "69"}], ",", 
         RowBox[{"False", "\[Rule]", "1"}]}], "\[RightAssociation]"}],
        ",", 
       RowBox[{"\[LeftAssociation]", 
        RowBox[{"True", "\[Rule]", "56"}], "\[RightAssociation]"}], 
       ",", 
       RowBox[{"\[LeftAssociation]", 
        RowBox[{"True", "\[Rule]", "28"}], "\[RightAssociation]"}], 
       ",", 
       RowBox[{"\[LeftAssociation]", 
        RowBox[{"True", "\[Rule]", "8"}], "\[RightAssociation]"}], 
       ",", 
       RowBox[{"\[LeftAssociation]", 
        RowBox[{"True", "\[Rule]", "1"}], "\[RightAssociation]"}]}], 
      "}"}], ",", 
     RowBox[{"{", 
      RowBox[{
       RowBox[{"\[LeftAssociation]", "\[RightAssociation]"}], ",", 
       RowBox[{"\[LeftAssociation]", 
        RowBox[{
         RowBox[{"True", "\[Rule]", "7"}], ",", 
         RowBox[{"False", "\[Rule]", "5"}]}], "\[RightAssociation]"}],
        ",", 
       RowBox[{"\[LeftAssociation]", 
        RowBox[{
         RowBox[{"True", "\[Rule]", "42"}], ",", 
         RowBox[{"False", "\[Rule]", "14"}]}], 
        "\[RightAssociation]"}], ",", 
       RowBox[{"\[LeftAssociation]", 
        RowBox[{
         RowBox[{"True", "\[Rule]", "56"}], ",", 
         RowBox[{"False", "\[Rule]", "14"}]}], 
        "\[RightAssociation]"}], ",", 
       RowBox[{"\[LeftAssociation]", 
        RowBox[{
         RowBox[{"True", "\[Rule]", "50"}], ",", 
         RowBox[{"False", "\[Rule]", "6"}]}], "\[RightAssociation]"}],
        ",", 
       RowBox[{"\[LeftAssociation]", 
        RowBox[{
         RowBox[{"True", "\[Rule]", "27"}], ",", 
         RowBox[{"False", "\[Rule]", "1"}]}], "\[RightAssociation]"}],
        ",", 
       RowBox[{"\[LeftAssociation]", 
        RowBox[{"True", "\[Rule]", "8"}], "\[RightAssociation]"}], 
       ",", 
       RowBox[{"\[LeftAssociation]", 
        RowBox[{"True", "\[Rule]", "1"}], "\[RightAssociation]"}]}], 
      "}"}], ",", 
     RowBox[{"{", 
      RowBox[{
       RowBox[{"\[LeftAssociation]", "\[RightAssociation]"}], ",", 
       RowBox[{"\[LeftAssociation]", 
        RowBox[{
         RowBox[{"True", "\[Rule]", "7"}], ",", 
         RowBox[{"False", "\[Rule]", "5"}]}], "\[RightAssociation]"}],
        ",", 
       RowBox[{"\[LeftAssociation]", 
        RowBox[{
         RowBox[{"True", "\[Rule]", "42"}], ",", 
         RowBox[{"False", "\[Rule]", "14"}]}], 
        "\[RightAssociation]"}], ",", 
       RowBox[{"\[LeftAssociation]", 
        RowBox[{
         RowBox[{"True", "\[Rule]", "56"}], ",", 
         RowBox[{"False", "\[Rule]", "14"}]}], 
        "\[RightAssociation]"}], ",", 
       RowBox[{"\[LeftAssociation]", 
        RowBox[{
         RowBox[{"True", "\[Rule]", "50"}], ",", 
         RowBox[{"False", "\[Rule]", "6"}]}], "\[RightAssociation]"}],
        ",", 
       RowBox[{"\[LeftAssociation]", 
        RowBox[{
         RowBox[{"True", "\[Rule]", "27"}], ",", 
         RowBox[{"False", "\[Rule]", "1"}]}], "\[RightAssociation]"}],
        ",", 
       RowBox[{"\[LeftAssociation]", 
        RowBox[{"True", "\[Rule]", "8"}], "\[RightAssociation]"}], 
       ",", 
       RowBox[{"\[LeftAssociation]", 
        RowBox[{"True", "\[Rule]", "1"}], "\[RightAssociation]"}]}], 
      "}"}]}], "}"}]}], ";"}]], "Enter"],

Cell[BoxData[
 RowBox[{"Text", "[", 
  RowBox[{"Grid", "[", 
   RowBox[{
    RowBox[{"Prepend", "[", 
     RowBox[{
      RowBox[{"Prepend", "[", 
       RowBox[{
        RowBox[{"Table", "[", 
         RowBox[{
          RowBox[{"Flatten", "[", 
           RowBox[{"{", 
            RowBox[{"p", ",", 
             RowBox[{"Table", "[", 
              RowBox[{
               RowBox[{"With", "[", 
                RowBox[{
                 RowBox[{"{", 
                  RowBox[{"d", "=", 
                   RowBox[{"data", "[", 
                    RowBox[{"[", 
                    RowBox[{"i", ",", "p"}], "]"}], "]"}]}], "}"}], 
                 ",", 
                 RowBox[{
                  RowBox[{"{", 
                   RowBox[{
                    RowBox[{"d", "[", "False", "]"}], ",", 
                    RowBox[{"d", "[", "True", "]"}], ",", 
                    RowBox[{"PercentForm", "[", 
                    RowBox[{
                    RowBox[{"N", "[", 
                    RowBox[{
                    RowBox[{"d", "[", "True", "]"}], "https://writings.stephenwolfram.com/", 
                    RowBox[{"(", 
                    RowBox[{
                    RowBox[{"d", "[", "False", "]"}], "+", 
                    RowBox[{"d", "[", "True", "]"}]}], ")"}]}], "]"}],
                     ",", "2"}], "]"}]}], "}"}], "/.", 
                  RowBox[{
                   RowBox[{"Missing", "[", "__", "]"}], "\[Rule]", 
                   "0"}]}]}], "]"}], ",", 
               RowBox[{"{", 
                RowBox[{"i", ",", "3"}], "}"}]}], "]"}]}], "}"}], 
           "]"}], ",", 
          RowBox[{"{", 
           RowBox[{"p", ",", "2", ",", "8"}], "}"}]}], "]"}], ",", 
        RowBox[{
         RowBox[{
          RowBox[{"Style", "[", 
           RowBox[{"#", ",", " ", "Italic"}], "]"}], "&"}], "/@", 
         RowBox[{"{", 
          RowBox[{
          "\"\<p\>\"", ",", "\"\<\[Times]\>\"", ",", 
           "\"\<\[Checkmark]\>\"", ",", "\"\<\>\"", ",", " ", 
           "\"\<\[Times]\>\"", ",", "\"\<\[Checkmark]\>\"", ",", 
           "\"\<\>\"", ",", " ", "\"\<\[Times]\>\"", ",", 
           "\"\<\[Checkmark]\>\"", ",", "\"\<\>\""}], "}"}]}]}], 
       "]"}], ",", " ", 
      RowBox[{
       RowBox[{
        RowBox[{"Style", "[", 
         RowBox[{"#", ",", " ", "Italic"}], "]"}], "&"}], "/@", 
       RowBox[{"{", 
        RowBox[{
        "\"\<\>\"", ",", "\"\<\>\"", ",", "\"\<n=2\>\"", ",", 
         "\"\<\>\"", ",", "\"\<\>\"", ",", "\"\<n=3\>\"", ",", 
         "\"\<\>\"", ",", "\"\<\>\"", ",", "\"\<n=4\>\"", ",", 
         "\"\<\>\""}], "}"}]}]}], "]"}], ",", 
    RowBox[{"Frame", "\[Rule]", "All"}], ",", " ", 
    RowBox[{"FrameStyle", " ", "\[Rule]", 
     RowBox[{"GrayLevel", "[", ".7", "]"}]}], ",", " ", 
    RowBox[{"Background", " ", "->", " ", 
     RowBox[{"{", 
      RowBox[{
       RowBox[{"{", 
        RowBox[{"GrayLevel", "[", "0.9", "]"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{
         RowBox[{"GrayLevel", "[", "0.9", "]"}], ",", 
         RowBox[{"GrayLevel", "[", "0.9", "]"}]}], "}"}]}], "}"}]}], 
    ",", " ", 
    RowBox[{"Dividers", " ", "\[Rule]", 
     RowBox[{"{", 
      RowBox[{
       RowBox[{"{", 
        RowBox[{"True", ",", " ", "True", ",", " ", 
         RowBox[{"{", 
          RowBox[{"False", ",", " ", "False", ",", "True"}], "}"}]}], 
        "}"}], ",", " ", "True"}], "}"}]}], ",", " ", 
    RowBox[{"ItemSize", " ", "\[Rule]", " ", 
     RowBox[{"{", 
      RowBox[{"3.25", ",", " ", "Automatic"}], "}"}]}]}], "]"}], 
  "]"}]], "Enter"]
}, Open  ]]

As anticipated, it’s extra frequent to see confluence with shorter tapes, since there may be then much less alternative for branching within the multiway graph. (By the best way, even for arbitrarily giant n, cyclic tapes make extra machines confluent than infinite tapes do, as a result of they permit merging of branches related to the top “going all the best way round”. If as an alternative of cyclic boundary circumstances, one makes use of boundary circumstances that “replicate the top”, fewer machines are confluent.)

With finite tapes, it’s doable to contemplate beginning not simply from a selected preliminary situation, however from all doable preliminary circumstances—resulting in barely fewer guidelines that present “full confluence”:

Table

&#10005

Cell[CellGroupData[{Cell[BoxData[
 RowBox[{
  RowBox[{
  "CloudGet", "[", 
   "\"\<https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl\>\"", "]"}], ";"}]], "Enter"],

Cell[BoxData[
 RowBox[{"Table", "[", 
  RowBox[{
   RowBox[{"RemoteBatchSubmit", "[", 
    RowBox[{"env", ",", 
     RowBox[{"Monitor", "[", 
      RowBox[{
       RowBox[{"Table", "[", 
        RowBox[{
         RowBox[{"Counts", "[", 
          RowBox[{"ParallelMap", "[", 
           RowBox[{
            RowBox[{
             RowBox[{"CyclicTMCausalInvariantQ", "[", 
              RowBox[{
               RowBox[{"List", "/@", "#"}], ",", 
               RowBox[{"TMAllStates", "[", 
                RowBox[{"1", ",", "2", ",", "n"}], "]"}], ",", 
               RowBox[{"Length", "[", 
                RowBox[{"TMAllStates", "[", 
                 RowBox[{"1", ",", "2", ",", "n"}], "]"}], "]"}]}], 
              "]"}], "&"}], ",", 
            RowBox[{"Select", "[", 
             RowBox[{
              RowBox[{"Subsets", "[", 
               RowBox[{
                RowBox[{"TMRuleCases", "[", 
                 RowBox[{"1", ",", "2"}], "]"}], ",", 
                RowBox[{"{", "p", "}"}]}], "]"}], ",", 
              RowBox[{"Not", "@*", "TestDeterministic"}]}], "]"}]}], 
           "]"}], "]"}], ",", 
         RowBox[{"{", 
          RowBox[{"p", ",", "8"}], "}"}]}], "]"}], ",", "p"}], "]"}], 
     ",", 
     RowBox[{"RemoteProviderSettings", "\[Rule]", 
      RowBox[{"<|", 
       RowBox[{"\"\<VCPUCount\>\"", "\[Rule]", "70"}], "|>"}]}]}], 
    "]"}], ",", 
   RowBox[{"{", 
    RowBox[{"n", ",", "3", ",", "5"}], "}"}]}], "]"}]], "Enter"],

Cell[BoxData[
 RowBox[{
  RowBox[{"data", "=", 
   RowBox[{"{", 
    RowBox[{
     RowBox[{"{", 
      RowBox[{
       RowBox[{"\[LeftAssociation]", "\[RightAssociation]"}], ",", 
       RowBox[{"\[LeftAssociation]", 
        RowBox[{
         RowBox[{"False", "\[Rule]", "8"}], ",", 
         RowBox[{"True", "\[Rule]", "4"}]}], "\[RightAssociation]"}], 
       ",", 
       RowBox[{"\[LeftAssociation]", 
        RowBox[{
         RowBox[{"False", "\[Rule]", "16"}], ",", 
         RowBox[{"True", "\[Rule]", "40"}]}], "\[RightAssociation]"}],
        ",", 
       RowBox[{"\[LeftAssociation]", 
        RowBox[{
         RowBox[{"False", "\[Rule]", "14"}], ",", 
         RowBox[{"True", "\[Rule]", "56"}]}], "\[RightAssociation]"}],
        ",", 
       RowBox[{"\[LeftAssociation]", 
        RowBox[{
         RowBox[{"True", "\[Rule]", "50"}], ",", 
         RowBox[{"False", "\[Rule]", "6"}]}], "\[RightAssociation]"}],
        ",", 
       RowBox[{"\[LeftAssociation]", 
        RowBox[{
         RowBox[{"True", "\[Rule]", "27"}], ",", 
         RowBox[{"False", "\[Rule]", "1"}]}], "\[RightAssociation]"}],
        ",", 
       RowBox[{"\[LeftAssociation]", 
        RowBox[{"True", "\[Rule]", "8"}], "\[RightAssociation]"}], 
       ",", 
       RowBox[{"\[LeftAssociation]", 
        RowBox[{"True", "\[Rule]", "1"}], "\[RightAssociation]"}]}], 
      "}"}], ",", 
     RowBox[{"{", 
      RowBox[{
       RowBox[{"\[LeftAssociation]", "\[RightAssociation]"}], ",", 
       RowBox[{"\[LeftAssociation]", 
        RowBox[{"False", "\[Rule]", "12"}], "\[RightAssociation]"}], 
       ",", 
       RowBox[{"\[LeftAssociation]", 
        RowBox[{
         RowBox[{"False", "\[Rule]", "32"}], ",", 
         RowBox[{"True", "\[Rule]", "24"}]}], "\[RightAssociation]"}],
        ",", 
       RowBox[{"\[LeftAssociation]", 
        RowBox[{
         RowBox[{"False", "\[Rule]", "28"}], ",", 
         RowBox[{"True", "\[Rule]", "42"}]}], "\[RightAssociation]"}],
        ",", 
       RowBox[{"\[LeftAssociation]", 
        RowBox[{
         RowBox[{"True", "\[Rule]", "44"}], ",", 
         RowBox[{"False", "\[Rule]", "12"}]}], 
        "\[RightAssociation]"}], ",", 
       RowBox[{"\[LeftAssociation]", 
        RowBox[{
         RowBox[{"True", "\[Rule]", "26"}], ",", 
         RowBox[{"False", "\[Rule]", "2"}]}], "\[RightAssociation]"}],
        ",", 
       RowBox[{"\[LeftAssociation]", 
        RowBox[{"True", "\[Rule]", "8"}], "\[RightAssociation]"}], 
       ",", 
       RowBox[{"\[LeftAssociation]", 
        RowBox[{"True", "\[Rule]", "1"}], "\[RightAssociation]"}]}], 
      "}"}], ",", 
     RowBox[{"{", 
      RowBox[{
       RowBox[{"\[LeftAssociation]", "\[RightAssociation]"}], ",", 
       RowBox[{"\[LeftAssociation]", 
        RowBox[{"False", "\[Rule]", "12"}], "\[RightAssociation]"}], 
       ",", 
       RowBox[{"\[LeftAssociation]", 
        RowBox[{
         RowBox[{"False", "\[Rule]", "36"}], ",", 
         RowBox[{"True", "\[Rule]", "20"}]}], "\[RightAssociation]"}],
        ",", 
       RowBox[{"\[LeftAssociation]", 
        RowBox[{
         RowBox[{"False", "\[Rule]", "30"}], ",", 
         RowBox[{"True", "\[Rule]", "40"}]}], "\[RightAssociation]"}],
        ",", 
       RowBox[{"\[LeftAssociation]", 
        RowBox[{
         RowBox[{"True", "\[Rule]", "44"}], ",", 
         RowBox[{"False", "\[Rule]", "12"}]}], 
        "\[RightAssociation]"}], ",", 
       RowBox[{"\[LeftAssociation]", 
        RowBox[{
         RowBox[{"True", "\[Rule]", "26"}], ",", 
         RowBox[{"False", "\[Rule]", "2"}]}], "\[RightAssociation]"}],
        ",", 
       RowBox[{"\[LeftAssociation]", 
        RowBox[{"True", "\[Rule]", "8"}], "\[RightAssociation]"}], 
       ",", 
       RowBox[{"\[LeftAssociation]", 
        RowBox[{"True", "\[Rule]", "1"}], "\[RightAssociation]"}]}], 
      "}"}]}], "}"}]}], ";"}]], "Enter"],

Cell[BoxData[
 RowBox[{"Text", "[", 
  RowBox[{"Grid", "[", 
   RowBox[{
    RowBox[{"Prepend", "[", 
     RowBox[{
      RowBox[{"Prepend", "[", 
       RowBox[{
        RowBox[{"Table", "[", 
         RowBox[{
          RowBox[{"Flatten", "[", 
           RowBox[{"{", 
            RowBox[{"p", ",", 
             RowBox[{"Table", "[", 
              RowBox[{
               RowBox[{"With", "[", 
                RowBox[{
                 RowBox[{"{", 
                  RowBox[{"d", "=", 
                   RowBox[{"data", "[", 
                    RowBox[{"[", 
                    RowBox[{"i", ",", "p"}], "]"}], "]"}]}], "}"}], 
                 ",", 
                 RowBox[{
                  RowBox[{"{", 
                   RowBox[{
                    RowBox[{"d", "[", "False", "]"}], ",", 
                    RowBox[{"d", "[", "True", "]"}], ",", 
                    RowBox[{"PercentForm", "[", 
                    RowBox[{
                    RowBox[{"N", "[", 
                    RowBox[{
                    RowBox[{"d", "[", "True", "]"}], "https://writings.stephenwolfram.com/", 
                    RowBox[{"(", 
                    RowBox[{
                    RowBox[{"d", "[", "False", "]"}], "+", 
                    RowBox[{"d", "[", "True", "]"}]}], ")"}]}], "]"}],
                     ",", "2"}], "]"}]}], "}"}], "/.", 
                  RowBox[{
                   RowBox[{"Missing", "[", "__", "]"}], "\[Rule]", 
                   "0"}]}]}], "]"}], ",", 
               RowBox[{"{", 
                RowBox[{"i", ",", "3"}], "}"}]}], "]"}]}], "}"}], 
           "]"}], ",", 
          RowBox[{"{", 
           RowBox[{"p", ",", "2", ",", "8"}], "}"}]}], "]"}], ",", 
        RowBox[{
         RowBox[{
          RowBox[{"Style", "[", 
           RowBox[{"#", ",", " ", "Italic"}], "]"}], "&"}], "/@", 
         RowBox[{"{", 
          RowBox[{
          "\"\<p\>\"", ",", "\"\<\[Times]\>\"", ",", 
           "\"\<\[Checkmark]\>\"", ",", "\"\<\>\"", ",", " ", 
           "\"\<\[Times]\>\"", ",", "\"\<\[Checkmark]\>\"", ",", 
           "\"\<\>\"", ",", " ", "\"\<\[Times]\>\"", ",", 
           "\"\<\[Checkmark]\>\"", ",", "\"\<\>\""}], "}"}]}]}], 
       "]"}], ",", " ", 
      RowBox[{
       RowBox[{
        RowBox[{"Style", "[", 
         RowBox[{"#", ",", " ", "Italic"}], "]"}], "&"}], "/@", 
       RowBox[{"{", 
        RowBox[{
        "\"\<\>\"", ",", "\"\<\>\"", ",", "\"\<n=2\>\"", ",", 
         "\"\<\>\"", ",", "\"\<\>\"", ",", "\"\<n=3\>\"", ",", 
         "\"\<\>\"", ",", "\"\<\>\"", ",", "\"\<n=4\>\"", ",", 
         "\"\<\>\""}], "}"}]}]}], "]"}], ",", 
    RowBox[{"Frame", "\[Rule]", "All"}], ",", " ", 
    RowBox[{"FrameStyle", " ", "\[Rule]", 
     RowBox[{"GrayLevel", "[", ".7", "]"}]}], ",", " ", 
    RowBox[{"Background", " ", "->", " ", 
     RowBox[{"{", 
      RowBox[{
       RowBox[{"{", 
        RowBox[{"GrayLevel", "[", "0.9", "]"}], "}"}], ",", 
       RowBox[{"{", 
        RowBox[{
         RowBox[{"GrayLevel", "[", "0.9", "]"}], ",", 
         RowBox[{"GrayLevel", "[", "0.9", "]"}]}], "}"}]}], "}"}]}], 
    ",", " ", 
    RowBox[{"Dividers", " ", "\[Rule]", 
     RowBox[{"{", 
      RowBox[{
       RowBox[{"{", 
        RowBox[{"True", ",", " ", "True", ",", " ", 
         RowBox[{"{", 
          RowBox[{"False", ",", " ", "False", ",", "True"}], "}"}]}], 
        "}"}], ",", " ", "True"}], "}"}]}], ",", 
    RowBox[{"ItemSize", " ", "\[Rule]", " ", 
     RowBox[{"{", 
      RowBox[{"3.25", ",", " ", "Automatic"}], "}"}]}]}], "]"}], 
  "]"}]], "Enter"]
}, Open  ]]

Listed here are examples of multiway graphs for guidelines that present full confluence

CyclicTMSTG1

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; 
Framed[Graph[CyclicTMSTG1[[email protected]#, 1, 2, 4], ImageSize -> {80, 80}],
    FrameStyle -> 
    LightGray] & /@ {{{1, 1} -> {1, 1, -1}, {1, 1} -> {1, 0, 1}, {1, 
     0} -> {1, 1, 1}}, {{1, 1} -> {1, 1, -1}, {1, 0} -> {1, 
     1, -1}, {1, 0} -> {1, 0, -1}}, {{1, 1} -> {1, 1, -1}, {1, 
     1} -> {1, 0, -1}, {1, 1} -> {1, 1, 1}, {1, 0} -> {1, 
     1, -1}}, {{1, 1} -> {1, 1, -1}, {1, 1} -> {1, 0, 1}, {1, 
     0} -> {1, 1, -1}, {1, 0} -> {1, 0, -1}}, {{1, 1} -> {1, 
     1, -1}, {1, 1} -> {1, 0, 1}, {1, 0} -> {1, 0, -1}, {1, 0} -> {1, 
     1, 1}}, {{1, 1} -> {1, 1, -1}, {1, 1} -> {1, 0, -1}, {1, 
     1} -> {1, 0, 1}, {1, 0} -> {1, 1, -1}, {1, 0} -> {1, 1, 1}, {1, 
     0} -> {1, 0, 1}}}

and ones that don’t:

CyclicTMSTG1

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"]; 
Framed[Graph[CyclicTMSTG1[[email protected]#, 1, 2, 4], ImageSize -> {80, 80}],
    FrameStyle -> 
    LightGray] & /@ {{{1, 0} -> {1, 1, -1}, {1, 0} -> {1, 
     0, -1}}, {{1, 1} -> {1, 1, -1}, {1, 1} -> {1, 0, -1}, {1, 
     1} -> {1, 1, 1}}, {{1, 1} -> {1, 1, -1}, {1, 0} -> {1, 1, 1}, {1,
      0} -> {1, 0, 1}}, {{1, 1} -> {1, 1, -1}, {1, 1} -> {1, 
     0, -1}, {1, 0} -> {1, 0, -1}, {1, 0} -> {1, 0, 1}}, {{1, 
     1} -> {1, 1, -1}, {1, 0} -> {1, 1, -1}, {1, 0} -> {1, 0, -1}, {1,
      0} -> {1, 0, 1}}, {{1, 1} -> {1, 0, -1}, {1, 1} -> {1, 0, 
     1}, {1, 0} -> {1, 0, -1}, {1, 0} -> {1, 0, 1}}}

Usually non-confluent instances look extra “tree like” whereas confluent ones look extra “cyclic”. However typically the general kinds will be very related, with the one important distinction being the directionality of edges. (Notice that if a multiway graph is Hamiltonian, then it inevitably corresponds to a system that reveals confluence.)

Notes

What I name multiway Turing machines are definitionally the identical as what are often known as nondeterministic Turing machines (NDTMs) within the concept of computation literature. I take advantage of “multiway” moderately than “nondeterministic”, nonetheless, to point that my curiosity is in the entire multiway graph of doable evolutions, moderately than in whether or not a selected consequence can “nondeterministically” be reached.

The thought of nondeterminism appears to have subtle fairly regularly into the idea of computation, with the precise idea of nondeterministic Turing machines rising round 1970, and promptly getting used to formulate the category of NP computations. The unique Turing machines from 1936 have been purely deterministic. Nonetheless, though they weren’t but nicely understood, combinators launched in 1920 already concerned what we now consider as nondeterministic reductions, as did lambda calculus.

Many mathematical issues are of the shape “Does there exist a ___ that does ___?”, and the idea of wanting “nondeterministically” for a selected resolution has arisen many occasions. In a particularly computational context it appears to have been emphasised when formal grammars became established in 1956, and it was frequent to ask whether or not a selected string was in a given formal language, within the sense that some parse tree (or equal) could possibly be discovered for it. Nondeterministic finite automata appear to have first been explicitly mentioned in 1959, and varied different types of nondeterministic language descriptions appeared in the middle of the Sixties.

Within the early Eighties, quantum generalizations of Turing machines started to be thought-about (and I in reality studied them just a little at the moment). The apparent fundamental setup was structurally the identical as for nondeterministic Turing machines (and now for multiway Turing machines), besides that within the quantum case totally different “nondeterministic states” have been recognized as quantum states, assigned quantum amplitudes, and seen as being mixed in superpositions. (There was additionally important complexity in imagining a bodily implementation, with an precise Hamiltonian, and so on.)

Turing machines are most frequently used as theoretical constructs, moderately than being investigated on the stage of particular easy guidelines. However whereas some work on particular odd Turing machines has been achieved (for example by me), virtually nothing appears to have been achieved on particular nondeterministic (i.e. multiway) Turing machines.

The truth that two head states are adequate for universality in odd Turing machines was established by Claude Shannon in 1956 (and we now know that s = 2, okay = 3 is adequate), however I do know of no related outcomes for nondeterministic Turing machines.

Notice that in my formulation of multiway Turing machines halting happens simply because there are not any guidelines that apply. Following Alan Turing, most therapies of Turing machines introduce an specific particular “halt” state—however in my formulation this isn’t wanted.

I’ve thought-about solely Turing machines with single heads. If a number of heads are launched in odd Turing machines (or mobile automata) there sometimes must be particular guidelines added to outline how they need to work together. However with my formulation of multiway Turing machines, there is no such thing as a have to specify this; heads that may “collide in house” simply find yourself at totally different locations in branchial house.

A fundamental multiway generalization of the TuringMachine operate in Wolfram Language is (be aware that the specification of configurations is barely totally different from what is used in A New Kind of Science):

MWTMEvolveList

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"];
MWTMEvolveList[rule_, inits : {{{_, _}, _} ...}, t_Integer] := 
 NestList[Union[#, Catenate[Map[MWTMStep[rule, #] &, #]]] &, inits, t]
MWTMStep

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"];
MWTMStep[rule_List, {{s_, i_}, a_}] /; 1 <= i <= Size[a] := 
 Apply[{{#1, i + #3}, ReplacePart[a, i -> #2]} &, 
  ReplaceList[{s, a[[i]]}, rule], {1}]

Operating this for two steps from a clean tape offers:

MWTMEvolveList

&#10005

CloudGet["https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl"];
MWTMEvolveList[{{1, 1} -> {1, 0, -1}, {1, 0} -> {1, 0, -1}, {1, 
    0} -> {1, 1, 1}}, {{{1, 3}, {0, 0, 0, 0, 0}}}, 2]

The variety of distinct states will increase as:

Length /@ %

This creates a multiway graph for the evolution:

NestGraph

&#10005

Cell[CellGroupData[{Cell[BoxData[
 RowBox[{
  RowBox[{
  "CloudGet", "[", 
   "\"\<https://www.wolframcloud.com/obj/sw-blog/\
MultiwayTuringMachines/Programs-01.wl\>\"", "]"}], ";"}]], "Enter"],

Cell[BoxData[
 RowBox[{
  RowBox[{"MWTMStep", "[", 
   RowBox[{"rule_List", ",", 
    RowBox[{"h_", "[", 
     RowBox[{
      RowBox[{"{", 
       RowBox[{"s_", ",", "n_"}], "}"}], ",", "a_"}], "]"}]}], "]"}], 
  ":=", "\[IndentingNewLine]", 
  RowBox[{"With", "[", 
   RowBox[{
    RowBox[{"{", 
     RowBox[{"nn", " ", "=", " ", 
      RowBox[{"Mod", "[", 
       RowBox[{"n", ",", " ", 
        RowBox[{"Length", "[", "a", "]"}], ",", " ", "1"}], "]"}]}], 
     "}"}], ",", "\[IndentingNewLine]", 
    RowBox[{"h", "@@@", 
     RowBox[{"Apply", "[", 
      RowBox[{
       RowBox[{
        RowBox[{"{", 
         RowBox[{
          RowBox[{"{", 
           RowBox[{"#1", ",", 
            RowBox[{"Mod", "[", 
             RowBox[{
              RowBox[{"nn", "+", "#3"}], ",", " ", 
              RowBox[{"Length", "[", "a", "]"}], ",", " ", "1"}], 
             "]"}]}], "}"}], ",", 
          RowBox[{"ReplacePart", "[", 
           RowBox[{"a", ",", 
            RowBox[{"nn", "\[Rule]", "#2"}]}], "]"}]}], "}"}], "&"}], 
       ",", 
       RowBox[{"ReplaceList", "[", 
        RowBox[{
         RowBox[{"{", 
          RowBox[{"s", ",", 
           RowBox[{"a", "[", 
            RowBox[{"[", "nn", "]"}], "]"}]}], "}"}], ",", "rule"}], 
        "]"}], ",", 
       RowBox[{"{", "1", "}"}]}], "]"}]}]}], "]"}]}]], "Enter"],

Cell[BoxData[
 RowBox[{"NestGraph", "[", 
  RowBox[{
   RowBox[{
    RowBox[{"MWTMStep", "[", 
     RowBox[{
      RowBox[{"{", 
       RowBox[{
        RowBox[{
         RowBox[{"{", 
          RowBox[{"1", ",", "1"}], "}"}], "\[Rule]", 
         RowBox[{"{", 
          RowBox[{"1", ",", "0", ",", 
           RowBox[{"-", "1"}]}], "}"}]}], ",", 
        RowBox[{
         RowBox[{"{", 
          RowBox[{"1", ",", "0"}], "}"}], "\[Rule]", 
         RowBox[{"{", 
          RowBox[{"1", ",", "0", ",", 
           RowBox[{"-", "1"}]}], "}"}]}], ",", 
        RowBox[{
         RowBox[{"{", 
          RowBox[{"1", ",", "0"}], "}"}], "\[Rule]", 
         RowBox[{"{", 
          RowBox[{"1", ",", "1", ",", "1"}], "}"}]}]}], "}"}], ",", 
      "#"}], "]"}], "&"}], ",", 
   RowBox[{"Graph", "[", 
    RowBox[{
     RowBox[{"{", 
      RowBox[{"h", "[", 
       RowBox[{
        RowBox[{"{", 
         RowBox[{"1", ",", "3"}], "}"}], ",", 
        RowBox[{"{", 
         RowBox[{"0", ",", "0", ",", "0", ",", "0", ",", "0"}], 
         "}"}]}], "]"}], "}"}], ",", 
     RowBox[{"{", "}"}]}], "]"}], ",", "4", ",", 
   RowBox[{"VertexLabels", "\[Rule]", "None"}]}], "]"}]], "Enter"]
}, Open  ]]

Leave a Reply

Your email address will not be published.