Named Combinators

CombinatorFromString["(S(SK))"]
In[]:=
s[s[k]]
Out[]=
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)))))"]
In[]:=
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]]]]]
Out[]=

Y combinator

CombinatorFromString["(((SS)K)((S(K((SS)(S((SS)K)))))K))"]
In[]:=
s[s][k][s[k[s[s][s[s[s][k]]]]][k]]
Out[]=
CombinatorEvolveList[s[s][k][s[k[s[s][s[s[s][k]]]]][k]],5]
In[]:=
{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]]]}
Out[]=
CombinatorEvolveList[s[s][k][s[k[s[s][s[s[s][k]]]]][k]][x][y],5]
In[]:=
{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]}
Out[]=
LeafCount/@CombinatorEvolveList[s[s][k][s[k[s[s][s[s[s][k]]]]][k]][x][y],20]
In[]:=
{14,22,22,22,20,21,31,19,29,39,51,49,61,47,60,84,58,46,70,94,132}
Out[]=
ListStepPlot[LeafCount/@CombinatorEvolveList[s[s][k][s[k[s[s][s[s[s][k]]]]][k]][x][y],100]]
In[]:=
Out[]=
CombinatorEvolutionPlot[CombinatorEvolveList[s[s][k][s[k[s[s][s[s[s][k]]]]][k]][x][y],50],"SizeAndMatches"]
In[]:=
Out[]=
CombinatorEvolutionPlot[CombinatorEvolveList[s[s][k][s[k[s[s][s[s[s][k]]]]][k]][x][y],100],"SizeAndMatches"]
In[]:=
Out[]=
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]]]
In[]:=
{{1,0}}
Out[]=

Mockingbird combinator

CombinatorFromString["((S((SK)K))((SK)K))"]
In[]:=
s[s[k][k]][s[k][k]]
Out[]=
CombinatorEvolveList[s[s[k][k]][s[k][k]],5]
In[]:=
{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]]}
Out[]=
CombinatorEvolveList[s[s[k][k]][s[k][k]][x],5]
In[]:=
{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]}
Out[]=

More

Graph[MWCombinatorGraphMinimal[s[s[s]][s][s][s][s[k]],12],AspectRatio1.2]
In[]:=
CloudConnect
:Connecting to a cloud running an earlier version of the Wolfram Engine: 12.1
Out[]=

Different Updating Orders

<<CombinatorEvolve`
In[]:=
EnumerateCombinators[3]
In[]:=
{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]]}
Out[]=
ResourceFunction["InteractiveListSelector"][ResourceFunction["ParallelMapMonitored"][Function[cb,(ListStepPlot[LeafCount/@CombinatorEvolveList[cb,100,Append[#,1]],PlotRangeAll,ImageSize100,FrameTrue,FrameTicksNone,FillingAxis,FillingStyleGrayLevel[.8]]&/@allschemes)cb],EnumerateCombinators[3]]]
In[]:=


,
,
,
,
,
,
,

Add
,

,
,
,
,
,
,
,

Add
,

,
,
,
,
,
,
,

Add
,

,
,
,
,
,
,
,

Add
,

,
,
,
,
,
,
,

Add
,

,
,
,
,
,
,
,

Add
,

,
,
,
,
,
,
,

Add
,

,
,
,
,
,
,
,

Add
,

,
,
,
,
,
,
,

Add
,

,
,
,
,
,
,
,

Add
,

,
,
,
,
,
,
,

Add
,

,
,
,
,
,
,
,

Add
,

,
,
,
,
,
,
,

Add
,

,
,
,
,
,
,
,

Add
,

,
,
,
,
,
,
,

Add
,

,
,
,
,
,
,
,

Add

Clear
Copy
Out[]=

Unique Evolution Cases

Almost deterministic combinator evolution....

Single-path multiway system.....

Find Non-Fixed-Point SK cases

S combinator world

Equivalence of infinite S behavior

Number of terminating cases

NOTE: redo computing final sizes as well......

Checking for off-by-one

Old computation

Busy Beaver

State Transition Graph

Saving Non-Terminating Cases

Multiway Neck Search