## NDTM

NDTM

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

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

#### Combined states [ AKA superposition states ]

Combined states [ AKA superposition states ]

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

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}],FrameStyleLightGray],{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",VertexSize2,AspectRatio1/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",VertexSize2,ImageSize{Automatic,120}],FrameStyleLightGray],{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",VertexSize2,ImageSize{Automatic,120}],FrameStyleLightGray],{t,1,2}]

Out[]=

,

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

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

### Superbranchial graph

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)

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?

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 ]

New Type of Branchial Graph [ Superbranchial graph ]

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

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 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

Wolfram Model Analog

## Branchial Multiway System

Branchial Multiway System

#### Nodes: branchial graphs

Nodes: branchial graphs

#### Edges: possible successor branchial graphs

Edges: possible successor branchial graphs

## Region in Branchial Space for an NP Problem?

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

(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

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?

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

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