[Probably excised] A Fully Recursive Symbolic View | The Naming of Nodes
[Probably excised] A Fully Recursive Symbolic View | The Naming of Nodes
Consider the rule discussed earlier:
{{x,y}}{{y,z},{z,x}}
Each time this rule is applied, it generates two copies of an element z. Pretty much all we have said before about an element like this is that it needs to be new. And indeed, for most of what we will do, that is all we have to say. But there are some subtle issues that will come up in Section 6 for which it is helpful to have a more detailed way to look at what it means to generate a new element.
From the point of view of computer science, the obvious approach is for the rule to essentially just create a new free variable z every time the rule is used:
From the point of view of computer science, the obvious approach is for the rule to essentially just create a new free variable z every time the rule is used:
{{x_,y_}}Module[z,{{y,z},{z,x}}]
Each instance of the free variable is by definition given a globally unique name or label, that is used to identify the new element (“lexically scoped”) and can for example serve as a label for a node in a hypergraph. (In a practical implementation, the name could come from a globally maintained counter, be a UUID, etc.)
But one can also imagine another approach that is in some ways purer. Instead of just assigning each new element an (essentially arbitrary) new name, construct a name for it, for example by setting up the rule as:
But one can also imagine another approach that is in some ways purer. Instead of just assigning each new element an (essentially arbitrary) new name, construct a name for it, for example by setting up the rule as:
z:{{x_,y_}}{{y,z},{z,x}}
Imagine we start with {{1,2}}. Then when we apply this rule once we get:
Out[]=
{{2,{{1,2}}},{{{1,2}},1}}
Instead of arbitrarily generating a name like 3 for z, and getting {{2, 3}, {3, 1}}, we are using our result so far to recursively derive the “name” {{1,2}} to use for z.
When we use the rule again, it is applied twice: once on the relation that we might have called {2,3}, and once on {3,1}. Each application of the rule must generate a fresh new z. But with our recursive definition each instance of z is derived from previous results: with one of them having the “name” {2,{{1,2}}} and the other {{{1,2}},1}. The result of using the rule a second time can therefore be written:
When we use the rule again, it is applied twice: once on the relation that we might have called {2,3}, and once on {3,1}. Each application of the rule must generate a fresh new z. But with our recursive definition each instance of z is derived from previous results: with one of them having the “name” {2,{{1,2}}} and the other {{{1,2}},1}. The result of using the rule a second time can therefore be written:
Out[]=
{{{{1,2}},{{2,{{1,2}}}}},{{{2,{{1,2}}}},2},{1,{{{{1,2}},1}}},{{{{{1,2}},1}},{{1,2}}}}
If we indicate each top-level element with a frame, this becomes:
In[]:=
Map[Framed[#,BackgroundGrayLevel[.98],FrameStyleLightGray]&,Nest[SubsetReplace[#,z:{{x_,y_}}->Sequence[{y,z},{z,x}]]&,{{1,2}},2],{2}]
Out[]=
We can represent it as a graph:
In[]:=
Graph[Rule@@@Map[Framed[Text[StandardForm@#],BackgroundGrayLevel[.98],FrameStyleLightGray]&,Nest[SubsetReplace[#,z:{{x_,y_}}->Sequence[{y,z},{z,x}]]&,{{1,2}},2],{2}],VertexLabelsAutomatic,PerformanceGoal"Quality",GraphLayout"TutteEmbedding",AspectRatio1/3]
Out[]=
But in terms of the structure of the graph---which is all we normally care about---only the identities of the nodes are important; the elaborate names we now have for them are irrelevant.
But it is still instructive to continue thinking about building up results recursively. Consider the rule:
But it is still instructive to continue thinking about building up results recursively. Consider the rule:
[[[[[ improve these graphics. XXXXX ]]]]]
w:{{x_,y_},{x_,z_}}
w:{{x,y},{x,z}}{{x,z},{x,w},{y,w},{z,w}}
where now for presentation purposes we have added some annotations. Start this rule from the double self-loop {{1,1},{1,1}} and after one step we get: [[[ need to show with 1s ]]]]
Out[]=
[[[ Replace with • .... very minimal symbolic representation, with no numbers, unique identifiers, etc. ]]]]
In[]:=
MapIndexed[Magnify[#,1.2^-(First[#2]-1)]&,NestList[SubsetReplace[#,w:{{x_,y_},{x_,z_}}:>Sequence[{x,z},{x,w},{y,w},{z,w}]]&,{{•,•},{•,•}},3]]
Out[]=
But in a sense, there is no reason for the literal 1s in the initial condition; one could just as well replace these by the structure { }, or just by • (in analogy to combinators or to recursive constructions with sets). Now the first 3 steps of running the rule give (with color-coding for clarity):
Out[]=
As trees these become: [[[ color code the levels to agree with the tagging above ]]]
In[]:=
LayeredGraphPlot[ExpressionGraph[#],AspectRatio1/2]&/@NestList[SubsetReplace[#,p:{{x_,y_},{x_,z_}}:>Sequence[{x,z},{x,p},{y,p},{z,p}]]&,{{•,•},{•,•}},4]
Out[]=
But in our normal graph representation---not showing the names---these are just:
In[]:=
HypergraphPlot[Map[Hash,#,{2}],ImageSize120]&/@NestList[SubsetReplace[#,p:{{x_,y_},{x_,z_}}:>Sequence[{x,z},{x,p},{y,p},{z,p}]]&,{{•,•},{•,•}},5]
Out[]=
But in a sense the identity of each node is defined by its history, which we can in principle recursively show---with each graph in effect recursively containing the previous one as labels for its nodes:
Out[]=
From a computer science point of view, one can think of this approach as specifying nodes in terms of chains of pointers. In practice one could also imagine recursively naming each node with a hash of its history (as in Git or a blockchain). Both in practice and in principle, a significant feature of this approach is that it is completely local and distributed: everything we ever need to know about any element is directly associated with the element, and there is no need for anything that might be considered global coordination.
How we think of assigning names will almost always be irrelevant to studying what our models do. But with any particular recursive scheme, there can potentially be corner cases in which it makes a difference. Consider for example the rule:
How we think of assigning names will almost always be irrelevant to studying what our models do. But with any particular recursive scheme, there can potentially be corner cases in which it makes a difference. Consider for example the rule:
If we always generate new elements with arbitrary independent names, this gives:
But with the particular recursive scheme for generating names described here, we get:
The reason for the difference is that with this recursive scheme, there can be one lineage that traces through the {x,y} on the left-hand side of the rule, and another that goes through the copy of {x,y} on the right-hand side---causing what might otherwise be two different elements to be assigned the same name, and therefore be conflated as having the same identity.
This particular phenomenon does not occur for rules without repeated relations. It also does not occur if the recursively recorded history has markers that indicate where different pieces of content come from inside a rule. In most of what follows, we will ignore the details of how new elements are named, simply assuming that it is done so collisions are avoided. (And even the particular recursive scheme described here will automatically achieve this for essentially all but the most trivial rules we discuss.) However, it will be useful to bear in mind the possibility of recursive element naming, both for the conceptual purity of its structure, and for the way it informs certain details about enumerating all possible histories that we will discuss in Section 6.
This particular phenomenon does not occur for rules without repeated relations. It also does not occur if the recursively recorded history has markers that indicate where different pieces of content come from inside a rule. In most of what follows, we will ignore the details of how new elements are named, simply assuming that it is done so collisions are avoided. (And even the particular recursive scheme described here will automatically achieve this for essentially all but the most trivial rules we discuss.) However, it will be useful to bear in mind the possibility of recursive element naming, both for the conceptual purity of its structure, and for the way it informs certain details about enumerating all possible histories that we will discuss in Section 6.
MORE
MORE
Previous version
Previous version
Representation
Representation
More
More
Another
Another