o[x_][x_]x[x]
In[]:=
SKEvolveList[s[s][s][s[s]][s][s],30];
In[]:=
Extract[#,{First[Sort[Position[#,s[_][_][_],{0,Infinity},HeadsTrue]]]}]&/@SKEvolveList[s[s][s][s[s]][s][s],30];
In[]:=
Position[%,s[s][s][s[s]]]
Out[]=
{{1,1},{6,1}}
In[]:=
ee50=Extract[#,{First[Sort[Position[#,s[_][_][_],{0,Infinity},HeadsTrue]]]}]&/@SKEvolveList[s[s][s][s[s]][s][s],50];
In[]:=
Table[Select[Groupings[Table[s,n],Construct2],MatchQ[#,s[_][_][_]]&],{n,6}]
Out[]=
{{},{},{},{s[s][s][s]},{s[s[s]][s][s],s[s][s[s]][s],s[s][s][s[s]]},{s[s[s][s]][s][s],s[s[s[s]]][s][s],s[s][s[s][s]][s],s[s[s]][s[s]][s],s[s][s[s[s]]][s],s[s[s]][s][s[s]],s[s][s[s]][s[s]],s[s][s][s[s][s]],s[s][s][s[s[s]]]}}
In[]:=
Position[ee50,#]&/@Flatten[%91]
Out[]=
{{},{{5,1}},{},{{1,1},{6,1}},{},{},{},{},{},{},{},{},{}}
[[ For s alone, either terminates completely or is non-terminating ]]
In[]:=
SKFixedPointEvolveList[s[s[s[s][s]][s[s]][s][s][s][s]]];
In[]:=
Length[%]
Out[]=
895
In[]:=
Position[%87,s[s[s[s][s]][s[s]][s][s][s][s]],HeadsTrue]
Out[]=
{{1}}
s[s[s[s][s]][s[s]][s][s][s][s]]
If it has a copy, then it explodes....
Does an X exist s.t. : Given X and Nest[f,X,t], then X appears in it
1. Does the redex reproduce itself?
2. Does the redex appear in a particular evaluation sequence?
2. Does the redex appear in a particular evaluation sequence?
Generalized case: rewrite sequence repeats, but specific redex does not....
Self similarity in the MW graph ... and in MW causal graph
Self similarity in the MW graph ... and in MW causal graph
In[]:=
SKEvolveList[s[s][s][s[s]][s][s],10]
Out[]=
{s[s][s][s[s]][s][s],s[s[s]][s[s[s]]][s][s],s[s][s][s[s[s]][s]][s],s[s[s[s]][s]][s[s[s[s]][s]]][s],s[s[s]][s][s][s[s[s[s]][s]][s]],s[s][s][s[s]][s[s[s[s]][s]][s]],s[s[s]][s[s[s]]][s[s[s[s]][s]][s]],s[s][s[s[s[s]][s]][s]][s[s[s]][s[s[s[s]][s]][s]]],s[s[s[s]][s[s[s[s]][s]][s]]][s[s[s[s]][s]][s][s[s[s]][s[s[s[s]][s]][s]]]],s[s[s[s]][s[s[s[s]][s]][s]]][s[s[s]][s][s[s[s]][s[s[s[s]][s]][s]]][s[s[s[s]][s[s[s[s]][s]][s]]]]],s[s[s[s]][s[s[s[s]][s]][s]]][s[s][s[s[s]][s[s[s[s]][s]][s]]][s[s[s[s]][s[s[s[s]][s]][s]]]][s[s[s[s]][s[s[s[s]][s]][s]]]]]}
c[XXXX][x[z][y[z]]]
Tag expr tree...
In[]:=
LeafCount/@SKFixedPointEvolveList[s[s][s[s]][s[s[s[s]]]][s]]
Out[]=
{9,12,12,18,25,39,39,46,53,61,77,77,77,84,91,99,115,115,115,115,115,115,115,115,115,115,115,115,115}
LeafCount/@SKFixedPointEvolveList[s[s][s[s]][s[s[s[s]]]][s]]
In[]:=
Graph[MWCombinatorGraphMinimal[s[s][s[s]][s[s[s[s]]]][s],11,"LeftmostOutermost",NodeSizeMultiplier2.5],AspectRatio1]
Out[]=
In[]:=
Table[Graph[MWCombinatorGraphMinimal[s[s[s[s]]][s][s][s],t,"LeftmostOutermost",NodeSizeMultiplier.4],AspectRatio1],{t,15}]
Out[]=
,
,
,
,
,
,
,
,
,
,
,
,
,
,
In[]:=
Table[Graph[MWCombinatorGraphMinimal[s[s[s[s]]][s][s][s],t,NodeSizeMultiplier.4],AspectRatio1],{t,15}]
Out[]=
,
,
,
,
,
,
,
,
,
,
,
,
,
,
Proof of Non-Termination
Proof of Non-Termination
Recursion Testing
Recursion Testing
Causal Graph
Causal Graph
Each piece is an expression fragment:
In this case, the output from an event gets copied many times, to be used in many subtrees....
Non-Termination Test
Non-Termination Test
If any subexpression X at any stage has the feature that the evolution from X contains X then it recurses.....
On the initial state, all possible subtrees of the initial expressions are used.
Most promising...
Most promising...
Simpler case:
Simpler case:
Evaluation Strategies [[[ Quite a lot here is wrong ! ]]]
Evaluation Strategies [[[ Quite a lot here is wrong ! ]]]
(Could also label the part numbers)
Position sorts by the “ends” of the parts in the left-right prettyprint... [i.e. depth-first scan] Position is determining the order by a depth first scan.
/. : what is the order?
What does /. do?
For any list of matches, there is a partial order of which ones can be done.....
[ You can always do one at a time, but how many do you do ]
[ You can always do one at a time, but how many do you do ]
Leftmost outermost
Leftmost outermost
Leftmost innermost
Leftmost innermost
Innermost leftmost
Innermost leftmost
Rightmost outermost
Rightmost outermost
/. case
/. case
test whether pref is a prefix in list....
“Consistent deepest”
Assume Map has a traversal order; some things will drilldowns within a given expr; others will be different expressions......
/. is “consistent shallowest” ??
Collection
Collection
Position order: (a bit like Replace)
works like this:
Leftmost innermost
“One gulp” strategies so far; could also have drilldown strategies
“One gulp” strategies so far; could also have drilldown strategies
I.e. given that one rewrote a subexpression, one could drill down onto that subexpression further, rather than restarting at the top.....
Comparison between replacement and evaluation
Comparison between replacement and evaluation
Replacement scans the expression at each step, and picks out the parts that should be updated.
Evaluation takes a part, evaluates it, and then goes on evaluating that part until it is finished.
Evaluation takes a part, evaluates it, and then goes on evaluating that part until it is finished.
This maintains an “evaluation frame” from step to step....
SMP
SMP