Non-Terminating Combinator Expressions

S combinator expressions of leaf counts 1 through 10 that do not halt

Details

The data is calculated by enumerating S combinator expressions of a certain leaf count using EnumerateCombinators and then applying SCombinatorHaltsQ to check if each expression's evolution will terminate.

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.

Examples

Basic Examples

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

In[1]:=

$Normal[ResourceData[\!$\* TagBox["\"\<Non-Terminating Combinator Expressions\>\"", #& , BoxID -> "ResourceTag-Non-Terminating Combinator Expressions-Input", AutoDelete->True]$]][7]$

Out[1]=

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

In[2]:=

$Length[Normal[ResourceData[\!$\* TagBox["\"\<Non-Terminating Combinator Expressions\>\"", #& , BoxID -> "ResourceTag-Non-Terminating Combinator Expressions-Input", AutoDelete->True]$]][10]]$

Out[2]=

Scope & Additional Elements

The function SNT can be used to extend the dataset; however, note that as the leaf count for the combinator expressions increases, this computation will become increasingly more time-expensive:

In[3]:=

$SNT[n_Integer] := First[Reap[ With[{all = ResourceFunction["EnumerateCombinators"][n, {s}]}, ResourceFunction["ParallelMapMonitored"][ If[! ResourceFunction["SCombinatorHaltsQ"][#, "SGlyph" -> s], Sow[#], Nothing] &, all]]]]$

Return the time required to calculate non-terminating S combinator expressions of leaf count 11:

In[4]:=

Out[4]=

Group terminating S combinator expressions of leaf count 7 in equivalence groups designated by their fixed point form:

In[5]:=

$terminating7 = Complement[ResourceFunction["EnumerateCombinators"][7, {s}], Normal[ResourceData[\!$\* TagBox["\"\<Non-Terminating Combinator Expressions\>\"", #& , BoxID -> "ResourceTag-Non-Terminating Combinator Expressions-Input", AutoDelete->True]$]][7]];$