[Assume infinite tape]

From each node in the rulial multiway system, there are always (# offsets) * s * k

[Actually doesn’t care about the current state]

[Actually doesn’t care about the current state]

# nodes in graph = # configurations reachable after t steps

k^(2t+1)*s

#### Full graph

Full graph

In[]:=

With[{g=With[{t=4},MultiwayTuringMachine[AllDeltaTMRules[{1,2}],{{1,t+1,0},ReplacePart[Table[0,2t+1],51]},t,"StatesGraph","IncludeEventInstances"False,PerformanceGoal"Quality",VertexSize1{1,1/(2t+1)}]]},NeighborhoodGraph[g,First[VertexList[g]],1,VertexCoordinatesNone]]

Out[]=

In[]:=

With[{g=With[{t=4},MultiwayTuringMachine[AllDeltaTMRules[{1,2}],{{1,t+1,0},ReplacePart[Table[0,2t+1],41]},t,"StatesGraph","IncludeEventInstances"False,PerformanceGoal"Quality",VertexSize1{1,1/(2t+1)}]]},NeighborhoodGraph[g,First[VertexList[g]],1,VertexCoordinatesNone]]

Out[]=

Geodesic ball: set of states reachable by an extreme-ND TM

In[]:=

With[{g=With[{t=4},MultiwayTuringMachine[AllDeltaTMRules[{1,2}],{{1,t+1,0},Table[0,2t+1]},t,"StatesGraph","IncludeEventInstances"False,PerformanceGoal"Quality",VertexSize1{1,1/(2t+1)}]]},NeighborhoodGraph[g,First[VertexList[g]],2,VertexCoordinatesNone]]

Out[]=

In[]:=

With[{g=With[{t=6},MultiwayTuringMachine[AllDeltaTMRules[{1,2}],{{1,t+1,0},Table[0,2t+1]},t,"StatesGraphStructure","IncludeEventInstances"False,PerformanceGoal"Quality"]]},NeighborhoodGraph[g,First[VertexList[g]],2,VertexCoordinatesNone]]

Out[]=

In[]:=

SimpleGraph[UndirectedGraph[%252]]

Out[]=

In[]:=

PlanarGraphQ[%]

Out[]=

True

In[]:=

PlanarGraph

Out[]=

In[]:=

g4=With[{t=4},MultiwayTuringMachine[AllDeltaTMRules[{1,2}],{{1,t+1,0},Table[0,2t+1]},t,"StatesGraph",PerformanceGoal"Quality",VertexSize1{1,1/(2t+1)}]]

Out[]=

#### There is a cycle of length 4 involved in returning the head to its original position, with the original color

There is a cycle of length 4 involved in returning the head to its original position, with the original color

If head is allowed to stay stationary, then the cycle length is 3.

#### Two-way edges correspond to the head moving one way and back, both times writing onto the tape the color that was already there.

Two-way edges correspond to the head moving one way and back, both times writing onto the tape the color that was already there.

From a given tape state, we can move to the states with the head on either side, and the tape with one square different.

Eventually we get an infinite dimensional hypercube, with every node representing a complete tape state, joined by an edge corresponding to reversing the ith square on the tape.

## Finite tapes

Finite tapes

Cyclic tape: