Multiway TMs


Approach [“An Empirical Approach to the P vs. NP Problem”]

Enumerate MWTMs and see what functions they compute.
[? Look for nonblank final tapes. What to do about nonhalting cases? Just put a time bound.....]
Enumerate deterministic TMs. What functions do they compute?
Characterize computed functions by constructing vectors of results for each input... [and also recording halting time]
Enumerate possible functions .... see how long it takes an NDTM and a DTM to compute them....
? Have different outcomes represented by different halt states ?
For DTMs: generate a vector of outcomes, and times.
For NDTMs: same idea but just look for a True outcome

Alternative formulation

Compute outputs starting from blank tapes ... in ruliad with TM basis
[This assumes arbitrary algorithmic complexity]

Vs. algorithmic complexity

Running

In[]:=
TMStep[rule_List,{s_,a_List,n_}]:=If[!(1≤n≤Length[a]),Throw[Null],Apply[{#1,ReplacePart[a,#2,n],n+#3}&,Replace[{s,a〚n〛},rule]]]
In[]:=
TMEvolveList[rule_,init_List,t_Integer]:=NestWhileList[TMStep[rule,#]&,init,#[[1]]>0&,1,t]
In[]:=
AllHTM[s_,k_]:=Thread[Tuples[{Range[s],Range[0,k-1]}]->#]&/@Tuples[Tuples[{Range[-1,s],Range[0,k-1],{-1,1}}],s*k]
In[]:=
AllHTM[2,2]
Out[]=
{{{1,0}{-1,0,-1},{1,1}{-1,0,-1},{2,0}{-1,0,-1},{2,1}{-1,0,-1}},{{1,0}{-1,0,-1},{1,1}{-1,0,-1},{2,0}{-1,0,-1},{2,1}{-1,0,1}},{{1,0}{-1,0,-1},{1,1}{-1,0,-1},{2,0}{-1,0,-1},{2,1}{-1,1,-1}},{{1,0}{-1,0,-1},{1,1}{-1,0,-1},{2,0}{-1,0,-1},{2,1}{-1,1,1}},{{1,0}{-1,0,-1},{1,1}{-1,0,-1},{2,0}{-1,0,-1},{2,1}{0,0,-1}},{{1,0}{-1,0,-1},{1,1}{-1,0,-1},{2,0}{-1,0,-1},{2,1}{0,0,1}},
⋯65524⋯
,{{1,0}{2,1,1},{1,1}{2,1,1},{2,0}{2,1,1},{2,1}{1,1,-1}},{{1,0}{2,1,1},{1,1}{2,1,1},{2,0}{2,1,1},{2,1}{1,1,1}},{{1,0}{2,1,1},{1,1}{2,1,1},{2,0}{2,1,1},{2,1}{2,0,-1}},{{1,0}{2,1,1},{1,1}{2,1,1},{2,0}{2,1,1},{2,1}{2,0,1}},{{1,0}{2,1,1},{1,1}{2,1,1},{2,0}{2,1,1},{2,1}{2,1,-1}},{{1,0}{2,1,1},{1,1}{2,1,1},{2,0}{2,1,1},{2,1}{2,1,1}}}
Full expression not available
(
original memory size:
84.9 MB)
In[]:=
HTMRulePlot[rule_,opts___]:=​​Module​​s=Max[rule[[All,1,1]],rule[[All,2,1]]],​​cr=<|0
,1
,2
|>​​,​​GraphicsRow​​Graphics​​Style[Rectangle[{-1/2,0}],cr[#[[1,2]]],EdgeForm[GrayLevel[-1+GoldenRatio]]],
[◼]
FiniteStateIndicatorIcon
[{0,.5},{#[[1,1]],s}],If#[[2,1]]>0,Style[Rectangle[{-1/2,-1.25}],cr[#[[2,2]]],EdgeForm[GrayLevel[-1+GoldenRatio]]],
[◼]
FiniteStateIndicatorIcon
[{#[[2,3]],-0.75},{#[[2,1]],s}],{Style[Rectangle[{-1/2,-1.25}],White,EdgeForm[GrayLevel[-1+GoldenRatio]]],Style[Disk[{0,-.75},.3],Switch[#[[2,1]],0,Red,-1,Green]]},PlotRange->{{-2,2},{-7/4,3/2}+0{-.25,.25}}&/@SortBy[rule,{#[[1,1]],-#[[1,2]]}&],​​Frame->All,​​FrameStyle->GrayLevel[-1+GoldenRatio],​​opts​​​​
In[]:=
Clear[HTMEvolutionPlot]
In[]:=
HTMEvolutionPlot[rule_,init_,t_,opts___]:=​​Module{data,stot=Max[rule[[All,1,1]],rule[[All,2,1]]]},​​data={{#1,#3},#2}&@@@TMEvolveList[HTMFix@rule,init,t];​​Show​​ArrayPlot​​ArrayPad[data[[All,-1]],{{0},{1}}],​​ColorRules0
,1
,2
,​​opts​​,​​Graphics​​MapIndexed​​If#[[1,1]]>0,
[◼]
FiniteStateIndicatorIcon
[{#[[1,2]]+1/2,Length[data]-First[#2]+1/2},{#[[1,1]],stot}],Style[Disk[{#[[1,2]]+1/2,Length[data]-First[#2]+1/2},.3],Switch[#[[1,1]],0,Red,-1,Green]]&,​​data​​​​​​​​
In[]:=
HTMFix[rule_]:=Map[If[#[[2,1]]<=0,#[[1]]->{#[[2,1]],0,0},#]&,rule]
In[]:=
HTMRulePlot[#,ImageSize->300]&/@RandomSample
81
,5
Out[]=

,
,
,
,

In[]:=
%81[[1000]]
Out[]=
{{1,0}{-1,0,-1},{1,1}{-1,1,1},{2,0}{2,1,-1},{2,1}{0,1,1}}
In[]:=
HTMRulePlot[%]
Out[]=
In[]:=
Table[TMEvolveList[{{1,0}{-1,0,-1},{1,1}{-1,1,1},{2,0}{2,1,-1},{2,1}{0,1,1}},{1,Join[Table[0,10],IntegerDigits[i,2],Table[0,10]],11},30],{i,0,5}]
Out[]=
{{{1,{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},11},{-1,{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},10}},{{1,{0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0},11},{-1,{0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0},12}},{{1,{0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0},11},{-1,{0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0},12}},{{1,{0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0},11},{-1,{0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0},12}},{{1,{0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0},11},{-1,{0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0},12}},{{1,{0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0},11},{-1,{0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0},12}}}
In[]:=
Table[Catch[{Last[#][[1]],Length[#]}&[TMEvolveList[{{1,0}{-1,0,-1},{1,1}{-1,1,1},{2,0}{2,1,-1},{2,1}{0,1,1}},{1,Join[Table[0,10],IntegerDigits[i,2],Table[0,10]],11},30]]],{i,0,20}]
Out[]=
{{-1,2},{-1,2},{-1,2},{-1,2},{-1,2},{-1,2},{-1,2},{-1,2},{-1,2},{-1,2},{-1,2},{-1,2},{-1,2},{-1,2},{-1,2},{-1,2},{-1,2},{-1,2},{-1,2},{-1,2},{-1,2}}
In[]:=
ParallelMap[#->Table[Catch[{Last[#][[1]],Length[#]}&[TMEvolveList[#,{1,Join[Table[0,10],IntegerDigits[i,2],Table[0,10]],11},30]]],{i,0,20}]&,RandomSample[AllHTM[2,2],200]]
KernelObject
:Timeout for theta.wolfram.com//usr/local/bin/wolfram. Received only 0 of 24 connections.
Out[]=
{{{1,0}{-1,0,-1},{1,1}{2,1,1},{2,0}{1,0,1},{2,1}{1,0,1}}{{-1,2},{-1,4},{-1,4},{-1,4},{-1,4},{-1,6},{-1,4},{-1,6},{-1,4},{-1,4},{-1,6},{-1,6},{-1,4},{-1,4},{-1,6},{-1,6},{-1,4},{-1,4},{-1,4},{-1,4},{-1,6}},{{1,0}{2,1,1},{1,1}{0,1,1},{2,0}{0,1,1},{2,1}{1,1,-1}}{{0,3},{0,2},{0,2},{0,2},{0,2},{0,2},{0,2},{0,2},{0,2},{0,2},{0,2},{0,2},{0,2},{0,2},{0,2},{0,2},{0,2},{0,2},{0,2},{0,2},{0,2}},{{1,0}{0,0,-1},{1,1}{2,0,-1},{2,0}{0,1,-1},{2,1}{-1,1,1}}{{0,2},{0,3},{0,3},{0,3},{0,3},{0,3},{0,3},{0,3},{0,3},{0,3},{0,3},{0,3},{0,3},{0,3},{0,3},{0,3},{0,3},{0,3},{0,3},{0,3},{0,3}},
⋯194⋯
,{{1,0}{-1,0,-1},{1,1}{0,1,1},{2,0}{0,1,-1},{2,1}{2,1,-1}}{{-1,2},{0,2},{0,2},{0,2},{0,2},{0,2},{0,2},{0,2},{0,2},{0,2},{0,2},{0,2},{0,2},{0,2},{0,2},{0,2},{0,2},{0,2},{0,2},{0,2},{0,2}},{{1,0}{2,1,1},{1,1}{1,0,-1},{2,0}{0,1,1},{2,1}{0,0,-1}}{{0,3},{0,4},{0,4},{0,4},{0,4},{0,4},{0,4},{0,4},{0,4},{0,4},{0,4},{0,4},{0,4},{0,4},{0,4},{0,4},{0,4},{0,4},{0,4},{0,4},{0,4}},{{1,0}{1,1,-1},{1,1}{-1,0,-1},{2,0}{1,1,-1},{2,1}{1,1,-1}}{Null,{-1,2},{-1,2},{-1,2},{-1,2},{-1,2},{-1,2},{-1,2},{-1,2},{-1,2},{-1,2},{-1,2},{-1,2},{-1,2},{-1,2},{-1,2},{-1,2},{-1,2},{-1,2},{-1,2},{-1,2}}}
Full expression not available
(
original memory size:
0.6 MB)
Number of distinct time profiles:

NP

Run NDTM and harvest branches with accept or reject . Then feed to DTM and see what it can do

Lower Bounds on Functions

<NDTM: is the correct accept/reject on some branch?> < What if it enumerates all outputs? >