Wolfram Research

Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 CausalInvariantQ

Source Notebook

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"][rules→sel,…] 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

Determine causal invariance for two string substitution systems:

In[1]:=
ResourceFunction[ "CausalInvariantQ"][{"AA" -> "ABA", "AAA" -> "B"}, "AAA", 2]
Out[1]=
In[2]:=
ResourceFunction[ "CausalInvariantQ"][{"AA" -> "AB", "B" -> "BA"}, "AABAA", 2]
Out[2]=

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

In[3]:=
ResourceFunction[ "CausalInvariantQ"][{"AA" -> "ABA", "AAA" -> "B"}, "AAA", 2]
Out[3]=
In[4]:=
ResourceFunction[ "CausalInvariantQ"][{"AA" -> "ABA", "AAA" -> "B"} -> "Sequential", "AAA", 2]
Out[4]=

CausalInvariantQ can handle Wolfram Models and other system types:

In[5]:=
ResourceFunction["CausalInvariantQ"][ "WolframModel" -> {{{2, 2, 1}, {2, 2, 2}} -> {{1, 1, 3}, {1, 1, 1}, {2, 1, 2}}}, {{{0, 0, 0}, {0, 0, 0}, {0, 0, 0}}}, 2]
Out[5]=
In[6]:=
ResourceFunction["CausalInvariantQ"][ CellularAutomaton[30], {0, 0, 0, 1, 0, 0, 0}, 1]
Out[6]=
In[7]:=
ResourceFunction[ "CausalInvariantQ"][{{0} -> {0, 1, 0}, {1, 1} -> {1}}, {0, 1, 0}, 2]
Out[7]=

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

In[8]:=
ResourceFunction[ "CausalInvariantQ"][{"AA" -> "AB", "B" -> "BA"}, "AABAA", 2]
Out[8]=
In[9]:=
ResourceFunction[ "CausalInvariantQ"][{"AA" -> "AB", "B" -> "BA"}, "AABAA", 2, "IncludeStepNumber" -> True, "IncludeStateID" -> True]
Out[9]=

Scope

System Types

CausalInvariantQ supports both string and list substitution systems:

In[10]:=
ResourceFunction[ "CausalInvariantQ"][{"BB" -> "AA", "AB" -> "BA"}, "ABBA", 3]
Out[10]=
In[11]:=
ResourceFunction[ "CausalInvariantQ"][{{1, 1} -> {0, 0}, {0, 1} -> {1, 0}}, {0, 1, 1, 0}, 3]
Out[11]=

Lists can contain arbitrary symbolic elements:

In[12]:=
ResourceFunction["CausalInvariantQ"][{{ RGBColor[1, 1, 0]} -> {RGBColor[1, 1, 0], RGBColor[1, 1, 0]}, { RGBColor[1, 0.5, 0]} -> {RGBColor[1, 1, 0], RGBColor[ 1, 0.5, 0]}}, {{RGBColor[1, 1, 0], RGBColor[1, 0.5, 0], RGBColor[ 1, 1, 0]}}, 2]
Out[12]=

Give an explicit substitution system rule:

In[13]:=
ResourceFunction["CausalInvariantQ"][ SubstitutionSystem[{{0} -> {0, 0}, {0} -> {0, 1}}], {{0}}, 3]
Out[13]=

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

In[14]:=
ResourceFunction["CausalInvariantQ"][ "SubstitutionSystem" -> {{0} -> {0, 0}, {0} -> {0, 1}}, {{0}}, 3]
Out[14]=

CausalInvariantQ also supports multiway generalizations of cellular automata:

In[15]:=
ResourceFunction["CausalInvariantQ"][ CellularAutomaton[{170, 240}], {0, 0, 1, 0, 0}, 1]
Out[15]=
In[16]:=
ResourceFunction["CausalInvariantQ"][ CellularAutomaton[{170, 240}], {0, 0, 1, 0, 0}, 2]
Out[16]=

CausalInvariantQ also supports multiway generalizations of Wolfram Models:

In[17]:=
ResourceFunction["CausalInvariantQ"][ "WolframModel" -> {{{0, 1}, {1, 0}} -> {{1, 2}, {2, 1}, {0, 1}}}, {{{0, 1}, {1, 0}, {0, 1}, {2, 3}}}, 1]
Out[17]=
In[18]:=
ResourceFunction["CausalInvariantQ"][ "WolframModel" -> {{{0, 1}} -> {{1, 2}, {2, 1}}}, {{{0, 1}, {1, 0}}}, 1]
Out[18]=

Construct a multiway evolution by explicitly specifying an association:

In[19]:=
ResourceFunction[ "CausalInvariantQ"][<| "StateEvolutionFunction" -> (StringReplaceList[#, {"A" -> "AA", "B" -> "AB"}] &), "StateEquivalenceFunction" -> SameQ, "StateEventFunction" -> Identity, "EventDecompositionFunction" -> Identity, "EventApplicationFunction" -> Identity, "SystemType" -> "None", "EventSelectionFunction" -> Identity|>, {"ABA"}, 3]
Out[19]=

Rules and Initial Conditions

CausalInvariantQ accepts both individual rules and lists of rules:

In[20]:=
ResourceFunction["CausalInvariantQ"]["A" -> "AA", "AAA", 1]
Out[20]=
In[21]:=
ResourceFunction[ "CausalInvariantQ"][{"A" -> "AB", "B" -> "BA"}, "AAABA", 1]
Out[21]=

Likewise for initial conditions:

In[22]:=
ResourceFunction[ "CausalInvariantQ"][{"A" -> "AB", "B" -> "BA"}, {"ABA", "AAB"}, 3]
Out[22]=

Event Selection Functions

Apply only the first possible event at each step:

In[23]:=
ResourceFunction[ "CausalInvariantQ"][{"A" -> "AAB", "BA" -> "A"} -> "Sequential", "A", 2]
Out[23]=

Apply the first and last possible events at each step:

In[24]:=
ResourceFunction[ "CausalInvariantQ"][{"A" -> "AAB", "BA" -> "A"} -> ({First[#], Last[#]} &), "ABA", 1]
Out[24]=

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

In[25]:=
ResourceFunction[ "CausalInvariantQ"][{"A" -> "AA", "BA" -> "AB"} -> "MaxScan", "ABA", 4]
Out[25]=

Options

Explicitly specify the type of rule:

In[26]:=
ResourceFunction["CausalInvariantQ"][ "SubstitutionSystem" -> {"A" -> "AA", "A" -> "AB"}, {"ABA"}, 2]
Out[26]=
In[27]:=
ResourceFunction["CausalInvariantQ"][ "SubstitutionSystem" -> {{0} -> {0, 0}, {0} -> {0, 1}}, {{0, 1, 0}}, 2]
Out[27]=

Step Numbers and State IDs

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

In[28]:=
ResourceFunction[ "CausalInvariantQ"][{"A" -> "AB", "B" -> "BA"}, {"BABBAA"}, 2]
Out[28]=

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

In[29]:=
ResourceFunction[ "CausalInvariantQ"][{"A" -> "AB", "B" -> "BA"}, {"BABBAA"}, 2, "IncludeStepNumber" -> True]
Out[29]=

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

In[30]:=
ResourceFunction[ "CausalInvariantQ"][{"A" -> "AB", "B" -> "BA"}, {"BABBAA"}, 2, "IncludeStepNumber" -> True, "IncludeStateID" -> True]
Out[30]=

Applications

Causal Invariant Rules

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

In[31]:=
ResourceFunction[ "CausalInvariantQ"][{"TT" -> "F", "TF" -> "T", "FT" -> "T", "FF" -> "F"}, "TFTTFF", 2]
Out[31]=
In[32]:=
ResourceFunction[ "CausalInvariantQ"][{"TT" -> "T", "TF" -> "F", "FT" -> "F", "FF" -> "F"}, "TFTTFF", 2]
Out[32]=

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

In[33]:=
ResourceFunction[ "CausalInvariantQ"][{"TT" -> "F", "TF" -> "T", "FT" -> "T", "FF" -> "T"}, "TFTTFF", 2]
Out[33]=

Resource History

  • Date Created: 10 April 2020

Source Metadata

  • Citation:
    • Stephen Wolfram (2002), “A New Kind of Science”
    • Stephen Wolfram (2020), “A Class of Models with Potential to Represent Fundamental Physics”
    • Jonathan Gorard (2020), “Some Relativistic and Gravitational Properties of the Wolfram Model”
    • Jonathan Gorard (2020), “Some Quantum Mechanical Properties of the Wolfram Model”

Related Resources

License Information