Wolfram Cloud Page

In[]:=

SKFixedPointEvolveList[s[k][k][x]]

Out[]=

{s[k][k][x],k[x][k[x]],x}

In[]:=

SKFixedPointEvolveList[k[s][k][k][x][y]]

Out[]=

{k[s][k][k][x][y],s[k][x][y],k[y][x[y]],y}

In[]:=

SKFixedPointEvolveList[s[k][x][y]]

Out[]=

{s[k][x][y],k[y][x[y]],y}

In[]:=

SKFixedPointEvolveList[s[s][k[k[k[s][k][k]]]]]

Out[]=

{s[s][k[k[k[s][k][k]]]],s[s][k[k[s[k]]]]}

In[]:=

Grid[Map[If[LeafCount[#]≤2,#,Magnify[#,.5]]&,Transpose[PadRight[SKFixedPointEvolveList/@Apply[s[s][k[k[k[s][k][k]]]][#1][#2]&]/@Tuples[{k,s[k]},2],Automatic,""]],{2}],FrameAll]

Out[]=

s[s][k[k[k[s][k][k]]]][k][k]	s[s][k[k[k[s][k][k]]]][k][s[k]]	s[s][k[k[k[s][k][k]]]][s[k]][k]	s[s][k[k[k[s][k][k]]]][s[k]][s[k]]
s[k][k[k[k[s][k][k]]][k]][k]	s[k][k[k[k[s][k][k]]][k]][s[k]]	s[s[k]][k[k[k[s][k][k]]][s[k]]][k]	s[s[k]][k[k[k[s][k][k]]][s[k]]][s[k]]
k[k][k[k[k[s][k][k]]][k][k]]	k[s[k]][k[k[k[s][k][k]]][k][s[k]]]	s[k][k][k[k[k[s][k][k]]][s[k]][k]]	s[k][s[k]][k[k[k[s][k][k]]][s[k]][s[k]]]
k	s[k]	k[k[k[k[s][k][k]]][s[k]][k]][k[k[k[k[s][k][k]]][s[k]][k]]]	k[k[k[k[s][k][k]]][s[k]][s[k]]][s[k][k[k[k[s][k][k]]][s[k]][s[k]]]]
		k[k[k[s][k][k]]][s[k]][k]	k[k[k[s][k][k]]][s[k]][s[k]]
		k[k[s][k][k]][k]	k[k[s][k][k]][s[k]]
		k[s][k][k]	k[s][k][k]
		s[k]	s[k]

In[]:=

SKFixedPointEvolveList/@%

Out[]=

{{s[s][k[k[k[s][k][k]]]][k][k],s[k][k[k[k[s][k][k]]][k]][k],k[k][k[k[k[s][k][k]]][k][k]],k},{s[s][k[k[k[s][k][k]]]][k][s[k]],s[k][k[k[k[s][k][k]]][k]][s[k]],k[s[k]][k[k[k[s][k][k]]][k][s[k]]],s[k]},{s[s][k[k[k[s][k][k]]]][s[k]][k],s[s[k]][k[k[k[s][k][k]]][s[k]]][k],s[k][k][k[k[k[s][k][k]]][s[k]][k]],k[k[k[k[s][k][k]]][s[k]][k]][k[k[k[k[s][k][k]]][s[k]][k]]],k[k[k[s][k][k]]][s[k]][k],k[k[s][k][k]][k],k[s][k][k],s[k]},{s[s][k[k[k[s][k][k]]]][s[k]][s[k]],s[s[k]][k[k[k[s][k][k]]][s[k]]][s[k]],s[k][s[k]][k[k[k[s][k][k]]][s[k]][s[k]]],k[k[k[k[s][k][k]]][s[k]][s[k]]][s[k][k[k[k[s][k][k]]][s[k]][s[k]]]],k[k[k[s][k][k]]][s[k]][s[k]],k[k[s][k][k]][s[k]],k[s][k][k],s[k]}}

In[]:=

Last/@%

Out[]=

{k,s[k],s[k],s[k]}

In[]:=

Construct[f,a,b]

Out[]=

f[a,b]

In[]:=

SKFixedPointEvolveList[k[s][k][k]]

Out[]=

{k[s][k][k],s[k]}

In[]:=

Function[c,c->SKFixedPointEvolve/@Apply[c[#1][#2]&]/@Tuples[{k,s[k]},2]]/@AllCombinators[4]

Out[]=

In[]:=

FindBooleanFunctions[n_]:=(First[#]FromDigits[Last[#]/.{k1,s[k]0},2])&/@Select[Function[c,c->SKFixedPointEvolve/@Apply[c[#1][#2]&]/@Tuples[{k,s[k]},2]]/@AllCombinators[n],Union[Last[#]]===Sort[{k,s[k]}]&]

In[]:=

bt[1]=FindBooleanFunctions[1]

Out[]=

{}

In[]:=

bt[2]=FindBooleanFunctions[2]

Out[]=

{s[k]10}

In[]:=

bt[3]=FindBooleanFunctions[3]

Out[]=

{s[s][k]8,k[k][s]12,k[k][k]12}

NOTE: possibly not the best choice of what’s True vs. False

In[]:=

RulePlot[BooleanFunction[8,2]]

Out[]=

In[]:=

BooleanTable[Nand[p,q],{p,q}]

Out[]=

{False,True,True,True}

In[]:=

bt[4]=FindBooleanFunctions[4]

Out[]=

{s[s][s[k]]10,s[s[k]][k]12,s[k][s][k]12,s[k[k][s]]10,s[k][k][k]12,s[k[k][k]]10,k[s][s][k]10,k[s[k][s]]10,k[s[k]][s]10,k[s][k][k]10,k[s[k][k]]10,k[s[k]][k]10,k[k][s[s]]12,k[k][s[k]]12,k[k][k[s]]12,k[k][k[k]]12}

In[]:=

bt[5]=FindBooleanFunctions[5]

Out[]=

{s[s[s][s]][k]12,s[s][s[s][k]]8,s[s[s[k]]][s]2,s[s][s][k][k]12,s[s[s[k]][k]]10,s[s[s]][k[k]]10,s[s[k][s]][s]2,s[s[k][s][k]]10,s[s[k]][s][k]10,s[s[k]][s[k]]10,s[s[k][k]][s]2,s[s][k[k]][s]8,s[s][k[k][s]]8,s[s][k][k][k]12,s[s[k][k][k]]10,s[s][k[k][k]]8,s[s][k[k[k]]]11,s[k][s][s][k]10,s[k[s][s]][k]8,s[k][s[s]][k]12,s[k][s][s[k]]10,s[k[s[k]]][s]10,s[k[s][k]][k]8,s[k[s[k]]][k]10,s[k][s[k]][k]12,s[k[k][s[s]]]10,s[k][k][s][k]10,s[k][k[s]][k]12,s[k[k][s[k]]]10,s[k][k][s[k]]10,s[k[k][k[s]]]10,s[k][k[k]][k]12,s[k[k][k[k]]]10,k[s][s][s][k]8,k[s[s][s][k]]10,k[s[s]][s][k]8,k[s][s[s]][k]10,k[s[s][k]][s]8,k[s[s][k][k]]10,k[s[s][k]][k]8,k[s[s]][k][k]8,k[s][s[k]][k]10,k[s[k][s[s]]]10,k[s[k]][s[s]]10,k[s][k][s][k]8,k[s][k[s]][k]10,k[s[k][s[k]]]10,k[s[k]][s[k]]10,k[s[k][k[s]]]10,k[s[k]][k[s]]10,k[s][k[k]][k]10,k[s[k][k[k]]]10,k[s[k]][k[k]]10,k[k][s[s][s]]12,k[k][s[s[s]]]12,k[k][s[s][k]]12,k[k][s[s[k]]]12,k[k][s][k][s]12,k[k][s[k][s]]12,k[k][s[k[s]]]12,k[k][s][k][k]12,k[k][s[k][k]]12,k[k][s[k[k]]]12,k[k[k][s]][s]12,k[k[k]][s][s]12,k[k][k[s][s]]12,k[k][k[s[s]]]12,k[k[k][s]][k]12,k[k[k]][s][k]12,k[k][k[s][k]]12,k[k][k[s[k]]]12,k[k][k][k][s]12,k[k[k][k]][s]12,k[k[k]][k][s]12,k[k][k[k][s]]12,k[k][k[k[s]]]12,k[k][k][k][k]12,k[k[k][k]][k]12,k[k[k]][k][k]12,k[k][k[k][k]]12,k[k][k[k[k]]]12}

In[]:=

CountsBy[%,Last]

Out[]=

1235,812,23,1030,111

In[]:=

Select[%98,Last[#]8&]

Out[]=

{s[s][s[s][k]]8,s[s][k[k]][s]8,s[s][k[k][s]]8,s[s][k[k][k]]8,s[k[s][s]][k]8,s[k[s][k]][k]8,k[s][s][s][k]8,k[s[s]][s][k]8,k[s[s][k]][s]8,k[s[s][k]][k]8,k[s[s]][k][k]8,k[s][k][s][k]8}

In[]:=

First/@%

Out[]=

{s[s][s[s][k]],s[s][k[k]][s],s[s][k[k][s]],s[s][k[k][k]],s[k[s][s]][k],s[k[s][k]][k],k[s][s][s][k],k[s[s]][s][k],k[s[s][k]][s],k[s[s][k]][k],k[s[s]][k][k],k[s][k][s][k]}

In[]:=

Function[c,Length[SKFixedPointEvolveList[#]]&/@Apply[c[#1][#2]&]/@Tuples[{k,s[k]},2]]/@%104

Out[]=

{{4,4,10,10},{5,5,8,8},{4,4,7,7},{4,4,7,7},{5,5,7,7},{5,5,7,7},{5,5,7,7},{5,5,7,7},{5,5,7,7},{5,5,7,7},{5,5,7,7},{5,5,7,7}}

In[]:=

Length[%105]

Out[]=

12

In[]:=

bt[5]=(First[#]FromDigits[Last[#]/.{k1,s[k]0},2])&/@Select[ResourceFunction["ParallelMapMonitored"][Function[c,c->SKFixedPointEvolve/@Apply[c[#1][#2]&]/@Tuples[{k,s[k]},2]],AllCombinators[5]],Union[Last[#]]===Sort[{k,s[k]}]&]

Out[]=

{s[s[s][s]][k]12,s[s][s[s][k]]8,s[s[s[k]]][s]2,s[s][s][k][k]12,s[s[s[k]][k]]10,s[s[s]][k[k]]10,s[s[k][s]][s]2,s[s[k][s][k]]10,s[s[k]][s][k]10,s[s[k]][s[k]]10,s[s[k][k]][s]2,s[s][k[k]][s]8,s[s][k[k][s]]8,s[s][k][k][k]12,s[s[k][k][k]]10,s[s][k[k][k]]8,s[s][k[k[k]]]11,s[k][s][s][k]10,s[k[s][s]][k]8,s[k][s[s]][k]12,s[k][s][s[k]]10,s[k[s[k]]][s]10,s[k[s][k]][k]8,s[k[s[k]]][k]10,s[k][s[k]][k]12,s[k[k][s[s]]]10,s[k][k][s][k]10,s[k][k[s]][k]12,s[k[k][s[k]]]10,s[k][k][s[k]]10,s[k[k][k[s]]]10,s[k][k[k]][k]12,s[k[k][k[k]]]10,k[s][s][s][k]8,k[s[s][s][k]]10,k[s[s]][s][k]8,k[s][s[s]][k]10,k[s[s][k]][s]8,k[s[s][k][k]]10,k[s[s][k]][k]8,k[s[s]][k][k]8,k[s][s[k]][k]10,k[s[k][s[s]]]10,k[s[k]][s[s]]10,k[s][k][s][k]8,k[s][k[s]][k]10,k[s[k][s[k]]]10,k[s[k]][s[k]]10,k[s[k][k[s]]]10,k[s[k]][k[s]]10,k[s][k[k]][k]10,k[s[k][k[k]]]10,k[s[k]][k[k]]10,k[k][s[s][s]]12,k[k][s[s[s]]]12,k[k][s[s][k]]12,k[k][s[s[k]]]12,k[k][s][k][s]12,k[k][s[k][s]]12,k[k][s[k[s]]]12,k[k][s][k][k]12,k[k][s[k][k]]12,k[k][s[k[k]]]12,k[k[k][s]][s]12,k[k[k]][s][s]12,k[k][k[s][s]]12,k[k][k[s[s]]]12,k[k[k][s]][k]12,k[k[k]][s][k]12,k[k][k[s][k]]12,k[k][k[s[k]]]12,k[k][k][k][s]12,k[k[k][k]][s]12,k[k[k]][k][s]12,k[k][k[k][s]]12,k[k][k[k[s]]]12,k[k][k][k][k]12,k[k[k][k]][k]12,k[k[k]][k][k]12,k[k][k[k][k]]12,k[k][k[k[k]]]12}

In[]:=

First/@GatherBy[bt[5],Last]

Out[]=

{s[s[s][s]][k]12,s[s][s[s][k]]8,s[s[s[k]]][s]2,s[s[s[k]][k]]10,s[s][k[k[k]]]11}

In[]:=

bt[6]=(First[#]FromDigits[Last[#]/.{k1,s[k]0},2])&/@Select[ResourceFunction["ParallelMapMonitored"][Function[c,cTimeConstrained[SKFixedPointEvolve/@Apply[c[#1][#2]&]/@Tuples[{k,s[k]},2],1]],AllCombinators[6]],Union[Last[#]]===Sort[{k,s[k]}]&]

In[]:=

First/@GatherBy[bt[6],Last]

Out[]=

{s[s[s][s]][s][k]10,s[s[s]][s][s[k]]14,s[s[s][s][k]][s]2,s[s][s][s][k][k]12,s[s][s[s[k]][k]]8,s[s][s[k[k[k]]]]11}

In[]:=

bt[7]=(First[#]FromDigits[Last[#]/.{k1,s[k]0},2])&/@Select[ResourceFunction["ParallelMapMonitored"][Function[c,cTimeConstrained[SKFixedPointEvolve/@Apply[c[#1][#2]&]/@Tuples[{k,s[k]},2],1]],AllCombinators[7]],Union[Last[#]]===Sort[{k,s[k]}]&];

S combinator only

Random Combinator Behavior

[Combinator Visualization]

[[ From 1994 ]]