PRELIMINARY VERSION

Confluence and Causal Invariance

Max Piskunov (Wolfram Research)

Note: Adapted from SetReplace 18cae81. See the latest version on GitHub. You need the SetReplace paclet to evaluate the code from this Bulletin. Run PacletInstall["SetReplace"]; << SetReplace`; to install and import.


Introduction

There are claims made in the Wolfram Physics Project about the equivalence of confluence and causal invariance. This bulletin demonstrates that some of these claims are not correct. For example, consider the glossary on the project’s website, which as of October 30, 2020, says:

Causal Invariance: A property of multiway graphs whereby all possible paths yield the isomorphic causal graphs. When causal invariance exists, every branch in the multiway system must eventually merge. Causal invariance is a core property associated with relativistic invariance, quantum objectivity, etc. In the theory of term rewriting, a closely related property is confluence. In a terminating system, causal invariance implies that whatever path is taken, the “answer” will always be the same.

Confluence: A simplified form of causal invariance considered in term rewriting systems such as ones that reach fixed points.

However, the glossary does not explicitly define confluence, so we are going to use the standard definition from the theory of rewriting systems:

A state a is deemed confluent if, for all pairs of states b, c that can be reached from a, there exists a state d that can be reached from both b and c. If every state in the system is confluent, the system itself is confluent.

We can summarize the statements above with the following definitions:

A Wolfram model evolution is called causal invariant if and only if the causal graphs for singleway evolutions with any possible event ordering functions are isomorphic.

Note that the definition above is only meaningful for terminating systems (i.e. the systems that always reach a "FixedPoint", a state during the evolution where no more matches can be made to its expressions).

We can then define confluence as:

A Wolfram model evolution is called confluent if and only if any pair of partial singleway evolutions starting from a particular state can be continued in such a way as to reach isomorphic final states.

In what follows, we will demonstrate that causal invariance is not equivalent to confluence, neither of them implies the other, and the two statements made above are false:

When causal invariance exists, every branch in the multiway system must eventually merge.

In a terminating system, causal invariance implies that whatever path is taken, the “answer” will always be the same.

We will not make any comments in this note about the physics claims made above.

Before we get to specific examples, it’s essential to understand the fundamental difference between these two properties. Causal invariance has to do with symmetries between evolution branches of expressions-events graphs. It requires that, even though the branches operate on different expressions, they have the same causal structure:

Causal invariance

On the other hand, confluence has to do with the symmetries between expressions’ contents. It requires that particular states from different branches are isomorphic as hypergraphs, regardless of the causal structures that lead to them:

Confluence

Confluence !=> Causal Invariance

Consider the following system:

confluentRule
&#10005

confluentRule = {{1}, {1, 2}} -> {{1, 2}, {2}};
confluentInit = {{1}, {1, 2}, {2, 3}, {1, 3}};

This system is confluent, as any partial evolution, if continued, will always terminate at the final state isomorphic to {{1, 2}, {2, 3}, {1, 3}, {3}}:

ResourceFunction
&#10005

ResourceFunction["MultiwaySystem"][
 "WolframModel" -> {confluentRule}, {confluentInit}, 2, "StatesGraph",
  VertexSize -> 1]

However, this system is not causal invariant. We can generate two non-isomorphic causal graphs by using different event ordering functions, which contradicts the definition above:

IsomorphicGraphQ @@Echo@(WolframModel
IsomorphicGraphQ @@Echo@(WolframModel
&#10005

IsomorphicGraphQ @@ 
 Echo@(WolframModel[confluentRule, confluentInit, Infinity, 
       "EventOrderingFunction" -> #][
      "CausalGraph"] & /@ {"OldestEdge", "NewestEdge"})

Therefore, confluence does not imply causal invariance.

Note that the "CausalInvariantQ" property of MultiwaySystem checks for confluence despite its name:

ResourceFunction
&#10005

ResourceFunction["MultiwaySystem"][
 "WolframModel" -> {confluentRule}, {confluentInit}, 2, \
"CausalInvariantQ"]

Causal Invariance !=> Confluence

Consider the following causal invariant system:

causalInvariantRule
&#10005

causalInvariantRule = {{1, 2}, {2, 1}} -> {{1}};
causalInvariantInit = {{1, 2}, {2, 1}, {1}};

To see that it’s causal invariant, note that the multiway system in this case only has two events:

WolframModel
&#10005

WolframModel[causalInvariantRule, causalInvariantInit, Infinity, 
  "EventSelectionFunction" -> 
   "MultiwaySpacelike"]["ExpressionsEventsGraph", 
 VertexLabels -> Automatic]

These two events correspond to two different singleway evolutions terminating at states {{1}, {1}} and {{1}, {2}}, respectively:

WolframModel
&#10005

WolframModel[causalInvariantRule, causalInvariantInit, Infinity, 
    "EventOrderingFunction" -> #]["ExpressionsEventsGraph", 
   VertexLabels -> Placed[Automatic, After]] & /@ {"RuleOrdering", 
  "ReverseRuleOrdering"}

These evolutions yield isomorphic causal graphs, which are composed of a single vertex with no edges, implying that this system is causal invariant by definition:

IsomorphicGraphQ @@Echo@(WolframModel
IsomorphicGraphQ @@Echo@(WolframModel
&#10005

IsomorphicGraphQ @@ 
 Echo@(WolframModel[causalInvariantRule, causalInvariantInit, 
       Infinity, "EventOrderingFunction" -> #][
      "CausalGraph"] & /@ {"RuleOrdering", "ReverseRuleOrdering"})

It is not, however, confluent, because the final states in these two evolutions are not isomorphic, and the evolutions terminate after these states are reached:

ResourceFunction
&#10005

ResourceFunction["MultiwaySystem"][
 "WolframModel" -> {causalInvariantRule}, {causalInvariantInit}, 2, \
"StatesGraph", VertexSize -> .7]

Therefore, causal invariance does not imply confluence.

Note that the "CausalInvariantQ" property of MultiwaySystem returns False in this case:

ResourceFunction
&#10005

ResourceFunction["MultiwaySystem"][
 "WolframModel" -> {causalInvariantRule}, {causalInvariantInit}, 2, \
"CausalInvariantQ"]

Future Research

It would be interesting to investigate the systems exhibiting these properties in different combinations. For example, systems that don’t exhibit multiway branching at all do satisfy both of these conditions. One can also consider systems in which causal-graphs isomorphism is equivalent to states isomorphism by construction—for example, classical sequential growth models of causal sets. It might be possible to generalize this to include more classes of systems. We could also enumerate (#57) simple rules and determine how many of them exhibit just one of these properties, both or neither.

To do that, we need to implement tests for both confluence (#59, #477) and causal invariance (#486) in SetReplace.

We will also need to generalize the definition of causal invariance to non-terminating Wolfram models (#487).

It will be interesting to investigate other similar properties. For example, one can investigate a stronger version of confluence:

  1. Consider any infinite singleway evolution of a system.
  2. Consider another finite partial singleway evolution.
  3. If any such finite evolution can be continued in such a way as to reach one of the states from the infinite evolution, we define the system as “super”-confluent (#478).

Posted in: Physics

×