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,VertexSize1.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[]=

Add
,
Add
,
Add
,
Add
,
Add
,
Add
,
Add
,
Add
,
Add
,
Add
,
Add
,
Add
,
Add
,
Add
,
Add
,
Add
,
Add
,
Add
,
Add
,
Add

Clear
Copy
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"]],AspectRatio1/2]
Out[]=

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"]]
Out[]=

2 rule cases

Is it obvious that these cannot merge?

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-state NDTMs (2 colors)

These have rendering bugs:

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

Different Cases

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

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]

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

(This is a result from Knuth-Bendix-ology ; algebraic analogs ??)

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