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"→rulessystem of the specified type
assocsystem 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"Falsewhether to label states and events with their respective step numbers
"IncludeStateID"Falsewhether 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]:=
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 (10) 

System Types (5) 

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]:=
(* Evaluate this cell to get the example input *) CloudGet["https://www.wolframcloud.com/obj/8a4a1e17-d7f2-4352-8bd3-3c1137dd3263"]
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 (2) 

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 (3) 

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 (3) 

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 (3) 

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 (2) 

Causal Invariant Rules (2) 

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]=

Version History

  • 1.0.0 – 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