6.4 Testing for Causal Invariance

Testing for causal invariance in our models is similar in principle to the case of strings. Failure of causal invariance is again the result of branch pairs that do not resolve. And just like for strings, it is possible to test for total causal invariance by determining whether a certain finite set of core branch pairs resolve. (Again in analogy with strings, the finiteness of this set is a consequence of the finiteness of the hypergraphs involved in our rules.)

The core branch pairs that we need to test represent the minimal cases of overlap between left-hand sides of rules—or, in a sense, the minimal unifications of the hypergraphs that appear. For the two hypergraphs

there are two possible unifications (where the purple edge shows the overlap):

For a single rule with left-hand side

the core branch pairs arise from unifications associated with the possible self-overlaps of this small hypergraph. Representing two copies of the hypergraph as

the possible unifications are:

In the case of strings, all that matters is what symbols appear within the unification. In the case of hypergraphs, one also has to know how the unification in effect “attaches”, and so one has to distinguish different labelings of the nodes.

Starting from the unifications, one applies the rule to find what branch pairs can be produced. These branch pairs form the core set of branch pairs for the rule—and determining whether the rule is causal invariant then becomes a matter of finding out whether these branch pairs resolve.

In the case of

the application of the rule to the unifications above yields the following 58 core branch pairs:

Running the rule for one step yields resolutions for 6 of these branch pairs:

Running for another step resolves no additional branch pairs.

Will the rule turn out to be causal invariant in the end? As a comparison, consider the rule

discussed in the previous subsection. This rule starts with 14 core branch pairs:

After one step, 6 of them resolve:

Then after another step the 8 remaining ones resolve, establishing that the rule is indeed causal invariant:

But in general there is no upper bound on the number of steps it can take for core branch pairs to resolve. Perhaps the fact that so many additional branch pairs are generated at each step in the rule {{x,y},{x,z}}{{x,z},{x,w},{y,w},{z,w}} makes it seem unlikely that they will all resolve, but ultimately this is not clear.

And even if the rule does not show total causal invariance, it is still perfectly possible that it will be causal invariant for the particular set of states generated from a certain initial condition. However, determining this kind of partial causal invariance seems even more difficult than determining total causal invariance.

Note that if one looks at all 4702 2₂  3₂ rules, the largest number of core branch pairs for any rule is 554; the largest number that resolve in 1 step is 132, and the largest number that remain unresolved is 430.