NDTM

Underlying states (“machine configurations”) [ quantum eigenstates in ~ computational basis ]

Combined states [ AKA superposition states ]

Evolution of NDTM (MWTM / QTM) is from one branchlike hypersurface to the “next”

​
In[]:=
CloudGet["https://www.wolframcloud.com/obj/sw-blog/MultiwayTuringMachines/Programs-01.wl"];Table[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,2t+1]},t,"BranchialGraphStructure",ImageSize{Automatic,120}],FrameStyleLightGray],{t,1,4}]
Out[]=

,
,
,

In[]:=
With[{t=2},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,2t+1]},t,"StatesGraph",GraphLayout->"LayeredDigraphEmbedding",VertexSize2,AspectRatio1/2]]
Out[]=
In[]:=
Table[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,2t+1]},t,"BranchialGraph",VertexSize2,ImageSize{Automatic,120}],FrameStyleLightGray],{t,1,2}]
Out[]=

,

In[]:=
Table[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,2t+1]},t,"EvolutionBranchialGraph",VertexSize2,ImageSize{Automatic,120}],FrameStyleLightGray],{t,1,2}]
Out[]=

,


What is the evolution of one branchial graph to the next?

Superbranchial graph

In[]:=
ResourceFunction["MultiwaySystem"][{"A""BA","B""AB"},"AB",3,"EvolutionEventsGraph"]
Out[]=
The purple lines could be directed: they say that a given token has a given event as an ancestor
The orange lines are undirected, and represent branch pairs for events that have causal ancestors in common (i.e. they are both part of some light cone)

What is the merging criterion for a multiway system?

The states information is merely a shadow of the evolution .... [i.e. the food/resources for the evolution, not how it is configured]
(Just as the branchial graph is also merely a shadow)

New Type of Branchial Graph [ Superbranchial graph ]

Two kinds of edges: common state ancestors ; common event ancestors

Common event ancestors: spacelike separation [ following a path along spacelike edges, we can reconstruct a global state ]
Common state ancestor: branchlike separation : every pair allow us to reconstruct a branch pair

In local multiway systems: we break into tokens.

In WM, every token is a relation (i.e. a list of elements [AKA “atoms of space”)]
[[ In this view, a MWTM is a collection of relations, between tape coordinate positions, tape configurations, head positions, head states ... ; rule-based constraints: only one head in a given spacelike configuration ]]

Wolfram Model Analog

Branchial Multiway System

Nodes: branchial graphs

Edges: possible successor branchial graphs

Region in Branchial Space for an NP Problem?

Causal vs. chronological relation between events
(Light-like separated) Horismos = light cone related = i.e. single path
Chronological = inside the light cone = i.e. multiple causally consistent paths
polynomial time transformation: moving from one causally consistent path to another (“by webbing”) [conformal transformations]
NP hardness: there is no P transformation to a P problem : i.e. there is no homotopic transformation
P transformation “geometrically” will be replacing one sets of edges by another boundedly different in size set of edges

What the model-theoretic version of computational complexity theory?

Claim: the metalogic is the underlying TM; the particular type of problem (e.g. TSP) corresponds to a particular model wrt that TM
Specializing to a particular concrete problem as opposed to a complexity class

What is the analog of an inertial frame in computational complexity theory