In[]:=
ResourceFunction["TuringMachineFromNumber"][2506]
Out[]=
{{1,1}{2,0,-1},{1,0}{2,1,1},{2,1}{1,0,1},{2,0}{1,1,-1}}
Max’s magic TM rule code:
In[]:=
NKSSpecialFunctions`RulePlot`Dump`ValidTuringMachineRulesQ;PrependTo[DownValues[NKSSpecialFunctions`RulePlot`Dump`ValidTuringMachineRulesQ],HoldPattern[NKSSpecialFunctions`RulePlot`Dump`ValidTuringMachineRulesQ[args___]]True];
In[]:=
rulecases=Flatten[Table[{s0,c0}{s1,c1,d},{s0,1,2},{s1,1,2},{c0,0,1},{c1,0,1},{d,{-1,1}}],4]
Out[]=
{{1,0}{1,0,-1},{1,0}{1,0,1},{1,0}{1,1,-1},{1,0}{1,1,1},{1,1}{1,0,-1},{1,1}{1,0,1},{1,1}{1,1,-1},{1,1}{1,1,1},{1,0}{2,0,-1},{1,0}{2,0,1},{1,0}{2,1,-1},{1,0}{2,1,1},{1,1}{2,0,-1},{1,1}{2,0,1},{1,1}{2,1,-1},{1,1}{2,1,1},{2,0}{1,0,-1},{2,0}{1,0,1},{2,0}{1,1,-1},{2,0}{1,1,1},{2,1}{1,0,-1},{2,1}{1,0,1},{2,1}{1,1,-1},{2,1}{1,1,1},{2,0}{2,0,-1},{2,0}{2,0,1},{2,0}{2,1,-1},{2,0}{2,1,1},{2,1}{2,0,-1},{2,1}{2,0,1},{2,1}{2,1,-1},{2,1}{2,1,1}}
In[]:=
RulePlot[TuringMachine[{{2,0}{1,0,1},{2,1}{1,1,-1}}]]
Out[]=
In[]:=
With[{t=3},Show[ResourceFunction["MultiwayTuringMachine"][{{{1,0}{1,0,1}},{{2,1}{1,1,-1}}},{{1,t+1,0},Table[0,2t+1]},t,"StatesGraph","IncludeEventInstances"True,VertexSize1.1{1,1.1/(2t+1)}]]]
Out[]=
In[]:=
Length[%4]
Out[]=
32
In[]:=
List/@RandomSample[rulecases,5]
Out[]=
{{{2,1}{2,1,1}},{{1,1}{2,1,1}},{{1,1}{1,1,-1}},{{2,1}{1,1,1}},{{1,1}{2,0,-1}}}
In[]:=
With[{t=4},Show[ResourceFunction["MultiwayTuringMachine"][%,{{1,t+1,0},Table[0,2t+1]},t,"StatesGraphStructure"]]]
Out[]=
In[]:=
ResourceFunction["InteractiveListSelector"][With[{t=5},ResourceFunction["MultiwayTuringMachine"][#,{{1,t+1,0},Table[0,2t+1]},t,"StatesGraphStructure"]]#&/@Table[List/@RandomSample[rulecases,5],20]]
Out[]=
In[]:=
LayeredGraphPlot[With[{t=12},ResourceFunction["MultiwayTuringMachine"][{{{2,1}{1,0,1}},{{1,0}{2,0,-1}},{{1,0}{2,0,1}},{{1,0}{1,0,1}},{{2,0}{2,1,-1}}},{{1,t+1,0},Table[0,2t+1]},t,"StatesGraphStructure"]],AspectRatio1/2]
Out[]=
Minimal cases
Minimal cases
In[]:=
With[{t=5},ResourceFunction["MultiwayTuringMachine"][{{{1,0}{1,0,-1}},{{1,0}{1,0,1}}},{{1,t+1,0},Table[0,2t+1]},t,"StatesGraphStructure"]]
Out[]=
In this case, it can terminate at each step, by going to the right, and writing a 1:
In[]:=
With[{t=5},ResourceFunction["MultiwayTuringMachine"][{{{1,0}{1,0,-1}},{{1,0}{1,1,1}}},{{1,t+1,0},Table[0,2t+1]},t,"StatesGraphStructure"]]
2 rule cases
2 rule cases
Is it obvious that these cannot merge?
3-rule s=2,k=2 case
3-rule s=2,k=2 case
First two rules only:
Mostly this just goes to the left or right, with a small amount of indecision at the beginning
Out[]=
{{{1, 0} -> {1, 0, 1}}, {{1, 0} -> {1, 1, -1}}, {{1, 1} -> {1, 0, -1}}}
{{{1, 0} -> {1, 0, 1}}, {{1, 0} -> {1, 1, -1}}, {{1, 1} -> {1, 0, -1}}}
1-state NDTMs (2 colors)
1-state NDTMs (2 colors)
These have rendering bugs:
1-state 1-color
1-state 1-color
2-states 1-color
2-states 1-color
Causal connections are made depending both on tape state, and head state [ NKS uses only tape state ]
All blank because this is a 1-color TM:
4-rule s=2,k=2 case
4-rule s=2,k=2 case
Different Cases
Altogether there are 2^32 possible “2,2 subset” NDTMs
Altogether there are 2^32 possible “2,2 subset” NDTMs
These correspond to allowing between 0 and 8 RHSs for any of the 4 possible LHSs
QTMs
QTMs
Given a foliation / evolution slice ; look at the path weights : they define elements of a vector
The transition “matrix” maps from the sequence of weights at one slice to another slice [assuming that every state is represented, albeit with weight 0, in each slice]
The transition “matrix” maps from the sequence of weights at one slice to another slice [assuming that every state is represented, albeit with weight 0, in each slice]
Quantum measurement
Quantum measurement
In the Jonathan interpretation: you are getting a definite output by doing “whole state” completions
Alternatively an analyzer on the multiway graph, that finds a normalizing path (or some feature that is “the answer”)
If you do enough completions, you reduce the transition function to a deterministic function
If you do enough completions, you reduce the transition function to a deterministic function
(This is a result from Knuth-Bendix-ology ; algebraic analogs ??)
Criterion for the analyzer not to be where the computation is really happening [?]
Criterion for the analyzer not to be where the computation is really happening [?]
“Information theoretically” we can look at the redundancy of the state distribution in branchial space
“Information theoretically” we can look at the redundancy of the state distribution in branchial space