Functions Needed
Functions Needed
TuringMachineRuleCases[s,k]
TuringMachineRuleCount[s,k](4sk)^(2sk)
TuringMachineFunction[machine,i,steps]->value
TuringMachineFunction[machine,i,steps,"Value"|"Steps"|"MaxWidth"|All]->value
TuringMachineFunction[{All,s,k},{imin,imax},steps]
OneSidedTuringMachineFunction[]
Method->"Basic","Compiled","External"
OneSidedTuringMachinePlot[]
In[]:=
<<ExtensionCargo`
In[]:=
CargoBuild[PacletInstall["https://www.wolframcloud.com/obj/nikm/TuringMachineSearch.paclet",ForceVersionInstall->True]];
In[]:=
<<TuringMachineSearch`
In[]:=
ParallelEvaluate[CargoBuild[PacletInstall["https://www.wolframcloud.com/obj/nikm/TuringMachineSearch.paclet",ForceVersionInstall->True]],"OneKernelPerMachine",DistributedContexts->"ExtensionCargo`"]
In[]:=
ParallelEvaluate[$MachineName,"OneKernelPerMachine"]
Out[]=
{delta,epsilon,tremac,macstudio-basement,lambda,threadripper,threadripper2}
In[]:=
OneSidedTuringMachineFunction[{All,1,2},{1,20},30]
Out[]=
{{Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined},{0,2,0,4,4,6,0,8,8,10,8,12,12,14,0,16,16,18,16,20},{Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined},{3,3,7,5,7,7,15,9,11,11,15,13,15,15,31,17,19,19,23,21},{0,Undefined,2,Undefined,4,Undefined,6,Undefined,8,Undefined,10,Undefined,12,Undefined,14,Undefined,16,Undefined,18,Undefined},{0,2,2,4,4,6,6,8,8,10,10,12,12,14,14,16,16,18,18,20},{0,0,2,0,4,4,6,0,8,8,10,8,12,12,14,0,16,16,18,16},{0,3,2,5,4,7,6,9,8,11,10,13,12,15,14,17,16,19,18,21},{Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined},{Undefined,2,Undefined,4,Undefined,6,Undefined,8,Undefined,10,Undefined,12,Undefined,14,Undefined,16,Undefined,18,Undefined,20},{Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined},{Undefined,3,Undefined,5,Undefined,7,Undefined,9,Undefined,11,Undefined,13,Undefined,15,Undefined,17,Undefined,19,Undefined,21},{1,Undefined,3,Undefined,5,Undefined,7,Undefined,9,Undefined,11,Undefined,13,Undefined,15,Undefined,17,Undefined,19,Undefined},{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20},{1,3,3,7,5,7,7,15,9,11,11,15,13,15,15,31,17,19,19,23},{1,3,3,5,5,7,7,9,9,11,11,13,13,15,15,17,17,19,19,21}}
In[]:=
OneSidedTuringMachineFunction[{1285,2,2},{1,60},100]
Out[]=
{0,0,0,4,0,0,0,8,8,0,0,12,0,0,0,16,16,16,16,20,0,0,0,24,24,0,0,28,0,0,0,32,32,32,32,36,32,32,32,40,40,0,0,44,0,0,0,48,48,48,48,52,0,0,0,56,56,0,0,60}
In[]:=
OneSidedTuringMachineFunction[{1285,2,2},{1,60},100,"Steps"]
Out[]=
{9,7,15,3,13,13,21,3,9,11,19,3,19,19,27,3,9,7,15,3,17,17,25,3,9,17,25,3,25,25,33,3,9,7,15,3,13,13,21,3,9,15,23,3,23,23,31,3,9,7,15,3,23,23,31,3,9,23,31,3}
In[]:=
OneSidedTuringMachineFunction[{3,1,2},{1,50},100,"Steps"]
Out[]=
{3,1,5,1,3,1,7,1,3,1,5,1,3,1,9,1,3,1,5,1,3,1,7,1,3,1,5,1,3,1,11,1,3,1,5,1,3,1,7,1,3,1,5,1,3,1,9,1,3,1}
In[]:=
ResourceFunction["TuringMachineToNumber"][{{1,0}{1,1,-1},{1,1}{1,1,1}}]
Out[]=
{14,1,2}
In[]:=
Module[{a},a[i_]:=If[OddQ[i],i,2a[i/2]+1];Array[a,20]]
Out[]=
{1,3,3,7,5,7,7,15,9,11,11,15,13,15,15,31,17,19,19,23}
Module[{a},a[i_]:=If[EvenQ[i],i,2a[i/2]+1];Array[a,20]]
In[]:=
Module[{a},a[i_]:=a[a[i]];a[1]=1;a[2]=3;Array[a,20]]
Out[]=
TerminatedEvaluation[RecursionLimit]
In[]:=
Table[BitOr[i,i-1],{i,1,20}]
Out[]=
{1,3,3,7,5,7,7,15,9,11,11,15,13,15,15,31,17,19,19,23}
In[]:=
Out[]=
{{1,0}{1,1,-1},{1,1}{2,0,-1},{2,0}{2,0,1},{2,1}{1,0,1}}Output{0,0,Undefined,0,4,Undefined,0,0,8,8,0,Undefined,12,0,Undefined,0,16,16,0,16,20,0,16,Undefined,24,24,Undefined,0,28,Undefined,0,0,32,32,0,32,36,0,32,32,40,40,32,0,44,32,0,Undefined,48,48},Runtime{3,5,∞,9,3,∞,11,11,3,5,13,∞,3,13,∞,15,3,5,17,9,3,17,11,∞,3,5,∞,17,3,∞,19,17,3,5,19,9,3,19,11,11,3,5,13,19,3,13,21,∞,3,5}
In[]:=
Out[]=
{{{1,0}{2,0,-1},{1,1}{1,0,-1},{2,0}{2,0,1},{2,1}{1,0,-1}}Output{0,0,0,4,0,0,0,8,8,0,0,12,0,0,0,16,16,16,16,20,0,0,0,24,24,0,0,28,0,0,0,32,32,32,32,36,32,32,32,40,40,0,0,44,0,0,0,48,48,48},Runtime{5,7,7,3,9,9,9,3,5,11,11,3,11,11,11,3,5,7,7,3,13,13,13,3,5,13,13,3,13,13,13,3,5,7,7,3,9,9,9,3,5,15,15,3,15,15,15,3,5,7},{{1,0}{2,0,-1},{1,1}{1,1,-1},{2,0}{2,0,1},{2,1}{1,0,-1}}Output{0,0,0,4,0,0,0,8,8,0,0,12,0,0,0,16,16,16,16,20,0,0,0,24,24,0,0,28,0,0,0,32,32,32,32,36,32,32,32,40,40,0,0,44,0,0,0,48,48,48},Runtime{9,7,15,3,13,13,21,3,9,11,19,3,19,19,27,3,9,7,15,3,17,17,25,3,9,17,25,3,25,25,33,3,9,7,15,3,13,13,21,3,9,15,23,3,23,23,31,3,9,7},{{1,0}{2,0,-1},{1,1}{2,1,-1},{2,0}{2,0,1},{2,1}{1,0,-1}}Output{0,0,0,4,0,0,0,8,8,0,0,12,0,0,0,16,16,16,16,20,0,0,0,24,24,0,0,28,0,0,0,32,32,32,32,36,32,32,32,40,40,0,0,44,0,0,0,48,48,48},Runtime{7,7,11,3,11,11,15,3,7,11,15,3,15,15,19,3,7,7,11,3,15,15,19,3,7,15,19,3,19,19,23,3,7,7,11,3,11,11,15,3,7,15,19,3,19,19,23,3,7,7}}
TuringMachineFunction[{1285,2,2},{1,60},100]
In[]:=
OneSidedTuringMachineFunction[{All,1,2},{1,20},30,All]
Out[]=
Work
Work
In[]:=
all22=TuringMachineOutput[2,2,2^12,2^9];
In[]:=
CountDistinct[all22]
Out[]=
352
In[]:=
all22=OneSidedTuringMachineFunction[{All,2,2},{1,2^9},2^14];
In[]:=
CountDistinct[all22]
Out[]=
350
In[]:=
all22=OneSidedTuringMachineFunction[{All,2,2},{1,2^10},2^14];
In[]:=
CountDistinct[all22]
Out[]=
350
In[]:=
2^9
Out[]=
512
ParallelMap[]
In[]:=
Select[OneSidedTuringMachineFunction[{All,2,2},{1,2^10},2^14],FreeQ[Undefined]->{"Index","Element"}]-{1,0}
Out[]=
Counts[Select[OneSidedTuringMachineFunction[{All,2,2},{1,2^9},2^14],FreeQ[Undefined]]]
In[]:=
GraphicsGrid[Partition[KeyValueMap[ListStepPlot[Take[#1,30],PlotRange->{-2,All},Filling->Axis,Frame->True,FrameTicks->None,Epilog->Text[#2,Scaled[{.1,.8}],{-1,0}]]&,ReverseSort[Counts[Select[OneSidedTuringMachineFunction[{All,2,2},{1,2^9},2^14],FreeQ[Undefined]]]]],UpTo[10]]]
s=3, k=2
s=3, k=2
[[[ crashed ]]]
NDTM
NDTM
This is the lower bound for all TM computations:
The everything machine can always compute a result in a runtime proportional to the max size of the output and input
Given a DTM, it computes a function that has certain values. The NDTM time is basically proportional to the max size of input & output
Plan
Plan
Look at progressively more non-determinism
Look at progressively more non-determinism
Given a deterministic machine, start add rule cases...
Deficient TMs
Deficient TMs
Invariant TMs
Invariant TMs
{ terminated (steps, value) , queue sizes , loop ? }
<<< Can plot the aggregate function in each case ... with dots >>>
Now compare the runtimes, allowing another machine to be used as well at each step....
Now compare the runtimes, allowing another machine to be used as well at each step....
When is there a speed up from being multiway?
When is there a speed up from being multiway?
Take all pairs of rules ...
Amount of non-determinism
Amount of non-determinism
This represents the amount of non-determinism between machines...
[ This specifies how often there are q cases that disagree ]
1,2 NDTMs
1,2 NDTMs
Claim: after t steps, we reach 2^Floor[2 t] values....
If the output is large, the NDTM doesn’t have an advantage over the DTM
Basic point
Basic point
Any given function needs a certain size of DTM to compute it. The everything machine computes most functions (whose values don’t get too big) “quickly”.
What functions need a very big DTM to compute them? Those are exactly the functions of high algorithmic complexity.
limit as problem size infinity ... for a fixed machine size
A given function first shows up at what computation speed? E.g. in the 2,2 case the slow computations were of trivial functions
In 3,2 are there functions that first show up as hard-to-compute by any 3,2 DTM ?
<< Determinism paths in the everything machine >>