You are using a browser not supported by the Wolfram Cloud
Supported browsers include recent versions of Chrome, Edge, Firefox and Safari.
I understand and wish to continue anyway »
WOLFRAM NOTEBOOK
[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: