6.9 Foliations of Causal Graphs

At least in a causal invariant system, the structure of the causal graph is always the same, and it defines the causal relationships that exist between updating events. But in relating the causal graph to actual underlying evolution histories for the system, we need to specify how we want to foliate the causal graph—or, in effect, how we want to define “steps” in the evolution of the system.

As an example, consider the rule:

(This rule is probably not causal invariant, but this fact will not affect our discussion here.) The most obvious foliation for the causal graph basically follows our standard updating order:

But this is not the only foliation we can use. In fact, we can divide the graph into slices in any way, so long as the slices respect the causal relationships defined by the graph, in the sense that within a slice the causal relationships allow the events to occur in any order, and between successive slices events must occur in the order of the slices. And with these criteria, for example, another possible foliation is:

With the first foliation shown above, the hypergraphs from what we consider to be the first “few steps” in the evolution of the underlying rule are:

But the second foliation in effect has a different (and coarser) definition of “steps”, and with this foliation the first few steps would be:

When we discussed foliations in the context of string substitution systems, there were a number of simplifying features in our discussion. First, the underlying system fundamentally involved a linear string of elements. And second, the main causal graph we actually considered was a simple grid.

With a rule like

we can also get a simple grid causal graph (and this rule happens to be causal invariant). With the obvious foliation

the steps in the evolution of the underlying system from a particular initial condition are:

But given the grid structure of the causal graph, we can use the same diagonal slice method for generating foliations that we did in 5.14. And for example with the foliation

there are more steps involved in the evolution of the system:

But when the causal graph does not have such a simple structure, the definition of foliations can be much more complicated. When the causal graph at least in some statistical sense limits to a sufficiently uniform structure, it should be possible to set up foliations that are analogous to the diagonal slices. And even in other cases, it will often be possible to set up foliations that can be described, for example, by the kind of lapse functions we discussed in 5.14.

But there is one issue that can make it impossible to set up any reasonable “progressive” foliation of a causal graph at all, and that is the issue of loops. This issue is actually already present even in the case of string substitution systems (and even causal invariant ones). Consider for example the rule:

Starting from AA the multiway causal graph for this rule is:

But note here the presence of several loops. And looking at the states graph in this case

one can see where these loops come from: they are reflections of the fact that in the evolution of the system, there are states that can repeat—and where in a sense a state can return to its past.

Whenever this happens, there is no way to make a progressive foliation in which events in future slices systematically depend only on events in earlier slices. (In the continuum limit, the analog is failure of strong hyperbolicity [86]; loops are the analog of closed timelike curves (e.g. [75])) (Self-loops also cause trouble for progressive foliations by forcing events to happen repeatedly within a slice, rather than only affecting later slices.)

The phenomenon of loops is quite common in string substitution systems, and already happens with the trivial rule A  A. It also happens for example with a rule like:

Starting with ABA, this gives the causal graph

and has a states graph:

Loops can also happen in our models. Consider for example the very simple rule:

The multiway graph for this rule is:

This contains loops, as does the corresponding causal graph:

(Note that the issue discussed in 6.1 of when we consider states “identical” as opposed to “equivalent” can again arise here. There are similar issues when we consider finite-size systems where the whole state inevitably repeats—and where in principle we can define a cyclic analog of our foliations.)