Message Boards Message Boards

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

Posted 3 years ago

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.

POSTED BY: David Stephenson
9 Replies

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) hypergraph

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.

normal graph

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.

POSTED BY: Ruggero Valli

Good to hear your thoughts on the matter.

Allow me to start with your first point, which you eloquently phrased as:

"{x,y,x} is already an edge and subdividing it in {x,y} and {y,x} is meaningless".

On the contrary, since any hypergraph of any size can be accurately defined as an unordered set of its irreducible edges, without any loss of information, it is, in fact, your "already an edge" that is epiphenomenal to the fundamental definition of a hypergraph, not the other way around. The independent variable in the hypergraph is the set of irreducible edges that it is composed of, and the dependent variable is the length of any one particular edge in the hypergraph (an "n-nodes edge"), which will inevitably be composed of one or more irreducible edges.

I am, of course, speaking from a purely informational perspective.

From that perspective, and from the perspective of processing hypergraph information efficiently to both "grow" and store them according to one or more rule sets, there is simply no need whatsoever to deal with an "n-nodes edge". It isn't required for hypergraph storage, pattern matching, or substitution.

Perhaps an example is in order here. Where is the loss of information between defining a hypergraph as:

{{u,u,v},{v,u,y},{z,y,v}}

and defining that same hypergraph as the following set of irreducible edges:

  • {u,u}
  • {u,v}
  • {v,u}
  • {u,y}
  • {z,y}
  • {y,v}

There is, of course, no loss of information. Not only that, but the set is unordered by definition, which is highly fortuitous for pattern matching and substitution purposes (as I'm sure you can imagine).

So no, my friend, "subdividing it in {x,y} and {y,x}" is far from meaningless. Let's put that to bed right now.

Which brings us to your second point, which I (of course) agree with:

"Subdividing a pattern in(to) 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."

Perhaps not as eloquently phrased as your first point, but I know what you mean. To paraphrase: all symbolically equivalent letters in the LHS must match one, and only one, node in the target hypergraph.

I also agree with you that {x,y,x} should not match {u,v,w} for the very reasons you cited.

So okay, there is not, as I previously postulated, a "fundamental contradiction in the syntax". I have to admit that. You've convinced me. But I still find this "many to one" relationship between the nodes in the LHS and the target hypergraph completely arbitrary, unnecessary, counterproductive, and quite frankly, repugnant.

I mean, seriously, if the pattern hypergraph has twenty-three nodes, all intricately laid out, how can you justify it being "matched" by a hypergraph of only one node? Where, in the whole body of graph theory or substitution systems theory, is that justifiable?

And even if it were justifiable in some arcane graph theory tome somewhere, does that make it necessary to the study of the Wolfram Model? I don't believe so.

It would seem to me, therefore, that a much easier, more workable, more algebraically consistent, and empirically more flexible syntax would be defined by the single rule:

A match is found when all the nodes and irreducible edges of a "search" hypergraph is found to exist as a sub-hypergraph in the target.

Simple. Elegant.

Such a syntax would be exactly like the current Wolfram Model syntax, but for the important omission of the "{x,y} will match {x,x}" aberration.

More to say on the subject, but must eat. Interesting dialectic thus far. Kudos.

POSTED BY: David Stephenson

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 BY: Ruggero Valli

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 BY: David Stephenson

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 BY: Ruggero Valli

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:

  1. {x,y} will match both a {u,u} and a {u,v}.
  2. {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 uw), 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 BY: David Stephenson

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:

  1. {{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.
  2. {{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 BY: Ruggero Valli

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 BY: David Stephenson

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. enter image description here

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:

  1. The left hand side of a rule can be matched even if more than one label is attached to the same node.
  2. Initial conditions are chosen to be as simple as possible (e.g. one node connecting to itself is ok).
  3. If a new label appears on the right hand side, it must correspond to a new node.

I hope this helps

POSTED BY: Ruggero Valli
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract