In[]:=
RepresentativeKernels[]:=Last/@First/@GatherBy[ParallelEvaluate[{$MachineName,#},#]&/@Kernels[],First]
In[]:=
SetAttributes[ParallelOnce,HoldFirst]
In[]:=
ParallelOnce[expr_]:=ParallelEvaluate[expr,RepresentativeKernels[]]
In[]:=
PacletInstall["/Users/sw/Dropbox/Physics/CodeDevelopment/Paclets/CombinatorEvolve-0.0.4.paclet"]
Out[]=
PacletObject
Name: CombinatorEvolve
Version: 0.0.4
Location: /Users/sw/Library/WolframDesktop/Paclets/Repository/CombinatorEvolve-0.0.4
Description: CombinatorEvolve computes SK combinator leaf counts.

In[]:=
ParallelOnce["/Users/sw/Dropbox/Physics/CodeDevelopment/Paclets/CombinatorEvolve-0.0.4.paclet"]
Out[]=
{/Users/sw/Dropbox/Physics/CodeDevelopment/Paclets/CombinatorEvolve-0.0.4.paclet,/Users/sw/Dropbox/Physics/CodeDevelopment/Paclets/CombinatorEvolve-0.0.4.paclet,/Users/sw/Dropbox/Physics/CodeDevelopment/Paclets/CombinatorEvolve-0.0.4.paclet,/Users/sw/Dropbox/Physics/CodeDevelopment/Paclets/CombinatorEvolve-0.0.4.paclet,/Users/sw/Dropbox/Physics/CodeDevelopment/Paclets/CombinatorEvolve-0.0.4.paclet}
In[]:=
ParallelEvaluate[<<CombinatorEvolve`]
In[]:=
<<CombinatorEvolve`
In[]:=
FindLambdasFromStephen[n_,vars_]:=ResourceFunction["ParallelMapMonitored"][Function[c,If[FreeQ[Last[#],s|k],If[Head[#]===Failure,Nothing,#]&[#],Nothing]&[cCombinatorFixedPoint[Fold[#[#2]&,c,Range[vars]],"MaxSize"10000,"MaxSteps"1000]]],EnumerateCombinators[n]]
In[]:=
SKCombinatorExpressionsWithLeafCount[leafCount_] := EnumerateCombinators[leafCount]
In[]:=
$skCombinatorRules = {s[a_][b_][c_] :> a[c][b[c]], k[a_][b_] :> a};​​$maxSteps = 1000;​​$maxLeafCount = 10000;​​$evaluationOrder = "LeftmostOutermost";
In[]:=
skCombinatorFixedPointIfAppliedToArguments[argumentCount_][expr_] := Module[{init,fixedPoint},​​ init = Fold[#[#2] &, expr, Range[argumentCount]];​​ fixedPoint = CombinatorFinalExpression[ {s[a_][b_][c_] :> a[c][b[c]], k[a_][b_] :> a}, init, $maxSteps, $evaluationOrder, $maxLeafCount];​​ If[fixedPoint =!= $Failed && FreeQ[fixedPoint, s | k],​​ fixedPoint​​ ,​​ $Failed]​​]
In[]:=
FindLambdas[leafCount_, variableCount_] := Cases[​​ ResourceFunction["ParallelMapMonitored"][​​ (#  skCombinatorFixedPointIfAppliedToArguments[variableCount][#]) &,​​ SKCombinatorExpressionsWithLeafCount[leafCount]],​​ Except[_ -> $Failed]]
In[]:=
CombinatorFinalExpression[{s[a_][b_][c_]:>a[c][b[c]],k[a_][b_]:>a},s[s[s]],$maxSteps,$evaluationOrder,$maxLeafCount]
Out[]=
s[s[s]]
In[]:=
DeleteCases[FindLambdasFromStephen[#,#],_->_?FailureQ]===FindLambdas[#,#]&/@Range[8]
Out[]=
{True,True,True,True,True,True,True,True}
In[]:=
SKCombinatorExpressionsWithLeafCount[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[]:=
InputForm[%]
Out[]//InputForm=
{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[]:=
FindLambdas[4,4]
Out[]=
{s[s[s[s]]]2[1[2]][3][1[2][2[1[2]]][3]][4],s[s][s][k]1[2][3][4],s[s[s][k]]2[1[2]][2][3][4],s[s[s[k]]]2[1[2]][3][4],s[s][s[k]]1[2][2][3][4],s[s[k][s]]2[1[2]][3][4],s[s[k]][s]1[3][2[3]][4],s[s[k[s]]]2[1[2]][4][3[4]],s[s][k][k]1[2][3][4],s[s[k][k]]2[1[2]][3][4],s[s[k]][k]1[3][4],s[s[k[k]]]2[1[2]][4],s[k][s][s]1[3][2[3]][4],s[k[s][s]]2[3][1[2][3]][4],s[k[s]][s]1[2[3]][3[2[3]]][4],s[k[s[s]]]3[4][1[2][3][4]],s[k][s[s]]1[2][3][4],s[k][s][k]1[3][4],s[k[s][k]]2[3][1[2][3]][4],s[k[s]][k]1[2[3]][4],s[k[s[k]]]3[4],s[k][s[k]]1[2][3][4],s[k][k][s]1[3][2[3]][4],s[k[k][s]]2[3][4],s[k[k]][s]1[4][3[4]],s[k][k[s]]1[2][3][4],s[k][k][k]1[3][4],s[k[k][k]]2[3][4],s[k[k]][k]1[4],s[k[k[k]]]3,s[k][k[k]]1[2][3][4],k[s][s][s]2[3][1[2][3]][4],k[s[s]][s]2[3][1[2][3]][4],k[s[s[s]]]2[3][4][3[2[3]][4]],k[s][s[s]]1[3][2[3]][4],k[s][s][k]2[3][4],k[s[s][k]]2[3][2][4],k[s[s]][k]2[3][1[2][3]][4],k[s[s[k]]]2[3][4],k[s][s[k]]1[3][2[3]][4],k[s][k][s]2[3][1[2][3]][4],k[s[k][s]]2[3][4],k[s[k]][s]2[3][4],k[s][k[s]]1[3][2[3]][4],k[s][k][k]2[3][4],k[s[k][k]]2[3][4],k[s[k]][k]2[3][4],k[s[k[k]]]2[3],k[s][k[k]]1[3][2[3]][4],k[k][s][s]2[4][3[4]],k[k[s][s]]2[4][3[4]],k[k[s]][s]2[4][3[4]],k[k][s[s]]1[3][4],k[k][s][k]2[4],k[k[s][k]]2[4][3[4]],k[k[s]][k]2[4][3[4]],k[k[s[k]]]4,k[k][s[k]]1[3][4],k[k][k][s]2[4][3[4]],k[k[k][s]]2[4],k[k[k]][s]2[4],k[k][k[s]]1[3][4],k[k][k][k]2[4],k[k[k][k]]2[4],k[k[k]][k]2[4],k[k][k[k]]1[3][4]}
In[]:=
FindLambdas[4,2]
Out[]=
{s[s][s][k]1[2],s[s[s][k]]2[1[2]][2],s[s[s[k]]]2[1[2]],s[s][s[k]]1[2][2],s[s[k][s]]2[1[2]],s[s][k][k]1[2],s[s[k][k]]2[1[2]],s[s[k]][k]1,s[k][s[s]]1[2],s[k][s][k]1,s[k][s[k]]1[2],s[k[k][s]]2,s[k][k[s]]1[2],s[k][k][k]1,s[k[k][k]]2,s[k][k[k]]1[2],k[s][s][k]2,k[s[k][s]]2,k[s[k]][s]2,k[s][k][k]2,k[s[k][k]]2,k[s[k]][k]2,k[k][s[s]]1,k[k][s[k]]1,k[k][k[s]]1,k[k][k[k]]1}
In[]:=
FindLambdas[8,2]
Out[]=
{s[s][s][s][s][s][s][k]1[2],s[s[s][s][s][s][s][k]]2[1[2]],s[s[s[s][s][s][s][k]]]1[2][2[1[2]]],s[s[s][s][s][s]][s][k]2,s[s[s[s[s][s][s][k]]]]2[1[2]][1[2][2[1[2]]]],s[s[s[s][s][s]][s][k]]1[2],s[s[s[s][s][s]]][s][k]2,s[s[s[s[s[s][s][k]]]]]1[2][2[1[2]]][2[1[2]][1[2][2[1[2]]]]],s[s[s[s[s][s]][s][k]]]2[1[2]],s[s[s[s][s]][s]][s][k]1[2],
⋯33050⋯
,k[k][k][k][k[k][k[k]]]1,k[k[k][k]][k[k[k][k]]]1,k[k[k][k]][k[k[k]][k]]1,k[k[k]][k][k[k[k][k]]]1,k[k[k][k]][k[k[k[k]]]]1,k[k[k][k]][k[k][k[k]]]1,k[k[k]][k][k[k[k]][k]]1,k[k[k]][k][k[k[k[k]]]]1,k[k[k]][k][k[k][k[k]]]1}
large output
show less
show more
show all
set size limit...
In[]:=
Select[%170,LeafCount[Last[#]]<10&]
Out[]=
{s[s][s][s][s][s][s][k]1[2],s[s[s][s][s][s][s][k]]2[1[2]],s[s[s[s][s][s][s][k]]]1[2][2[1[2]]],s[s[s][s][s][s]][s][k]2,s[s[s[s[s][s][s][k]]]]2[1[2]][1[2][2[1[2]]]],s[s[s[s][s][s]][s][k]]1[2],s[s[s[s][s][s]]][s][k]2,s[s[s[s[s][s]][s][k]]]2[1[2]],s[s[s[s][s]][s]][s][k]1[2],s[s[s[s[s][s]]]][s][k]1[2],
⋯32978⋯
,k[k][k][k][k[k[k[k]]]]1,k[k][k][k][k[k][k[k]]]1,k[k[k][k]][k[k[k][k]]]1,k[k[k][k]][k[k[k]][k]]1,k[k[k]][k][k[k[k][k]]]1,k[k[k][k]][k[k[k[k]]]]1,k[k[k][k]][k[k][k[k]]]1,k[k[k]][k][k[k[k]][k]]1,k[k[k]][k][k[k[k[k]]]]1,k[k[k]][k][k[k][k[k]]]1}
large output
show less
show more
show all
set size limit...
In[]:=
Length[%]
Out[]=
26255
In[]:=
FindLambdasFromStephen[4,2]
Out[]=
{s[s][s][k]1[2],s[s[s][k]]2[1[2]][2],s[s[s[k]]]2[1[2]],s[s][s[k]]1[2][2],s[s[k][s]]2[1[2]],s[s][k][k]1[2],s[s[k][k]]2[1[2]],s[s[k]][k]1,s[k][s[s]]1[2],s[k][s][k]1,s[k][s[k]]1[2],s[k[k][s]]2,s[k][k[s]]1[2],s[k][k][k]1,s[k[k][k]]2,s[k][k[k]]1[2],k[s][s][k]2,k[s[k][s]]2,k[s[k]][s]2,k[s][k][k]2,k[s[k][k]]2,k[s[k]][k]2,k[k][s[s]]1,k[k][s[k]]1,k[k][k[s]]1,k[k][k[k]]1}
In[]:=
First[AbsoluteTiming[FindLambdas[8,8]]]
Out[]=
43.9823
In[]:=
First[AbsoluteTiming[FindLambdas[8,8]]]
Out[]=
33.9938
In[]:=
First[AbsoluteTiming[FindLambdas[10,10]]]
Out[]=
3042.83
In[]:=
First[AbsoluteTiming[FindLambdas[10,10]]]
In[]:=
FindLambdas[4,2]
Out[]=
{s[s][s][k]1[2],s[s[s][k]]2[1[2]][2],s[s[s[k]]]2[1[2]],s[s][s[k]]1[2][2],s[s[k][s]]2[1[2]],s[s][k][k]1[2],s[s[k][k]]2[1[2]],s[s[k]][k]1,s[k][s[s]]1[2],s[k][s][k]1,s[k][s[k]]1[2],s[k[k][s]]2,s[k][k[s]]1[2],s[k][k][k]1,s[k[k][k]]2,s[k][k[k]]1[2],k[s][s][k]2,k[s[k][s]]2,k[s[k]][s]2,k[s][k][k]2,k[s[k][k]]2,k[s[k]][k]2,k[k][s[s]]1,k[k][s[k]]1,k[k][k[s]]1,k[k][k[k]]1}
In[]:=
CombinatorFixedPointList[s[s][s][k][1][2]]//Column

How many of the lambdas can we get with how large a combinator expression?

Original

Single variable: 4n - 1 is the combinator size for all 1-argument lambdas
Up to size 6, only get 1

The case of 1[1]

Fastest:

Beaver

The pure program evaluates before it’s applied to arguments.....

Fl 9 1

To get to Nest[#[1]&,

What can one compute? (AKA algorithmic complexity of various computations)

What are the “most natural things to compute” with combinators?

Cf. what chemicals are most commonly synthesized

Summary 1[1] occurs for size 6, 1[1[1]] needs size 8

Program entropy: for computing a given function, how many distinct programs do it?

Two argument case (?)

Purely with S

Answer must be embedded in a coat of S’s..... Cannot be “the pure answer”....

Saving data

This is case #2:
Another case:

Lambdas