[MaxP]
[MaxP]
Combinator Termination
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:
1
.One of the further states contains the init.
2
.One of the further states contains another exploding expression.
Evolution Code
Evolution Code
In[]:=
recursingCombinatorExpression[expr_,maxSteps_]:=recursingCombinatorExpression[expr,maxSteps]=!FreeQ[Rest[SKFixedPointEvolveList[expr,∞,maxSteps]],expr]
In[]:=
explodingCombinatorExpression[expr_,maxSteps_]:=explodingCombinatorExpression[expr,maxSteps]=AnyTrue[Catenate[Level[#,{0,∞},HeadsTrue]&/@SKFixedPointEvolveList[expr,∞,maxSteps]],recursingCombinatorExpression[#,maxSteps]&]
s[x_][y_][z_]x[z][y[z]]
In[]:=
explodingCombinatorExpression[s[s][s][s],300]
Out[]=
False
In[]:=
explodingCombinatorExpression[s[s[s]][s][s][s][s[k]],200]
Out[]=
True
In[]:=
explodingCombinatorExpression,100
Out[]=
True
In[]:=
recursingCombinatorExpression,100
Out[]=
True
Causal graphs
Causal graphs
Metadata is expression[contents, creatorEvent]
In[]:=
addMetadataToInitExpression[expr_,nextExpressionIDFunction_]:=Map[expression[#,nextExpressionIDFunction[]]&,expr,{0,∞},HeadsTrue]
In[]:=
addMetadataToInitExpression[s[s][s][s]]
Out[]=
expression[expression[expression[expression[s,0][expression[s,0]],0][expression[s,0]],0][expression[s,0]],0]
In[]:=
%//.expression[expr_,0]expr
Out[]=
s[s][s][s]
In[]:=
addMetadataToInitExpression[x]
Out[]=
expression[x,0]
In[]:=
Clear[skRulesWithMetadata]
In[]:=
outputIDs
Out[]=
outputIDs
Thread[expression/@{inputID1s,inputID2stripExpression[s[x]],inputID3->stripExpression[s[x][y]],inputID4->stripExpression[s[x][y][z]]}event[eventID]]
In[]:=
Quit
In[]:=
skRulesWithMetadata[nextExpressionIDFunction_,nextEventIDFunction_]:={Echo[expression[expression[expression[expression[s,inputID1_][x_],inputID2_][y_],inputID3_][z_],inputID4_]:>(Echo[outputIDs];With[{outputIDs=Table[nextExpressionIDFunction[],3],eventID=nextEventIDFunction[]},(Sow[Join[EchoLabel["thread"]@Thread[expression/@{inputID1s,inputID2stripExpression[s[x]],inputID3->stripExpression[s[x][y]],inputID4->stripExpression[s[x][y][z]]}event[eventID]],Thread[event[eventID]expression/@{outputIDs〚1〛stripExpression[x[z]],outputIDs〚2〛stripExpression[y[z]],outputIDs〚3〛stripExpression[x[z][y[z]]]}]]];expression[expression[x[z],outputIDs〚1〛][expression[y[z],outputIDs〚2〛]],outputIDs〚3〛])])],expression[expression[expression[k,inputID1_][x_],inputID2_][y_],inputID3_]With[{eventID=nextEventIDFunction[]},(Sow[Thread[expression/@{inputID1,inputID2,inputID3}event[eventID]]];x)]}
In[]:=
stripExpression[expr_]:=Module[{x},Echo[expr]//.expression[x_,_]x]
In[]:=
skExpressionsEventsGraph[init_,steps_]:=Module[{expressionID,eventID,nextExpressionIDFunction,nextEventIDFunction,initWithMetadata},expressionID=0;eventID=0;nextExpressionIDFunction=++expressionID&;nextEventIDFunction=++eventID&;initWithMetadata=addMetadataToInitExpression[init,nextExpressionIDFunction];Graph[Cases[initWithMetadata,expression[_,id_]expression[id],All,HeadsTrue],Flatten@Reap[FixedPoint[Replace[#,skRulesWithMetadata[nextExpressionIDFunction,nextEventIDFunction],All,HeadsTrue]&,initWithMetadata,steps]]〚-1〛,VertexStyle{_expressionResourceFunction["WolframPhysicsProjectStyleData"]["ExpressionsEventsGraph","ExpressionVertexStyle"],_eventResourceFunction["WolframPhysicsProjectStyleData"]["ExpressionsEventsGraph","EventVertexStyle"]},EdgeStyleResourceFunction["WolframPhysicsProjectStyleData"]["ExpressionsEventsGraph","EdgeStyle"]]]
In[]:=
skExpressionsEventsGraph[s[s][s][s],∞]
Out[]=
In[]:=
skExpressionsEventsGraph[s[s][s][s][s][s][s],∞]
»
expression[expression[expression[expression[s,inputID1$_][x$_],inputID2$_][y$_],inputID3$_][z$_],inputID4$_](Echo[outputIDs];With[{outputIDs$=Table[(++expressionID$27625&)[],3],eventID$=(++eventID$27625&)[]},Sow[Join[EchoLabel[thread][Thread[expression/@{inputID1$s,inputID2$stripExpression[s[x$]],inputID3$stripExpression[s[x$][y$]],inputID4$stripExpression[s[x$][y$][z$]]}event[eventID$]]],Thread[event[eventID$]expression/@{outputIDs$〚1〛stripExpression[x$[z$]],outputIDs$〚2〛stripExpression[y$[z$]],outputIDs$〚3〛stripExpression[x$[z$][y$[z$]]]}]]];expression[expression[x$[z$],outputIDs$〚1〛][expression[y$[z$],outputIDs$〚2〛]],outputIDs$〚3〛]])
»
outputIDs
»
s[expression[s,2]]
»
s[expression[s,2]][expression[s,4]]
»
s[expression[s,2]][expression[s,4]][expression[s,6]]
»
thread{expression[1s]event[1],expression[3s[s]]event[1],expression[5s[s][s]]event[1],expression[7s[s][s][s]]event[1]}
»
expression[s,2][expression[s,6]]
»
expression[s,4][expression[s,6]]
»
expression[s,2][expression[s,6]][expression[s,4][expression[s,6]]]
»
expression[expression[expression[expression[s,inputID1$_][x$_],inputID2$_][y$_],inputID3$_][z$_],inputID4$_](Echo[outputIDs];With[{outputIDs$=Table[(++expressionID$27625&)[],3],eventID$=(++eventID$27625&)[]},Sow[Join[EchoLabel[thread][Thread[expression/@{inputID1$s,inputID2$stripExpression[s[x$]],inputID3$stripExpression[s[x$][y$]],inputID4$stripExpression[s[x$][y$][z$]]}event[eventID$]]],Thread[event[eventID$]expression/@{outputIDs$〚1〛stripExpression[x$[z$]],outputIDs$〚2〛stripExpression[y$[z$]],outputIDs$〚3〛stripExpression[x$[z$][y$[z$]]]}]]];expression[expression[x$[z$],outputIDs$〚1〛][expression[y$[z$],outputIDs$〚2〛]],outputIDs$〚3〛]])
»
outputIDs
»
s[expression[s,6]]
»
s[expression[s,6]][expression[expression[s,4][expression[s,6]],15]]
»
s[expression[s,6]][expression[expression[s,4][expression[s,6]],15]][expression[s,8]]
»
thread{expression[2s]event[2],expression[14s[s]]event[2],expression[16s[s][s[s]]]event[2],expression[9s[s][s[s]][s]]event[2]}
»
expression[s,6][expression[s,8]]
»
expression[expression[s,4][expression[s,6]],15][expression[s,8]]
»
expression[s,6][expression[s,8]][expression[expression[s,4][expression[s,6]],15][expression[s,8]]]
»
expression[expression[expression[expression[s,inputID1$_][x$_],inputID2$_][y$_],inputID3$_][z$_],inputID4$_](Echo[outputIDs];With[{outputIDs$=Table[(++expressionID$27625&)[],3],eventID$=(++eventID$27625&)[]},Sow[Join[EchoLabel[thread][Thread[expression/@{inputID1$s,inputID2$stripExpression[s[x$]],inputID3$stripExpression[s[x$][y$]],inputID4$stripExpression[s[x$][y$][z$]]}event[eventID$]]],Thread[event[eventID$]expression/@{outputIDs$〚1〛stripExpression[x$[z$]],outputIDs$〚2〛stripExpression[y$[z$]],outputIDs$〚3〛stripExpression[x$[z$][y$[z$]]]}]]];expression[expression[x$[z$],outputIDs$〚1〛][expression[y$[z$],outputIDs$〚2〛]],outputIDs$〚3〛]])