Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 TuringMachineCausalGraph

Source Notebook

Generate a causal graph of the Turing machine evolution

Contributed by: Wolfram Research

ResourceFunction["TuringMachineCausalGraph"][e]

yields the causal graph for a Turing machine evolution e.

ResourceFunction["TuringMachineCausalGraph"][rule,init,t]

yields the causal graph for the evolution of rule from init for t steps.

Details and Options

Turing machine events have two causal dependencies: to the previous event, and to the last event that changed the color at the current tape position.
For the first events, and for events at tape positions that were never modified before, there would be fewer incoming connections.
ResourceFunction["TuringMachineCausalGraph"] accpets the same options as Graph.

Examples

Basic Examples (2) 

Make a causal graph for a Turing machine evolution:

In[1]:=
ResourceFunction["TuringMachineCausalGraph"][2506, {1, {{}, 0}}, 20]
Out[1]=

Use a manually created evolution spec:

In[2]:=
ResourceFunction[ "TuringMachineCausalGraph"][{{{1, 1, 0}, {0, 0}}, {{2, 2, 1}, {0, 0}}, {{1, 1, 0}, {0, 0}}, {{2, 2, 1}, {0, 0}}}]
Out[2]=

Scope (2) 

All TuringMachine specs are supported, including 3-color rules:

In[3]:=
ResourceFunction[ "TuringMachineCausalGraph"][{596440, 2, 3}, {1, {{2, 1, 1}, 0}}, 10]
Out[3]=

And multidimensional rules:

In[4]:=
ResourceFunction["TuringMachineCausalGraph"][{ {1, 0} -> {2, 1, {0, 1}}, {1, 1} -> {2, 0, {0, -1}}, {2, 0} -> {4, 1, {0, -1}}, {2, 1} -> {3, 0, {0, 1}}, {3, 0} -> {1, 1, {-1, 0}}, {3, 1} -> {2, 1, {0, 1}}, {4, 0} -> {3, 1, {0, -1}}, {4, 1} -> {2, 0, {1, 0}}}, {1, {{{}}, 0}}, 20]
Out[4]=

Options (1) 

Graph options are supported:

In[5]:=
ResourceFunction["TuringMachineCausalGraph"][2506, {1, {{}, 0}}, 20, GraphLayout -> "SpringElectricalEmbedding"]
Out[5]=

Properties and Relations (1) 

Reproduce a causal graph from the TuringMachine documentation:

In[6]:=
ResourceFunction[ "TuringMachineCausalGraph"][1507, {1, RandomInteger[1, 30]}, 200]
Out[6]=

Neat Examples (1) 

Generate a complex causal graph for a multidimensional rule:

In[7]:=
ResourceFunction["TuringMachineCausalGraph"][{ {1, 0} -> {2, 1, {0, 1}}, {1, 1} -> {2, 0, {0, -1}}, {2, 0} -> {4, 1, {0, -1}}, {2, 1} -> {3, 0, {0, 1}}, {3, 0} -> {1, 1, {-1, 0}}, {3, 1} -> {2, 1, {0, 1}}, {4, 0} -> {3, 1, {0, -1}}, {4, 1} -> {2, 0, {1, 0}}}, {1, {{{}}, 0}}, 1000]
Out[7]=

Version History

  • 1.0.0 – 09 June 2020

Related Resources

Author Notes

No argument checking, not tested.

License Information