Wolfram Research

Extensively Evolving Combinator Expressions

Source Notebook

S combinator expressions of leaf counts 1 through 13 that do not terminate after 10,000 evolution steps

Details

The data is calculated using the method shown in the "Scope & additional elements" subsection.
The default content is a Dataset where the rows are labeled by the leaf count of the S combinator expression and contain the combinator expressions that do not terminate after 10,000 evolution steps.

Examples

Basic Examples

Get the list of non-terminating S combinator expressions of leaf count 7:

In[1]:=
Normal[ResourceData[\!\(\*
TagBox["\"\<Extensively Evolving Combinator Expressions\>\"",
#& ,
BoxID -> "ResourceTag-Extensively Evolving Combinator \
Expressions-Input",
AutoDelete->True]\)]][7]
Out[1]=

Get the length of the list of non-terminating S combinator expressions of leaf count 13:

In[2]:=
Length[Normal[ResourceData[\!\(\*
TagBox["\"\<Extensively Evolving Combinator Expressions\>\"",
#& ,
BoxID -> "ResourceTag-Extensively Evolving Combinator \
Expressions-Input",
AutoDelete->True]\)]][13]]
Out[2]=

Scope & Additional Elements

Perform from scratch the enumeration of S combinator expressions of leaf count n that do not terminate in max steps. This method can be used to extend the dataset; however, note that as the leaf count for the combinator expressions and maximum steps for the evolutions increase, this computation will become increasingly expensive:

In[3]:=
SNT[n_, max_] := With[{all = ResourceFunction["EnumerateCombinators"][n, {s}]}, Select[all, FailureQ[
     ResourceFunction["CombinatorFixedPoint"][#, "SKGlyphs" -> {s, k}, "MaxSteps" -> max]] &]
  ]

Enumerate S combinator expressions of leaf count 8 that do not terminate within 10 steps:

In[4]:=
SNT[8, 10]
Out[4]=

Group S combinator expressions of leaf count 7 that terminate within 10,000 steps in equivalence groups designated by their fixed point form:

In[5]:=
terminating7 = Complement[ResourceFunction["EnumerateCombinators"][7, {s}], Normal[ResourceData[\!\(\*
TagBox["\"\<Extensively Evolving Combinator Expressions\>\"",
#& ,
BoxID -> "ResourceTag-Extensively Evolving Combinator \
Expressions-Input",
AutoDelete->True]\)]][7]];
In[6]:=
Map[First, GatherBy[{#, ResourceFunction["CombinatorFixedPoint"][#, "MaxSteps" -> 10000, "SKGlyphs" -> {s, k}]} & /@
   terminating7, Last], {2}]
Out[6]=

Find the distribution of fixed point leaf counts for S combinator expressions of leaf count 7 that terminate within 10,000 steps:

In[7]:=
fps = Keys[
  GroupBy[{#, ResourceFunction["CombinatorFixedPoint"][#, "MaxSteps" -> 10000, "SKGlyphs" -> {s, k}]} & /@ terminating7, Last]]
Out[7]=
In[8]:=
Histogram[LeafCount /@ fps]
Out[8]=

Wolfram Research, "Extensively Evolving Combinator Expressions" from the Wolfram Data Repository (2021) 

Data Resource History

See Also

Publisher Information