Named Combinators
Named Combinators
In[]:=
CombinatorFromString["(S(SK))"]
Out[]=
s[s[k]]
In[]:=
CombinatorFromString["((S(K((S(K(S((S(K((S((SK)K))((SK)K))))((S(K((S(KS))K)))((S(K(S((SK)K))))K))))))K)))(S(K((S((S(K((S(KS))K)))S))(KK)))))"]
Out[]=
s[k[s[k[s[s[k[s[s[k][k]][s[k][k]]]][s[k[s[k[s]][k]]][s[k[s[s[k][k]]]][k]]]]]][k]]][s[k[s[s[k[s[k[s]][k]]][s]][k[k]]]]]
Y combinator
Y combinator
In[]:=
CombinatorFromString["(((SS)K)((S(K((SS)(S((SS)K)))))K))"]
Out[]=
s[s][k][s[k[s[s][s[s[s][k]]]]][k]]
In[]:=
CombinatorEvolveList[s[s][k][s[k[s[s][s[s[s][k]]]]][k]],5]
Out[]=
{s[s][k][s[k[s[s][s[s[s][k]]]]][k]],s[s[k[s[s][s[s[s][k]]]]][k]][k[s[k[s[s][s[s[s][k]]]]][k]]],s[s[k[s[s][s[s[s][k]]]]][k]][k[s[k[s[s][s[s[s][k]]]]][k]]],s[s[k[s[s][s[s[s][k]]]]][k]][k[s[k[s[s][s[s[s][k]]]]][k]]],s[s[k[s[s][s[s[s][k]]]]][k]][k[s[k[s[s][s[s[s][k]]]]][k]]],s[s[k[s[s][s[s[s][k]]]]][k]][k[s[k[s[s][s[s[s][k]]]]][k]]]}
In[]:=
CombinatorEvolveList[s[s][k][s[k[s[s][s[s[s][k]]]]][k]][x][y],5]
Out[]=
{s[s][k][s[k[s[s][s[s[s][k]]]]][k]][x][y],s[s[k[s[s][s[s[s][k]]]]][k]][k[s[k[s[s][s[s[s][k]]]]][k]]][x][y],s[k[s[s][s[s[s][k]]]]][k][x][k[s[k[s[s][s[s[s][k]]]]][k]][x]][y],k[s[s][s[s[s][k]]]][x][k[x]][k[s[k[s[s][s[s[s][k]]]]][k]][x]][y],s[s][s[s[s][k]]][k[x]][k[s[k[s[s][s[s[s][k]]]]][k]][x]][y],s[k[x]][s[s[s][k]][k[x]]][k[s[k[s[s][s[s[s][k]]]]][k]][x]][y]}
In[]:=
LeafCount/@CombinatorEvolveList[s[s][k][s[k[s[s][s[s[s][k]]]]][k]][x][y],20]
Out[]=
{14,22,22,22,20,21,31,19,29,39,51,49,61,47,60,84,58,46,70,94,132}
In[]:=
ListStepPlot[LeafCount/@CombinatorEvolveList[s[s][k][s[k[s[s][s[s[s][k]]]]][k]][x][y],100]]
Out[]=
In[]:=
CombinatorEvolutionPlot[CombinatorEvolveList[s[s][k][s[k[s[s][s[s[s][k]]]]][k]][x][y],50],"SizeAndMatches"]
Out[]=
In[]:=
CombinatorEvolutionPlot[CombinatorEvolveList[s[s][k][s[k[s[s][s[s[s][k]]]]][k]][x][y],100],"SizeAndMatches"]
Out[]=
In[]:=
Position[CombinatorEvolveList[s[s][k][s[k[s[s][s[s[s][k]]]]][k]][x],30],s[s][k][s[k[s[s][s[s[s][k]]]]][k]]]
Out[]=
{{1,0}}
Mockingbird combinator
Mockingbird combinator
In[]:=
CombinatorFromString["((S((SK)K))((SK)K))"]
Out[]=
s[s[k][k]][s[k][k]]
In[]:=
CombinatorEvolveList[s[s[k][k]][s[k][k]],5]
Out[]=
{s[s[k][k]][s[k][k]],s[s[k][k]][s[k][k]],s[s[k][k]][s[k][k]],s[s[k][k]][s[k][k]],s[s[k][k]][s[k][k]],s[s[k][k]][s[k][k]]}
In[]:=
CombinatorEvolveList[s[s[k][k]][s[k][k]][x],5]
Out[]=
{s[s[k][k]][s[k][k]][x],s[k][k][x][s[k][k][x]],k[x][k[x]][s[k][k][x]],x[s[k][k][x]],x[k[x][k[x]]],x[x]}
More
More
In[]:=
Graph[MWCombinatorGraphMinimal[s[s[s]][s][s][s][s[k]],12],AspectRatio1.2]
Out[]=
Different Updating Orders
Different Updating Orders
In[]:=
<<CombinatorEvolve`
In[]:=
EnumerateCombinators[3]
Out[]=
{s[s][s],s[s[s]],s[s][k],s[s[k]],s[k][s],s[k[s]],s[k][k],s[k[k]],k[s][s],k[s[s]],k[s][k],k[s[k]],k[k][s],k[k[s]],k[k][k],k[k[k]]}
In[]:=
ResourceFunction["InteractiveListSelector"][ResourceFunction["ParallelMapMonitored"][Function[cb,(ListStepPlot[LeafCount/@CombinatorEvolveList[cb,100,Append[#,1]],PlotRangeAll,ImageSize100,FrameTrue,FrameTicksNone,FillingAxis,FillingStyleGrayLevel[.8]]&/@allschemes)cb],EnumerateCombinators[3]]]
Out[]=
Unique Evolution Cases
Unique Evolution Cases
Almost deterministic combinator evolution....
Almost deterministic combinator evolution....
Single-path multiway system.....
Find Non-Fixed-Point SK cases
Find Non-Fixed-Point SK cases
S combinator world
S combinator world
Equivalence of infinite S behavior
Equivalence of infinite S behavior
Number of terminating cases
Number of terminating cases
NOTE: redo computing final sizes as well......
Checking for off-by-one
Checking for off-by-one
Old computation
Old computation
Busy Beaver
Busy Beaver
State Transition Graph
State Transition Graph
Saving Non-Terminating Cases
Saving Non-Terminating Cases
Multiway Neck Search
Multiway Neck Search