Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

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"CombinatorSsymbol used to represent the S combinator in cmb

Examples

Basic Examples (2) 

Demonstrate that an 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 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 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 combinator:

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

Version History

  • 1.0.0 – 08 March 2021

Source Metadata

  • Citation:
    • Barendregt, H., Endrullis, J., Klop, J.W., Waldmann, J., "Dance of the Starlings." In: Fitting, M., Rayman, B. (eds), Raymond Smullyan on Self Reference. Outstanding Contributions to Logic, vol. 14, 67–111. Springer International Publishing, 2017. DOI: 10.1007/978-3-319-68732-2_5

Related Resources

License Information