Function Repository Resource:

# CausalInvariantQ

Determine whether a given multiway system is causal invariant

Contributed by: Jonathan Gorard
 ResourceFunction["CausalInvariantQ"][rules,init,n] returns True if the multiway system with the specified rules is causal invariant after n steps, starting with initial conditions init, and False otherwise. ResourceFunction["CausalInvariantQ"][rules→sel,init,n] uses the function sel to select which of the events obtained at each step to include in the evolution.

## Details and Options

Rules can be specified in the following ways:
 {"lhs1"->"rhs1",…} string substitution system {{l11,l12,…}->{r11,r12,..},…} list substitution system SubstitutionSystem[rules] string or list substitution system CellularAutomaton[rules] cellular automaton system "type"→rules system of the specified type assoc system with properties defined by assoc
Supported rule types include:
 "StringSubstitutionSystem" rules given as replacements on strings "ListSubstitutionSystem" rules given as replacements on lists "CellularAutomaton" rules given as a list of CellularAutomaton rule specifications "WolframModel" rules given as replacements on hypergraphs
When rules are specified by an explicit association, the following elements can be included:
 "StateEvolutionFunction" gives the list of successors to a given state "StateEquivalenceFunction" determines whether two states should be considered equivalent "StateEventFunction" gives the list of events applicable to a given state "EventApplicationFunction" applies an event to a given state "EventDecompositionFunction" decomposes an event into creator and destroyer events for individual elements "SystemType" system type name "EventSelectionFunction" determines which events should be applied to a given state
The event selection function sel in ResourceFunction["CausalInvariantQ"][rulessel,] can have the following special forms:
 "Sequential" applies the first possible replacement (sequential substitution system) "Random" applies a random replacement {"Random",n} applies n randomly chosen replacements "MaxScan" applies the maximal set of spatially-separated replacements (strings only)
The initial condition for ResourceFunction["CausalInvariantQ"] is a list of states appropriate for the type of system used.
ResourceFunction["CausalInvariantQ"][rules,"string",] is interpreted as ResourceFunction["CausalInvariantQ"][rules,{"string"},].
ResourceFunction["CausalInvariantQ"] accepts both individual rules and lists of rules, and likewise for initial conditions.
Options for ResourceFunction["CausalInvariantQ"] include:
 "IncludeStepNumber" False whether to label states and events with their respective step numbers "IncludeStateID" False whether to label states and events with unique IDs
Causal invariance is a property of multiway systems in which all branches of evolution history yield causal networks that are isomorphic as acyclic graphs.
In the case of an abstract rewrite system it is a sufficient condition for confluence (or the Church-Rosser property), and in the case of a WolframModel it is equivalent to Lorentz covariance.

## Examples

### Basic Examples (4)

Determine causal invariance for two string substitution systems:

 In[1]:=
 Out[1]=
 In[2]:=
 Out[2]=

Different event selection functions can lead to different causal invariance behavior:

 In[3]:=
 Out[3]=
 In[4]:=
 Out[4]=

CausalInvariantQ can handle Wolfram Models and other system types:

 In[5]:=
 Out[5]=
 In[6]:=
 Out[6]=
 In[7]:=
 Out[7]=

Preventing identical states from being merged, by including step numbers and/or state IDs, can break causal invariance:

 In[8]:=
 Out[8]=
 In[9]:=
 Out[9]=

### Scope (10)

#### System Types (5)

CausalInvariantQ supports both string and list substitution systems:

 In[10]:=
 Out[10]=
 In[11]:=
 Out[11]=

Lists can contain arbitrary symbolic elements:

 In[12]:=
 Out[12]=

Give an explicit substitution system rule:

 In[13]:=
 Out[13]=

An alternative method of specifying that a substitution system should be used:

 In[14]:=
 Out[14]=

CausalInvariantQ also supports multiway generalizations of cellular automata:

 In[15]:=
 Out[15]=
 In[16]:=
 Out[16]=

CausalInvariantQ also supports multiway generalizations of Wolfram Models:

 In[17]:=
 Out[17]=
 In[18]:=
 Out[18]=

Construct a multiway evolution by explicitly specifying an association:

 In[19]:=
 Out[19]=

#### Rules and Initial Conditions (2)

CausalInvariantQ accepts both individual rules and lists of rules:

 In[20]:=
 Out[20]=
 In[21]:=
 Out[21]=

Likewise for initial conditions:

 In[22]:=
 Out[22]=

#### Event Selection Functions (3)

Apply only the first possible event at each step:

 In[23]:=
 Out[23]=

Apply the first and last possible events at each step:

 In[24]:=
 Out[24]=

Use a greedy-style algorithm to apply the maximal set of non-conflicting events at each step (strings only):

 In[25]:=
 Out[25]=

### Options (3)

Explicitly specify the type of rule:

 In[26]:=
 Out[26]=
 In[27]:=
 Out[27]=

#### Step Numbers and State IDs (3)

By default, equivalent states are merged across all time steps:

 In[28]:=
 Out[28]=

Merging of equivalent states across different time steps can be prevented by including step numbers:

 In[29]:=
 Out[29]=

Merging of equivalent states at the same time step can be prevented by also including state IDs:

 In[30]:=
 Out[30]=

### Applications (2)

#### Causal Invariant Rules (2)

Prove that the Xor and And functions are causal invariant (due to associativity):

 In[31]:=
 Out[31]=
 In[32]:=
 Out[32]=

On the other hand, the Nand function is not associative, so it is not causal invariant:

 In[33]:=
 Out[33]=

## Version History

• 1.0.0 – 10 April 2020