Wolfram Research

Function Repository Resource:

SCombinatorHaltsQ

Source Notebook

Test whether evolution of an S combinator expression will halt

Contributed by: Wolfram Research

ResourceFunction["SCombinatorHaltsQ"][cmb]

check whether the S combinator expression cmb will terminate.

Details and Options

The combinator expression cmb should be given in nested-bracket form and contain only the S combinator.
ResourceFunction["SCombinatorHaltsQ"] accepts one option:
"SGlyph" CombinatorS symbol used to represent the S combinator in cmb

Examples

Basic Examples (2) 

Demonstrate that an S combinator expression halts:

In[1]:=
ResourceFunction["SCombinatorHaltsQ"][
 CombinatorS[CombinatorS][CombinatorS][CombinatorS]]
Out[1]=

This corresponds to the fact that its evolution reaches a fixed point after one step:

In[2]:=
ResourceFunction["CombinatorFixedPointList"][
 CombinatorS[CombinatorS][CombinatorS][CombinatorS]]
Out[2]=

Define an S combinator expression with a leaf count that increases with each step:

In[3]:=
cmb = CombinatorS[CombinatorS[CombinatorS[CombinatorS]]][
    CombinatorS[CombinatorS[CombinatorS]]][CombinatorS[CombinatorS]];
LeafCount /@ ResourceFunction["CombinatorEvolveList"][cmb, 10]
Out[4]=

Thus its evolution does not terminate:

In[5]:=
ResourceFunction["SCombinatorHaltsQ"][cmb]
Out[5]=

Options (2) 

Define symbols other than the default CombinatorS glyph to represent the S combinator:

In[6]:=
ResourceFunction["SCombinatorHaltsQ"][s[s][s][s], "SGlyph" -> s]
Out[6]=
In[7]:=
ResourceFunction["SCombinatorHaltsQ"][1[1][1][1], "SGlyph" -> 1]
Out[7]=

SCombinatorHaltsQ throws a failure when the input does not use the specified "SGlyph":

In[8]:=
ResourceFunction["SCombinatorHaltsQ"][s[s][s][s], "SGlyph" -> 1]
Out[8]=

The input expression should exclusively use the S combinator:

In[9]:=
ResourceFunction["SCombinatorHaltsQ"][s[s][k][s], "SGlyph" -> s]
Out[9]=

Resource History

Source Metadata

Related Resources

License Information