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

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

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

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

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]],PlotRangeAll,ImageSize100,FrameTrue,FrameTicksNone,FillingAxis,FillingStyleGrayLevel[.8]]&/@allschemes)cb],EnumerateCombinators[3]]]
Out[]=


,
,
,
,
,
,
,

Add
,

,
,
,
,
,
,
,

Add
,

,
,
,
,
,
,
,

Add
,

,
,
,
,
,
,
,

Add
,

,
,
,
,
,
,
,

Add
,

,
,
,
,
,
,
,

Add
,

,
,
,
,
,
,
,

Add
,

,
,
,
,
,
,
,

Add
,

,
,
,
,
,
,
,

Add
,

,
,
,
,
,
,
,

Add
,

,
,
,
,
,
,
,

Add
,

,
,
,
,
,
,
,

Add
,

,
,
,
,
,
,
,

Add
,

,
,
,
,
,
,
,

Add
,

,
,
,
,
,
,
,

Add
,

,
,
,
,
,
,
,

Add

Clear
Copy

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