Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 CanonicalBranchPairs

Source Notebook

Compute canonical branch pairs for a given multiway system

Contributed by: Jonathan Gorard

ResourceFunction["CanonicalBranchPairs"][rules]

generates a list of canonical (i.e. initial condition-independent) branch pairs for the multiway system with the specified rules.

ResourceFunction["CanonicalBranchPairs"][rules,n]

generates an association of resolved and unresolved canonical branch pairs for the multiway system with the specified rules after n steps.

Details and Options

Rules can be specified in the following ways:
{"lhs1"→"rhs1",…}string substitution system
{{l11,l12,…}->{r11,r12,..},…}list substitution system
CellularAutomaton[rules]cellular automaton system
"type"→rulessystem of the specified type
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
ResourceFunction["CanonicalBranchPairs"] accepts both individual rules and lists of rules.
Options for ResourceFunction["CanonicalBranchPairs"] include:
"GivePredecessors"Falsewhether to label branch pairs with their predecessor state
"GiveResolvents"Falsewhether to label branch pairs with their resolvent state
"IncludeSelfPairs"Falsewhether to include trivial branch pairs
In the theory of abstract rewrite systems, a critical pair (branch pair) is a pair of expressions that can be derived from a common expression by two different applications of a rewrite rule (i.e. either the same rule applied in two different places, or two different rules).
More generally, a branch pair indicates where a multiway evolution bifurcates.

Examples

Basic Examples (3) 

Generate the list of all canonical branch pairs (i.e. critical pairs) for a string substitution system:

In[1]:=
ResourceFunction[ "CanonicalBranchPairs"][{"AA" -> "ABA", "AAA" -> "B"}]
Out[1]=

Generate the association showing which branch pairs converge after 2 steps and which do not:

In[2]:=
ResourceFunction[ "CanonicalBranchPairs"][{"AA" -> "ABA", "AAA" -> "B"}, 2]
Out[2]=

Show common predecessor states:

In[3]:=
ResourceFunction[ "CanonicalBranchPairs"][{"AA" -> "ABA", "AAA" -> "B"}, "GivePredecessors" -> True]
Out[3]=

Show common resolvent states for resolved canonical branch pairs:

In[4]:=
ResourceFunction[ "CanonicalBranchPairs"][{"AA" -> "ABA", "AAA" -> "B"}, 2, "GiveResolvents" -> True]
Out[4]=

Show both common predecessors and common resolvents, where appropriate:

In[5]:=
ResourceFunction[ "CanonicalBranchPairs"][{"AA" -> "ABA", "AAA" -> "B"}, 2, "GivePredecessors" -> True, "GiveResolvents" -> True]
Out[5]=

CanonicalBranchPairs can handle Wolfram Models and other system types:

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

Scope (4) 

System Types (4) 

CanonicalBranchPairs supports both string and list substitution systems:

In[9]:=
ResourceFunction[ "CanonicalBranchPairs"][{"BB" -> "AA", "ABB" -> "BA"}]
Out[9]=
In[10]:=
ResourceFunction[ "CanonicalBranchPairs"][{{1, 1} -> {0, 0}, {0, 1, 1} -> {1, 0}}]
Out[10]=

CanonicalBranchPairs also supports multiway generalizations of cellular automata:

In[11]:=
Take[ResourceFunction["CanonicalBranchPairs"][ CellularAutomaton[{170, 240}]], 20]
Out[11]=

Generate all resolved branch pairs from left- and right- shift cellular automaton rules after 5 steps:

In[12]:=
ResourceFunction["CanonicalBranchPairs"][ CellularAutomaton[{170, 240}], 5]["Resolved"]
Out[12]=

Determine that the rule 30 cellular automaton is not causal invariant:

In[13]:=
ResourceFunction["CanonicalBranchPairs"][CellularAutomaton[30], 5]["Unresolved"]
Out[13]=

CanonicalBranchPairs also supports multiway generalizations of Wolfram Models:

In[14]:=
ResourceFunction["CanonicalBranchPairs"][ "WolframModel" -> {{{2, 2, 1}, {2, 2, 2}} -> {{1, 1, 2}, {2, 2, 2}}}]
Out[14]=

Determine that this Wolfram Model rule has unresolved branch pairs, and thus is not causal invariant:

In[15]:=
ResourceFunction["CanonicalBranchPairs"][ "WolframModel" -> {{{2, 2, 1}, {2, 2, 2}} -> {{1, 1, 2}, {2, 2, 2}}}, 5]["Unresolved"]
Out[15]=

Options (4) 

Predecessors and Resolvents (2) 

By default, CanonicalBranchPairs returns only a list of canonical branch pairs:

In[16]:=
ResourceFunction[ "CanonicalBranchPairs"][{"AA" -> "BA", "AABAA" -> "AB"}]
Out[16]=

Common predecessor states can be shown using "GivePredecessors":

In[17]:=
ResourceFunction[ "CanonicalBranchPairs"][{"AA" -> "BA", "AABAA" -> "AB"}, "GivePredecessors" -> True]
Out[17]=

Similarly, CanonicalBranchPairs with a step count by default lists only resolved and unresolved canonical branch pairs:

In[18]:=
ResourceFunction[ "CanonicalBranchPairs"][{"AA" -> "BA", "AABAA" -> "AB"}, 2]
Out[18]=

Common resolvents of resolved branch pairs can be shown using "GiveResolvents":

In[19]:=
ResourceFunction[ "CanonicalBranchPairs"][{"AA" -> "BA", "AABAA" -> "AB"}, 2, "GiveResolvents" -> True]
Out[19]=

Show both common predecessors and common resolvents, where appropriate:

In[20]:=
ResourceFunction[ "CanonicalBranchPairs"][{"AA" -> "BA", "AABAA" -> "AB"}, 2, "GivePredecessors" -> True, "GiveResolvents" -> True]
Out[20]=

Self Pairs (2) 

By default, CanonicalBranchPairs does not include self pairs (i.e. trivial critical pairs):

In[21]:=
ResourceFunction[ "CanonicalBranchPairs"][{"AA" -> "AB", "BAA" -> "BA"}]
Out[21]=

Self pairs can be included using “IncludeSelfPairs”:

In[22]:=
ResourceFunction[ "CanonicalBranchPairs"][{"AA" -> "AB", "BAA" -> "BA"}, "IncludeSelfPairs" -> True]
Out[22]=

Applications (2) 

Causal Invariant Rules (2) 

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

In[23]:=
ResourceFunction[ "CanonicalBranchPairs"][{"TT" -> "F", "TF" -> "T", "FT" -> "T", "FF" -> "F"}, 1]["Unresolved"]
Out[23]=
In[24]:=
ResourceFunction[ "CanonicalBranchPairs"][{"TT" -> "T", "TF" -> "F", "FT" -> "F", "FF" -> "F"}, 1]["Unresolved"]
Out[24]=

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

In[25]:=
ResourceFunction[ "CanonicalBranchPairs"][{"TT" -> "F", "TF" -> "T", "FT" -> "T", "FF" -> "T"}, 1]["Unresolved"]
Out[25]=

Properties and Relations (1) 

CanonicalBranchPairs returns an empty list of unresolved canonical branch pairs if and only if the rule is total causal invariant:

In[26]:=
ResourceFunction[ "CanonicalBranchPairs"][{"TT" -> "F", "TF" -> "T", "FT" -> "T", "FF" -> "T"}, 1]["Unresolved"]
Out[26]=
In[27]:=
ResourceFunction[ "CanonicalBranchPairs"][{"TT" -> "F", "TF" -> "T", "FT" -> "T", "FF" -> "F"}, 1]["Unresolved"]
Out[27]=

Version History

  • 3.0.0 – 14 April 2020
  • 2.0.0 – 26 March 2020
  • 1.0.0 – 20 March 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