Comparing with Lower Bounds

MinRuntime[i_,o_]:=Max[2IntegerLength[BitXor[i,o],2]-1,1]
In[]:=
Select[Table[m->OneSidedTuringMachineFunction[{m,1,2},{1,50},1000,All],{m,0,15}],FreeQ[Last[#],Undefined]&]
Out[]=
In[]:=
First[#]->MapIndexed[First[#]-MinRuntime[First[#2],Last[#]]&,Last[#]]&/@
Out[]=
{1{2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2},3{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},5{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,0,2,0,2,0,2,0,2,0,2},6{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},7{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},13{2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2},14{2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2},15{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,0,2,0,2,0,2,0,2,0}}
In[]:=
Grid[{Table[OneSidedTuringMachinePlot[{3,1,2},i,{100,6},ImageSize->90,"LabelInput"->True],{i,13}]},Alignment->Top]
Out[]=
1
3
2
3
3
7
4
5
5
7
6
7
7
15
8
9
9
11
10
11
11
15
12
13
13
15
In[]:=
With[{m=3},Grid[{Table[Labeled[OneSidedTuringMachinePlot[{m,1,2},i,{100,6},ImageSize->90,"LabelInput"->True],Style[Text[{First[#],MinRuntime[i,Last[#]]}&[OneSidedTuringMachineFunction[{m,1,2},i,1000,All]]],Red]],{i,10}]},Alignment->Top]]
Out[]=
1
3
{3,3}
2
3
{1,1}
3
7
{5,5}
4
5
{1,1}
5
7
{3,3}
6
7
{1,1}
7
15
{7,7}
8
9
{1,1}
9
11
{3,3}
10
11
{1,1}
In[]:=
With[{m=#},Grid[{Table[Labeled[OneSidedTuringMachinePlot[{m,1,2},i,{100,6},ImageSize->90,"LabelInput"->True],Style[Text[{First[#],Max[MinRuntime[i,Last[#]],1]}&[OneSidedTuringMachineFunction[{m,1,2},i,1000,All]]],Red]],{i,10}]},Alignment->Top]]&/@({1,3,5,6,7,13,14,15})
Out[]=

1
0
{3,1}
2
2
{1,1}
3
0
{5,3}
4
4
{1,1}
5
4
{3,1}
6
6
{1,1}
7
0
{7,5}
8
8
{1,1}
9
8
{3,1}
10
10
{1,1}
,
1
3
{3,3}
2
3
{1,1}
3
7
{5,5}
4
5
{1,1}
5
7
{3,3}
6
7
{1,1}
7
15
{7,7}
8
9
{1,1}
9
11
{3,3}
10
11
{1,1}
,
1
0
{1,1}
2
2
{1,1}
3
2
{1,1}
4
4
{1,1}
5
4
{1,1}
6
6
{1,1}
7
6
{1,1}
8
8
{1,1}
9
8
{1,1}
10
10
{1,1}
,
1
0
{1,1}
2
0
{3,3}
3
2
{1,1}
4
0
{5,5}
5
4
{1,1}
6
4
{3,3}
7
6
{1,1}
8
0
{7,7}
9
8
{1,1}
10
8
{3,3}
,
1
0
{1,1}
2
3
{1,1}
3
2
{1,1}
4
5
{1,1}
5
4
{1,1}
6
7
{1,1}
7
6
{1,1}
8
9
{1,1}
9
8
{1,1}
10
11
{1,1}
,
1
1
{1,1}
2
2
{1,1}
3
3
{1,1}
4
4
{1,1}
5
5
{1,1}
6
6
{1,1}
7
7
{1,1}
8
8
{1,1}
9
9
{1,1}
10
10
{1,1}
,
1
1
{1,1}
2
3
{3,1}
3
3
{1,1}
4
7
{5,3}
5
5
{1,1}
6
7
{3,1}
7
7
{1,1}
8
15
{7,5}
9
9
{1,1}
10
11
{3,1}
,
1
1
{1,1}
2
3
{1,1}
3
3
{1,1}
4
5
{1,1}
5
5
{1,1}
6
7
{1,1}
7
7
{1,1}
8
9
{1,1}
9
9
{1,1}
10
11
{1,1}

With[{m=15},Grid[{Table[Labeled[OneSidedTuringMachinePlot[{m,1,2},i,{100,6},ImageSize->90,"LabelInput"->True],Style[Text[{First[#],Max[MinRuntime[i,Last[#]],1]}&[OneSidedTuringMachineFunction[{m,1,2},i,1000,All]]],Red]],{i,10}]},Alignment->Top]]
In[]:=
First[#]->MapIndexed[First[#]-MinRuntime[First[#2],Last[#]]&,Last[#]]&/@Select[ParallelTable[m->OneSidedTuringMachineFunction[{m,2,2},{1,20},10000,All],{m,0,4095}],FreeQ[Last[#],Undefined]&]
Out[]=
{64{2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2},65{2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2},66{2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2},67{2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2},68{2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2},69{2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2},70{2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2},71{2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2},72{2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2},73{2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2},74{2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2},75{2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2},76{2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2},77{2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2},78{2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2},
⋯1988⋯
,4082{2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0},4083{2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0},4084{2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0},4085{2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0},4086{2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0},4087{2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0},4088{2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0},4089{2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0},4090{2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0},4091{2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0},4092{2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0},4093{2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0},4094{2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0},4095{2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2,0}}
Full expression not available
(
original memory size:
1.2 MB)
In[]:=
TakeLargestBy
,Max[Last[#]]&,5
Out[]=
{378{6,2,14,2,6,2,30,2,6,2,14,2,6,2,62,2,6,2,14,2},1351{6,2,14,2,6,2,30,2,6,2,14,2,6,2,62,2,6,2,14,2},3626{2,6,2,14,2,6,2,30,2,6,2,14,2,6,2,62,2,6,2,14},3717{2,6,2,14,2,6,2,30,2,6,2,14,2,6,2,62,2,6,2,14},1447{8,4,18,2,12,6,32,2,10,4,24,2,16,8,50,2,8,4,22,2}}
In[]:=
First[#]->MapIndexed[First[#]-MinRuntime[First[#2],Last[#]]&,Last[#]]&/@SelectParallelTablem->OneSidedTuringMachineFunction[{m,2,2},{1,200},10^6,All],m,First/@
,FreeQ[Last[#],Undefined]&
Out[]=
In[]:=
First[#]->ListStepPlot[Last[#],PlotRange->All]&/@
264
Out[]=
378
0
50
100
150
200
0
100
200
300
400
500
,1351
0
50
100
150
200
0
100
200
300
400
500
,3626
0
50
100
150
200
0
100
200
300
400
500
,3717
0
50
100
150
200
0
100
200
300
400
500
,1447
0
50
100
150
200
0
20
40
60
80
100
120

In[]:=
With[{mm={378,2,2}},Max/@TakeList[MapIndexed[First[#]-MinRuntime[First[#2],Last[#]]&,OneSidedTuringMachineFunction[mm,{1,256},10^6,All]],PowerRange[1,127,2]]]
Out[]=
{4,12,28,60,124,252,508}
In[]:=
Ratios[%]//N
Out[]=
{3.,2.33333,2.14286,2.06667,2.03226,2.01587}
In[]:=
With[{mm={1447,2,2}},Max/@TakeList[MapIndexed[First[#]-MinRuntime[First[#2],Last[#]]&,OneSidedTuringMachineFunction[mm,{1,256},10^6,All]],PowerRange[1,127,2]]]
Out[]=
{8,18,32,50,72,98,128}
In[]:=
Differences[%]
Out[]=
{10,14,18,22,26,30}
In[]:=
Differences[%]
Out[]=
{4,4,4,4,4}
In[]:=
With[{mm={1447,2,2}},Max/@TakeList[OneSidedTuringMachineFunction[mm,{1,256},10^6,"Steps"],PowerRange[1,127,2]]]

Multiple Times

Partial Function

1,2 vs. 2,2

Space Complexity

BUGS!!!

More...