While Turing Machines run on arrays, I thought it would be interesting to extend Turing Machine evolution to a graph-based structure using principles of multiway computation.
An example Turing Machine:
In[]:=
RulePlot[TuringMachine[{{1,1}->{2,0,1},{1,0}->{3,1,-1},{2,1}->{3,1,1},{2,0}->{1,1,1},{3,1}->{1,0,-1},{3,0}->{2,1,1}}]]
Out[]=
In[]:=
RulePlot[TuringMachine[{{1,1}->{2,0,1},{1,0}->{3,1,-1},{2,1}->{3,1,1},{2,0}->{1,1,1},{3,1}->{1,0,-1},{3,0}->{2,1,1}}],{{1,5},ConstantArray[0,15]},30,Mesh->True,Frame->None]
Out[]=
Directed edges are locally similar to tapes, so the Turing Machine can be extended by running it along each valid edge. The direction specifies whether the Turing Machine is moving left or right, so in one case the Turing Machine will move along the adjacent edge, and in the other case it will move against the adjacent edge.
In[]:=
turingMachineGraph[rule_,graph_,state_,depth_]:=NestGraph[turingMachineGraphStep[rule,graph,#]&,{state},depth]
In[]:=
turingMachineGraphStep[rule_,graph_,state_]:=With[{action=Association[rule][{state[[1,1]],state[[2,state[[1,2]]]]}]},Map[{{action[[1]],#},ReplacePart[state[[2]],state[[1,2]]->action[[2]]]}&,If[action[[3]]==1,EdgeList[graph,state[[1,2]]_][[All,2]],EdgeList[graph,_state[[1,2]]][[All,1]]]]]
In[]:=
exampleGraph=
Out[]=
In[]:=
EdgeList[exampleGraph]
Out[]=
{19,28,41,51,67,71,72,81,93,95,108}
A single evolution step on the graph:
In[]:=
turingMachineGraphStep[{{1,1}->{2,0,1},{1,0}->{3,1,-1},{2,1}->{3,1,1},{2,0}->{1,1,1},{3,1}->{1,0,-1},{3,0}->{2,1,1}},exampleGraph,{{1,1},ConstantArray[0,VertexCount[exampleGraph](*Arrayshouldbethesamesizeasthegraph*)]}]
Out[]=
{{{3,4},{1,0,0,0,0,0,0,0,0,0}},{{3,5},{1,0,0,0,0,0,0,0,0,0}},{{3,7},{1,0,0,0,0,0,0,0,0,0}},{{3,8},{1,0,0,0,0,0,0,0,0,0}}}
Repeated steps with NestGraph:
turingMachineGraph[{{1,1}->{2,0,1},{1,0}->{3,1,-1},{2,1}->{3,1,1},{2,0}->{1,1,1},{3,1}->{1,0,-1},{3,0}->{2,1,1}},exampleGraph,{{1,1},ConstantArray[0,VertexCount[exampleGraph]]},3]
Out[]=
turingMachineGraph[{{1,1}->{2,0,1},{1,0}->{3,1,-1},{2,1}->{3,1,1},{2,0}->{1,1,1},{3,1}->{1,0,-1},{3,0}->{2,1,1}},exampleGraph,{{1,1},ConstantArray[0,VertexCount[exampleGraph]]},7]
Out[]=
turingMachineGraph[{{1,1}->{2,0,1},{1,0}->{3,1,-1},{2,1}->{3,1,1},{2,0}->{1,1,1},{3,1}->{1,0,-1},{3,0}->{2,1,1}},exampleGraph,{{1,1},ConstantArray[0,VertexCount[exampleGraph]]},20]
Out[]=
In[]:=
turingMachineGraphTooltipped[rule_,graph_,state_,depth_]:=With[{multiwayEvolution=turingMachineGraph[rule,graph,state,depth]},Graph[multiwayEvolution,VertexLabels->Map[#->Placed[turingMachineGraphStepPlot[rule,graph,#],Tooltip]&,VertexList[multiwayEvolution]]]]
In[]:=
turingMachineGraphPlot[rule_,graph_,state_,depth_]:=With[{multiwayEvolution=turingMachineGraph[rule,graph,state,depth]},Graph[multiwayEvolution,VertexShapeFunction->(Inset[Framed[Show[turingMachineGraphStepPlotSmall[rule,graph,#2]]],#1,Center,2*#3]&),VertexSize->0.5,ImageSize->Large]]
In[]:=
turingMachineGraphStepPlot[rule_,graph_,state_]:=Graph[graph,VertexShapeFunction->(Inset[If[state[[1,2]]==#2,RulePlot[TuringMachine[rule],{state[[1,1]],{state[[2,#2]]}},0,Mesh->True,Frame->None],If[state[[2,#2]]==0,Graphics[{EdgeForm[GrayLevel[-1+GoldenRatio]],FaceForm[GrayLevel[1]],Rectangle[]}],Graphics[{EdgeForm[GrayLevel[-1+GoldenRatio]],FaceForm[RGBColor[0.971,0.6765,0.09]],Rectangle[]}]]],#1,Center,2*#3]&),VertexSize->0.5]
In[]:=
turingMachineGraphStepPlotSmall[rule_,graph_,state_]:=Graph[graph,VertexShapeFunction->(Inset[If[state[[1,2]]==#2,RulePlot[TuringMachine[rule],{state[[1,1]],{state[[2,#2]]}},0,Mesh->True,Frame->None],If[state[[2,#2]]==0,Graphics[{EdgeForm[GrayLevel[-1+GoldenRatio]],FaceForm[GrayLevel[1]],Rectangle[]}],Graphics[{EdgeForm[GrayLevel[-1+GoldenRatio]],FaceForm[RGBColor[0.971,0.6765,0.09]],Rectangle[]}]]],#1,Center,2*#3]&),VertexSize->0.5,EdgeShapeFunction->{{"Arrow","ArrowSize"->0.1}}]
Stylized plots of a single step:
In[]:=
Map[turingMachineGraphStepPlot[{{1,1}->{2,0,1},{1,0}->{3,1,-1},{2,1}->{3,1,1},{2,0}->{1,1,1},{3,1}->{1,0,-1},{3,0}->{2,1,1}},exampleGraph,#]&,turingMachineGraphStep[{{1,1}->{2,0,1},{1,0}->{3,1,-1},{2,1}->{3,1,1},{2,0}->{1,1,1},{3,1}->{1,0,-1},{3,0}->{2,1,1}},exampleGraph,{{1,1},ConstantArray[0,VertexCount[exampleGraph](*Arrayshouldbethesamesizeasthegraph*)]}]]
The multiway graph with individual Turing Machine steps displayed as a tooltip:
The multiway graph with individual Turing Machine states displayed as the vertices of the graph:
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
Turing machine evolution on graphs using principles of multiway computation
by Joseph Stocke
Wolfram Community, STAFF PICKS, June 28, 2023
https://community.wolfram.com/groups/-/m/t/2946777
by Joseph Stocke
Wolfram Community, STAFF PICKS, June 28, 2023
https://community.wolfram.com/groups/-/m/t/2946777