Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 BranchPairResolutions

Source Notebook

Compute branch pair resolutions for a given multiway system

Contributed by: Jonathan Gorard

ResourceFunction["BranchPairResolutions"][rules,init,n]

generates an association of resolved and unresolved branch pairs for the multiway system with the specified rules after n steps, starting with initial conditions init.

ResourceFunction["BranchPairResolutions"][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
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
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"gives a system type name
"EventSelectionFunction"determines which events should be applied to a given state
The event selection function sel in ResourceFunction["BranchPairResolutions"][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["BranchPairResolutions"] is a list of states appropriate for the type of system used.
ResourceFunction["BranchPairResolutions"][rules,"string",…] is interpreted as ResourceFunction["BranchPairResolutions"][rules,{"string"},…].
ResourceFunction["BranchPairResolutions"] accepts both individual rules and lists of rules, and likewise for initial conditions.
Options for BranchPairsResolutions include:
"IncludeStepNumber"Falsewhether to label states and events with their respective step numbers
"IncludeStateID"Falsewhether to label states and events with unique IDs
"GivePredecessors"Falsewhether to label branch pairs with their predecessor state
"GiveResolvents"Falsewhether to label branch pairs with their resolvent state
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 (5) 

Generate the associations showing all convergent and non-convergent branch pairs (i.e. critical pairs) for two string substitution systems:

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

Show common predecessor states:

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

Show common resolvent states for resolved branch pairs:

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

Show both common predecessors and common resolvents, where appropriate:

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

Different event selection functions can lead to different branch pair resolution behavior:

In[6]:=
ResourceFunction[ "BranchPairResolutions"][{"AA" -> "ABA", "AAA" -> "B"}, "AAA", 2]
Out[6]=
In[7]:=
ResourceFunction[ "BranchPairResolutions"][{"AA" -> "ABA", "AAA" -> "B"} -> "Sequential", "AAA", 2]
Out[7]=

BranchPairResolutions can handle Wolfram Models and other system types:

In[8]:=
ResourceFunction["BranchPairResolutions"][ "WolframModel" -> {{{2, 2, 1}, {2, 2, 2}} -> {{1, 1, 3}, {3, 3, 2}}}, {{{2, 2, 1}, {2, 2, 3}, {2, 2, 2}, {3, 3, 3}}}, 1]
Out[8]=
In[9]:=
ResourceFunction["BranchPairResolutions"][ CellularAutomaton[30], {0, 0, 1, 0, 0}, 2]
Out[9]=
In[10]:=
ResourceFunction[ "BranchPairResolutions"][{{0} -> {0, 1, 0}, {1, 1} -> {1}}, {0, 1, 1}, 2]
Out[10]=

Preventing identical states from being merged, by including step numbers and/or state IDs, can change branch pair resolution behavior:

In[11]:=
ResourceFunction[ "BranchPairResolutions"][{"AA" -> "AB", "B" -> "BA"}, "AABAA", 2]
Out[11]=
In[12]:=
ResourceFunction[ "BranchPairResolutions"][{"AA" -> "AB", "B" -> "BA"}, "AABAA", 2, "IncludeStepNumber" -> True, "IncludeStateID" -> True]
Out[12]=

Scope (11) 

System Types (6) 

BranchPairResolutions supports both string and list substitution systems:

In[13]:=
ResourceFunction[ "BranchPairResolutions"][{"BB" -> "AA", "AB" -> "BA"}, "ABBA", 3]
Out[13]=
In[14]:=
ResourceFunction[ "BranchPairResolutions"][{{1, 1} -> {0, 0}, {0, 1} -> {1, 0}}, {0, 1, 1, 0}, 3]
Out[14]=

Lists can contain arbitrary symbolic elements:

In[15]:=
(* Evaluate this cell to get the example input *) CloudGet["https://www.wolframcloud.com/obj/330703b2-6eb0-4c0f-b3a6-721c6917f997"]
Out[15]=

Give an explicit substitution system rule:

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

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

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

BranchPairs also supports multiway generalizations of cellular automata:

In[18]:=
ResourceFunction["BranchPairs"][ CellularAutomaton[{170, 240}], {0, 0, 1, 0, 0}, 1]
Out[18]=

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

In[19]:=
ResourceFunction["BranchPairResolutions"][ CellularAutomaton[{170, 240}], {0, 0, 1, 0, 0}, 3]["Resolved"]
Out[19]=

Show that the rule 30 cellular automaton leads to unresolved branch pairs, and thus is not causal invariant:

In[20]:=
ResourceFunction["BranchPairResolutions"][ CellularAutomaton[30], {0, 0, 1, 0, 0}, 2]["Unresolved"]
Out[20]=

BranchPairResolutions also supports multiway generalizations of Wolfram Models:

In[21]:=
ResourceFunction["BranchPairResolutions"][ "WolframModel" -> {{{0, 1}, {1, 0}} -> {{1, 2}, {2, 1}, {0, 1}}}, {{{0, 1}, {1, 0}, {0, 1}, {2, 3}}}, 1]
Out[21]=
In[22]:=
ResourceFunction["BranchPairResolutions"][ "WolframModel" -> {{{0, 1}} -> {{1, 2}, {2, 1}}}, {{{0, 1}, {1, 0}}}, 1]
Out[22]=

Construct a multiway evolution by explicitly specifying an association:

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

Rules and Initial Conditions (2) 

BranchPairResolutions accepts both individual rules and lists of rules:

In[24]:=
ResourceFunction["BranchPairResolutions"]["A" -> "AA", "AAA", 1]
Out[24]=
In[25]:=
ResourceFunction[ "BranchPairResolutions"][{"A" -> "AB", "B" -> "BA"}, "AAABA", 1]
Out[25]=

Likewise for initial conditions:

In[26]:=
ResourceFunction[ "BranchPairResolutions"][{"A" -> "AB", "B" -> "BA"}, {"ABA", "AAB"}, 2]
Out[26]=

Event Selection Functions (3) 

Apply only the first possible event at each step:

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

Apply the first and last possible events at each step:

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

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

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

Options (7) 

Explicitly specify the type of rule:

In[30]:=
ResourceFunction["BranchPairResolutions"][ "SubstitutionSystem" -> {"A" -> "AA", "A" -> "AB"}, {"ABA"}, 2]
Out[30]=
In[31]:=
ResourceFunction["BranchPairResolutions"][ "SubstitutionSystem" -> {{0} -> {0, 0}, {0} -> {0, 1}}, {{0, 1, 0}}, 2]
Out[31]=

Step Numbers and State IDs (3) 

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

In[32]:=
ResourceFunction[ "BranchPairResolutions"][{"A" -> "AB", "B" -> "BA"}, {"BABB"}, 2]
Out[32]=

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

In[33]:=
ResourceFunction[ "BranchPairResolutions"][{"A" -> "AB", "B" -> "BA"}, {"BABB"}, 2, "IncludeStepNumber" -> True]
Out[33]=

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

In[34]:=
ResourceFunction[ "BranchPairResolutions"][{"A" -> "AB", "B" -> "BA"}, {"BABB"}, 1, "IncludeStepNumber" -> True, "IncludeStateID" -> True]
Out[34]=

Predecessors and Resolvents (4) 

By default, BranchPairs returns only an association of resolved and unresolved branch pairs:

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

Common predecessor states can be shown using "GivePredecessors":

In[36]:=
ResourceFunction[ "BranchPairResolutions"][{"AA" -> "BA", "AABAA" -> "AB"}, "AAABAAA", 2, "GivePredecessors" -> True]
Out[36]=

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

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

Show both common predecessors and common resolvents, where appropriate:

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

Applications (2) 

Causal Invariant Rules (2) 

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

In[39]:=
ResourceFunction[ "BranchPairResolutions"][{"TT" -> "F", "TF" -> "T", "FT" -> "T", "FF" -> "F"}, "TFTTFF", 5]["Unresolved"]
Out[39]=
In[40]:=
ResourceFunction[ "BranchPairResolutions"][{"TT" -> "T", "TF" -> "F", "FT" -> "F", "FF" -> "F"}, "TFTTFF", 5]["Unresolved"]
Out[40]=

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

In[41]:=
ResourceFunction[ "BranchPairResolutions"][{"TT" -> "F", "TF" -> "T", "FT" -> "T", "FF" -> "T"}, "TFTTFF", 5]["Unresolved"]
Out[41]=

Properties and Relations (1) 

BranchPairsResolutions returning an empty list of unresolved branch pairs is a sufficient (but not necessary) condition for causal invariance:

In[42]:=
ResourceFunction[ "BranchPairResolutions"][{"TT" -> "F", "TF" -> "T", "FT" -> "T", "FF" -> "T"}, "TFTTFF", 5]["Unresolved"]
Out[42]=
In[43]:=
ResourceFunction[ "BranchPairResolutions"][{"TT" -> "F", "TF" -> "T", "FT" -> "T", "FF" -> "F"}, "TFTTFF", 5]["Unresolved"]
Out[43]=

Publisher

Jonathan Gorard

Version History

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