# Question about a quoted expression: {x,y} matches {x,x} ?

Posted 3 months ago
707 Views
|
9 Replies
|
0 Total Likes
|
 Hello everyone,I find that I have gotten myself stuck on what I think was a Stephen Wolfram quote, the specifics of which escape me, but which can be roughly paraphrased as: "..and remember, {x,y} in the rule will match an {x,x} in the hypergraph.." I can't locate exactly where I might have read that (I've looked}, but I seem to remember that it made little sense to me at the time, and makes even less sense to me now.If an {x,y} in the rule will match an {x,x} in the hypergraph, then surely an {x,y,z} in the rule should match an {x,x,x} in the hypergraph. And by extension, also a {y,y,y}. And even a {z,z,y}.I mean, doesn't that imply, if not explicitly state, that any string of vertices in the rule will match any string of vertices in the hypergraph? As in, WTF? (excuse my French)So at the time, I dismissed it as a "Wolfram compatibility" issue, and continued investigating Wolfram Physics Model rules, hypergraphs, and multi-way graphs. But the problem cropped up again.Specifically, there is a rule that Stephen Wolfram (et al) mentions in Section 4.1 "Recognizable Geometry", of his white paper entitled, "A Class of Models with the Potential to Represent Fundamental Physics".As rules go, it's a beaut. When requisitely iterated, it is claimed to resemble a spatial "orbifold" - just what the doctor ordered for someone wanting to build a spatial Universe.Only thing is, as far as I can tell, the rule doesn't seem to work. It dead ends before the second iteration.The rule is: {{x,x,y},{x,z,u}}->{{u,u,v},{v,u,y},{z,y,v}}If we start with the left-hand side as the Initial Condition, as is the custom, then the first iteration will produce the right-hand side (of course) - but only the right-hand side. So far, so good.But then, where is the {{x,x,y},{x,z,u}} in {{u,u,v},{v,u,y},{z,y,v}} ??There isn't one. It dead-ends.If {{u,u,v},{v,u,y},{z,y,v}} is broken out into its component edges, then we can see that:{u,u} is matched by the {x,x} edge in the rule, and{u,v} is matched by the {x,y} edge in the rule, and{v,u} is not matched, and{u,y} is matched by the {x,z} edge in the rule, and{z,y} is not matched, and{y,v} is NOT matched by the {z,u} edge in the rule. - because the v is NOT unique.There doesn't appear to be any other possible permutations.So I guess my question is: If it is indeed true that the Wolfram Physics Model considers any {x,x} in the hypergraph to be "matched" by any {x,y} in the rule, then doesn't that essentially negate using unique symbols for vertices at all?If not, then what exactly are the limitations of this particular.. methodology?Any response would be appreciated.BTW, just so you know, I don't currently own a copy of Mathematica. All my current investigations are done using C++ and T-SQL.Thanks in advance.
9 Replies
Sort By:
Posted 2 months ago
 Hello, sorry for the late reply, I hope it could still be of use.I think that the problem with your reasoning stands on the assumption that the initial conditions used for the rule {{x,x,y},{x,z,u}}->{{u,u,v},{v,u,y},{z,y,v}} are exactly {{x,x,y},{x,z,u}}, with $x \neq y \neq z \neq u$, because this is not the simplest initial condition for that rule. I think (please correct me if I'm wrong on this) that the examples of rule evolution found on the catalogue always start from the simplest initial condition to which a rule is applicable.To clarify my point, let me talk about the first rule shown on the page you linked (Recognizable Geometry), namely {{x, y}} -> {{y, z}, {z, x}}.I copy here the first steps of evolution reported on the page. As you can see, the initial condition is one single node connected to itself. The single node is doing the double job of being both x and y at the same time. Obviously, this initial condition is the simplest to possible state to which the rule is applicable. So, in the first step there is only node 1 (labelled both x and y) connected to itself. The initial state can therefore be written as {{1,1}}.You can apply the rule and see that in the right hand side there is a new node, z, which is different from node 1, let's call it node 2. Now {y,z} means there is an edge between node 1 and node 2, and {z,x} means there is an edge between node 2 and node 1. Hence the second step, as shown in the picture, can be written {{1,2}{2,1}}Let's get now to the rule you asked of: {{x,x,y},{x,z,u}}->{{u,u,v},{v,u,y},{z,y,v}}.You can see that the simplest initial condition is the one in which x,y,z and u are different labels for the very same node (let's call it node 1). The starting point will be the hypergraph {{1,1,1},{1,1,1}}. One node with two triple connections from the node to itself.In the right hand side there is the new letter v, therefore a new node must appear, let's call it node 2. After applying the rule you get {{u,u,v},{v,u,y},{z,y,v}}, but $x=y=z=u=1$, so the second step looks like {{1,1,2}, {2,1,1}, {1,1,2}}.Now you see that you can apply the rule again. Just stick the labels x and z to node 1 and y and u to node 2. With this substitution you can write the second step as, for example, {{x,x,y}, {y,x,x}, {x,z,u}}, to which you can apply the rule and go on with the computation.To summarize, the way to apply the rules, as I understand it, is: The left hand side of a rule can be matched even if more than one label is attached to the same node. Initial conditions are chosen to be as simple as possible (e.g. one node connecting to itself is ok). If a new label appears on the right hand side, it must correspond to a new node. I hope this helps
Posted 1 month ago
 Thanks for the reply. I was beginning to think I was a ghost.So will an {x,x} in the LHS of a Wolfram-compatible rule match a {u,v} in the target hypergraph, assuming that u is distinct from v?BTW, your rule "3" requires amendment. To wit:"If a new label appears on the left hand side" s/b "If a new label appears on the right hand side".I have been called a grammar Nazi. Recently. Guilty as charged.
Posted 1 month ago
 Hi,I don't think that the example you made would work. If you find {x,x} on the LHS or RHS of a rule, it can only match to a node connected to itself, not to {u,v} where $u \neq v$. The reverse instead would work, meaning that if you find {u,v} in the LHS of a rule, it would match a {x,x} in the graph.I can make some examples to clarify: {{x,y}}->{{x, y}, {y, z}} means: take two nodes (not necessarily different) connected by an arc. Create a third node and connect the second to the third. {{x,x}}->{{x, x}, {x, z}} means: take a node connected to itself. Create a second node and connect the first to the second. Rule 1 can match anything that rule 2 can match, but the opposite is not true.If what you say were true, the two rules would be exactly equivalent, and the way of writing the rules would be extremely redundant.Actually you could write every LHS using only one letter: {{x,y,z}{y,y,z}} could be written equivalently as {{x,x,x}{x,x,x}} and they would match the same things!BTW, I edited my previous comment with your amendment. Thank you. It is sad to keep confusing left and right :(
Posted 1 month ago
 Actually, I wasn't trying to "make" anything in my last post, I simply asked a single question, to which you gave a wonderfully complete answer. So thank you for that. What fun.So the pattern-matching rules for the LHS of a Wolfram-compatible rule, as we have previously discussed and agreed upon, are: {x,y} will match both a {u,u} and a {u,v}. {x,x} will only match a {u,u}. So where does that leave the LHS interpretation of something like:{x,y,x} ?Specifically, will the above match {u,v,w} ? If it does, then it breaks rule 2 (because u â‰  w), and if it doesn't, then it breaks rule 1 ( {x,y}->{u,v}, {y,x}->{v,w} ). A fundamental contradiction in the syntax.Apparently.
Posted 1 month ago
 I think that {x,y,x} does not match {u,v,w}, because of the first reason you mentioned. If it does, then it breaks rule 2 (because u â‰  w) I don't understand your second point, tough. if it doesn't, then it breaks rule 1 ( {x,y}->{u,v}, {y,x}->{v,w} ). could you clarify how rule 1 contradicts the statement "{x,y,x} does not match {u,v,w}"?
Posted 1 month ago
 Yes, understanding is "tough" (haughty muffled chortle).. ;)Because, according to rule 1: the {x,y} edge in the {x,y,x} pattern matches the {u,v} in the target, and the {y,x} edge in the {x,y,x} pattern matches the {v,w} in the target. Thus, the two edges of the pattern hypergraph (and there are only two) have been matched.Thus, according to rule 1: {x,y,x} should match {u,v,w}.
Posted 1 month ago
 Ok, I think I understand your issue, hopefully.Firstly, we are talking about hypergraphs not regular graphs. In regular graphs, an edge is a connection between two nodes, for example {u,v} means that node u is connected by an edge to node v. With hypergraphs instead, an edge is a connection between any number of nodes. For example {u,v,w} is a connection between the three nodes u,v and w. In the same way you can picture a 2-nodes edge as a line connecting the two nodes, you can imagine that a 3-nodes edge is some kind of surface on which the three nodes lay. And a 4-nodes edge like {u,v,w,z} is a 3-dimensional hypersurface, etc. [Technical introduction]I am sorry for this lengthy and perhaps unnecessary explanation, but I felt like there was some confusion, when you wrote "the {x,y} edge in the {x,y,x} pattern", because {x,y,x} is already an edge and subdividing it in {x, y} and {y, x} is meaningless.The second remark I would like to make is that even if you had two different edges, for example {{x,y}{y,x}} in the LHS of a rule, it still wouldn't match the pattern {{u,v}{v,w}}. The reason is that patterns must be matched as a whole. Subdividing a pattern in smaller elements and matching these individually doesn't guarantee that the whole pattern matches. This is essentially the point of using a repeated letter when writing a rule.Consider the rule {{x,y,z}{x,x}} -> {{u,v,x}{x}}. Every time the letter x appears, it must represents the same node. x,y and z could all be labelling the same node. u and v appear only on the RHS, so they must be new nodes, different from any other and also $u \neq v$. I suggest you look at the first two parts of the technical introduction. The things that we are discussing here are not always stated explicitly, but there are many examples from witch they can be inferred.
Posted 1 month ago
Posted 1 month ago
 I must disagree with your first point. When you subdivide an hypergraph into a set of 2-node edges, there is indeed loss of information.Consider the hypergraph {{1,2,3}{3,4,5}} in the first picture. (Taken form here) It can be subdivided into the following set: {1,2} {2,3} {3,4} {4,5} Consider instead the hypergraph {{1,2}{2,3}{3,4}{4,5}} in the second picture.Its decomposition is the same, but the two hypergraphs are not isomorphic, hence there was loss of information during the decomposition process. Also from a pattern matching perspective, it is impossible to determine if a pattern matches an hypergraph, when given only its decomposition. For example, the pattern {{x,y,z}{z,u,v}} matches the first graph but not the second one, while {{x,y}{y,z}{z,u}{u,v}} matches the second one but not the first.Regarding you second point, I am not aware of any reason against your proposal, but I am not an expert of graph theory, nor I have knowledge of Wolfram's motives when he formulated the theory.All I can say is that your idea seems good to me. I hope that someone with better knowledge on the subject will comment on that.
Community posts can be styled and formatted using the Markdown syntax.