Message Boards Message Boards

GROUPS:

Causal Invariance versus Confluence

Posted 1 month ago
466 Views
|
4 Replies
|
9 Total Likes
|

I have a question that has been bothering me since 2002: what is the full relationship between causal invariance (all causal graphs are isomorphic independent of update order) and global confluence (all branch pairs eventually merge). As is stated many places, confluence is a necessary condition for causal invariance, but can be easily seen to not be sufficient.

I ask since things like CausalInvariantQ seem to be checking confluence instead, and I've heard you say things on livestream like "because this rule contains inverses, it is causal invariant," however from working through some examples it seems that containing inverses only implies confluence. Similarly the Knuth-Benedix completion only produces confluent systems, and not causal invariant ones. On the flipside, from reading Jonathan's paper on GR, it seems clear that you often truly want causal invariance.

I've read all sections of NKS and the WPP introduction several times, and I'm not 100% on this. Does anyone have anyplace that can help clear this up?

4 Replies
Posted 1 month ago

If it's any consolation, I'm confused as well. The only conclusion I can make is that the system being non-overlapping (i.e., there is no branching at all) implies both, but I don't think neither confluence nor causal invariance implies each other.

Any thoughts, @Jonathan Gorard?

My counterexamples are in this notebook:

Posted 1 month ago

Even cleaner than mine! I agree that they are philosophically similar in-so-far as both prevent the creation of unrectifiably divergent update histories, but it seems only causal invariance guarantees the creation of a single thread of history.

Just for completeness, since my example is less constructed, here is another case showing confluence doesn't imply causal invariance. In this case, the rule contains exact inverses, so it is confluent (indeed by applying the second rule repeatedly, you can always return to the single loop state). However (and here is the reason I didn't post the example first), one can show that the causal graphs generated are all non-isomorphic, and indeed, one can read off exactly the sequence of rules applied by taking the unique longest path in the graph (the one that connects all update events in order) and then counting the in-degree (in-degree 1 -> first rule, in-degree 2 -> second). It takes an argument now (assume there is an isomorphism, look at a neighborhood of the image of the first point in one graph in the other derive a contradiction unless it is also the first point on the second and induct) to show that this proves that not only are they not always causal invariant, but indeed no two distinct update orders ever produce isomorphic graphs.

Posted 1 month ago

This is actually a more subtle case because it depends on whether or not we identify isomorphic states during the evolution.

If we do identify them, and we keep random walking through the system, we would be reconstructing different subgraphs of the same causal graph. I.e., take a look at what MultiwaySystem does for this system:

ResourceFunction["MultiwaySystem"][
 "WolframModel" -> {{{0, 0}} -> {{0, 1}, {1, 1}}, {{0, 1}, {1, 
      1}} -> {{0, 0}}}, {{{0, 0}}}, 10, "CausalGraphStructure"]

Multiway causal graph

One can imagine the single-way evolution paths uncovering different parts of that same graph. That of course does not mean we will always get the same graph in the limit of steps going to infinity, but one could get the same graph if one chooses a particular updating sequence after any number of arbitrary events. Note that to make this graph, one had to do an isomorphism between different steps and identify different edges with each other, which WolframModel does not do.

Posted 1 month ago

Indeed---as I said, your examples are more more to the heart of the matter! The isomorphism class trick seems to just be a bandaid to me since if you just extend the rule I stated to throw off "dust" of disconnected hyper-edges with each update, this keeps track up update steps and explicitly breaks the isomorphism class fix while keep the exact same causal graphs as before (even to the degree the same causal graphs are generated for the same seed by your code ;) ). I'd be willing to bet you can pretty generically break isomorphism classes without breaking confluence.

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