[MaxP]

Combinator Termination

An expression is exploding iff we start an evolution with that expression as an init, it will not terminate.
An expression is exploding if:
One of the further states contains the init.
1
.
One of the further states contains another exploding expression.
2
.

Evolution Code

recursingCombinatorExpression[expr_,maxSteps_]:=recursingCombinatorExpression[expr,maxSteps]=!FreeQ[Rest[SKFixedPointEvolveList[expr,∞,maxSteps]],expr]
In[]:=
explodingCombinatorExpression[expr_,maxSteps_]:=explodingCombinatorExpression[expr,maxSteps]=AnyTrue[Catenate[Level[#,{0,∞},HeadsTrue]&/@SKFixedPointEvolveList[expr,∞,maxSteps]],recursingCombinatorExpression[#,maxSteps]&]
In[]:=
s[x_][y_][z_]x[z][y[z]]
explodingCombinatorExpression[s[s][s][s],300]
In[]:=
False
Out[]=
explodingCombinatorExpression[s[s[s]][s][s][s][s[k]],200]
In[]:=
True
Out[]=
explodingCombinatorExpression
s[
][
][
][
][
][
][
][
][
][
][
][
]
,100
In[]:=
True
Out[]=
recursingCombinatorExpression
s[
][
][
][
][
][
][
][
][
][
][
][
]
,100
In[]:=
True
Out[]=
LeafCount/@SKOuterEvolveList[s[s][s][s[s][s]][s[s][s]],40]
In[]:=
{9,11,13,15,21,27,37,47,57,70,83,96,116,126,146,166,186,213,226,239,255,265,281,297,313,336,349,372,382,405,428,451,481,497,513,532,545,564,574,593,612}
Out[]=
ListLinePlot[%]
In[]:=
Out[]=
ListStepPlot[Differences[LeafCount/@SKOuterEvolveList[s[s][s][s[s][s]][s[s][s]],200]]]
In[]:=
Out[]=
explodingCombinatorExpression[s[s][s][s[s][s]][s[s][s]],20]
In[]:=
False
Out[]=
recursingCombinatorExpressionX[expr_,maxSteps_]:=recursingCombinatorExpressionX[expr,maxSteps]=!FreeQ[Rest[SKOuterEvolveList[expr,maxSteps]],expr]
In[]:=
recursingCombinatorExpressionX[s[s][s][s[s][s]][s[s][s]],30]
In[]:=
False
Out[]=
evolxxx=SKOuterEvolveList[s[s][s][s[s][s]][s[s][s]],100];
In[]:=
Position[evolxxx,s[s][s][s[s][s]][s[s][s]]]
In[]:=
{{1}}
Out[]=
AnyTrue[Catenate[Level[#,{0,∞},HeadsTrue]&/@SKOuterEvolveList[expr,∞,maxSteps]],recursingCombinatorExpression[#,maxSteps]&]

Causal graphs

Metadata is expression[contents, creatorEvent]
addMetadataToInitExpression[expr_,nextExpressionIDFunction_,saveExpressionContentsFunction_,saveExpressionGenerationFunction_]:=Map[With[{id=nextExpressionIDFunction[]},saveExpressionContentsFunction[id,#];saveExpressionGenerationFunction[id,0];expression[#,id,0]]&,expr,{0,∞},HeadsTrue]
In[]:=
addMetadataToInitExpression[s[s][s][s]]
In[]:=
expression[expression[expression[expression[s,0][expression[s,0]],0][expression[s,0]],0][expression[s,0]],0]
Out[]=
%//.expression[expr_,0]expr
In[]:=
s[s][s][s]
Out[]=
addMetadataToInitExpression[x]
In[]:=
expression[x,0]
Out[]=
Clear[skRulesWithMetadata]
In[]:=
outputIDs
In[]:=
outputIDs
Out[]=
Thread[expression/@{inputID1s,inputID2stripExpression[s[x]],inputID3->stripExpression[s[x][y]],inputID4->stripExpression[s[x][y][z]]}event[eventID]]
skRulesWithMetadata[nextExpressionIDFunction_,nextEventIDFunction_,saveExpressionContentsFunction_,saveExpressionGenerationFunction_]:={​​expression[expression[expression[expression[s,inputID1_,t1_][x_],inputID2_,t2_][y_],inputID3_,t3_][z_],inputID4_,t4_](With[{outputIDs=Table[nextExpressionIDFunction[],3],eventID=nextEventIDFunction[],gen=Max[t1,t2,t3,t4]+1},(Sow[Join[Thread[expression/@{inputID1,inputID2,inputID3,inputID4}event[eventID]],Thread[event[eventID]expression/@{outputIDs〚1〛,outputIDs〚2〛,outputIDs〚3〛}]]];saveExpressionContentsFunction@@@Transpose[{outputIDs,{x[z],y[z],x[z][y[z]]}}];​​saveExpressionGenerationFunction@@@Transpose[{outputIDs,{gen,gen,gen}}];​​expression[expression[x[z],outputIDs〚1〛,gen][expression[y[z],outputIDs〚2〛,gen]],outputIDs〚3〛,gen])]),​​expression[expression[expression[k,inputID1_,_][x_],inputID2_,_][y_],inputID3_,_]With[{eventID=nextEventIDFunction[]},(Sow[Thread[expression/@{inputID1,inputID2,inputID3}event[eventID]]];x)]}
In[]:=
stripExpression[expr_]:=expr//.expression[e_,_,_]e
In[]:=
skStepWithMetadata[expr_,nextExpressionIDFunction_,nextEventIDFunction_,saveExpressionContentsFunction_,saveExpressionGenerationFunction_]:=With[{rules=skRulesWithMetadata[nextExpressionIDFunction,nextEventIDFunction,saveExpressionContentsFunction,saveExpressionGenerationFunction]},MapAt[Replace[rules],expr,{First[Sort[Position[expr,Alternatives@@First/@rules]],Nothing]}]]
In[]:=
Options[skExpressionsEventsGraph]=Options[Graph];
In[]:=
generationsFromExpressions[edges_,egens_]:=Association[(#->Max[Cases[edges,(expression[e_]->#):>egens[e]]]+1)&/@(Union[Cases[edges,_event,{2}]])]
In[]:=