Planar trinet computation with two rewrite rules

Tommaso Bolognesi - CNR/ISTI, Pisa, Italy

Abstract
In his NKS book, S. Wolfram advocates trivalent networks as a model for physical space, and investigates several algorithms for their expansion and transformation. One of these approaches, shortly mentioned in a note on 'network mobile automata', is based on the idea of a single active node that moves by small steps on the network while changing the local structure by some rewrite rule. However, it is reported that the exhaustive analysis of several families of rewrite systems has not led to especially complicated behaviors.   
In this paper we reconsider network mobile automata, and propose a deterministic algorithm for the creation of planar trivalent networks ('trinets') based on the application of only two, extremely simple rewrite rules, and on the enumeration and exploration of a number of choices for the 'brownian' dynamics of the active node.  The algorithm, which also improves on a previous proposal of ours, turns out to be remarkably fruitful in terms of emergent properties and behavioral complexity.  Rule selection and control node motion depend on three parameters: each value of a 'threshold' parameter identifies a class of 162 computations, resulting from all possible, symmetry-optimized combinations of the other two parameters.
A useful behavioral complexity indicator is introduced, called revisit indicator, that visually reveals the extent to which a given computation can to go back to past portions of the growing network.  A variety of emergent features in thus exposed, involving periodic, nested and random like dynamics. Trinets more or less rapidly converging to a regular structure are frequently obtained, with 1-D nets being the norm, and 2-D nets, based on the hexagonal grid, the exception.  In spite of the local nature of the algorithm step, fair, regular behaviors can be obtained in which every part of the net is visited infinitely often.  A frequently observed nested behavior is one in which the growing trinet  oscillates while assuming string-like and/or ring-like overall shapes, with variations in the details of the basic building block.  In two cases only, out of over a thousand we have inspected, a remarkably fair, random-like revisit indicator is found, whose trinets exhibit a slow, square-root growth rate; they deserve special attention.  Finally, one 2-D case is found that seems to be unique in the way  regularity and randomness are mixed.

Keywords.  Digital physics, trivalent network, complexity indicator, elementary cellular automata, two-dimensional Turing machine, turmite, emergent space, graph rewriting.

Cellular automata vs. trivalent networks ('trinets') for fundamental physics

Trinets do not assume a predefined, rigid space, but create it

Row[{ArrayPlot[CellularAutomaton[110,Table[Random[Integer],{400}],400],PixelConstrained->True,ImageSize->600],
trinetPlot[3,5,17,2,2000,GraphPlot3D]}]

Planar trinets and their duals

duals=Import["duals.pdf"]

The dual graph -- white nodes -- is also planar, its faces are (possibly degenerate) triangles, and its nodes have unrestricted degree

Two planar graph-rewrite rules

duals=Import["rules.pdf"]

The set of rules {T1, T2, T2rev} is complete: can transform any planar trinet into any other

The step of the planar trinet algorithm - a network mobile automaton approach [NKS, p. 1040]

Three parameters:    Threshold (3-∞),    RefinCode (1-18),    DiagsCode (1-9)

duals=Import["step.pdf"]

Revisit indicator 
thumbnails for all computations with Threshold = 3, RefinCode = *, DiagsCode = *, and 300 steps

Module[{init=3,threshold=3,steps=300},Show[GraphicsGrid[Table[Table[With[{myList=edgeIdList[init,threshold,refinCode,diagsCode,steps]},
ListPlot[myList,PlotLabel->{threshold,{refinCode,diagsCode},steps},DisplayFunction->Identity,PlotRange->{{0,Length[myList]},{0,Max[myList]}},Ticks->{{},{Max[myList]}},ImageSize->100]],{diagsCode,1,9}],{refinCode,1,18}]]]]

Final trinets for same class of Threshold-3 computations

Module[{threshold=3,init=3,steps=300},
Show[GraphicsGrid[
Table[Table[GraphPlot[primalGraph[dualDataFinalStep[init,threshold,refinCode,diagsCode,steps]],AspectRatio->0.8`,DisplayFunction->Identity,PlotLabel->{threshold,{refinCode,diagsCode},steps}],{diagsCode,1,9}],{refinCode,1,18}]]]]

Some selected computations

GraphicsRow[{revisitAndTrinetPlots[3,3,2,5,300,GraphPlot],revisitAndTrinetPlots[3,3,3,2,295,GraphPlot]},AspectRatio->1/3]
GraphicsRow[{revisitAndTrinetPlots[3,3,6,9,300,GraphPlot],revisitAndTrinetPlots[3,3,14,4,1000,GraphPlot]},AspectRatio->1/3]

Oscillations of code {3, {13, 2}} - manipulate

mySeq = Module[{init=3,threshold=3,refinCode=13,diagsCode=2,steps=200,jump=1},
GraphPlot[primalGraph[#]]&/@dualDataSequence[init,threshold,refinCode,diagsCode,steps]];
Manipulate[mySeq[[step]],{step,1,200,1}]

Other selected computations

GraphicsRow[{revisitAndTrinetPlots[3,4,16,4,200,GraphPlot],revisitAndTrinetPlots[3,5,17,2,2000,GraphPlot3D]},AspectRatio->1/3]

GraphicsRow[{revisitAndTrinetPlots[3,6,10,2,300,GraphPlot],revisitAndTrinetPlots[3,3,8,9,800,GraphPlot]},AspectRatio->1/3]

GraphicsRow[{revisitAndTrinetPlots[3,5,17,5,300,GraphPlot],revisitAndTrinetPlots[3,3,15,9,360,GraphPlot]},AspectRatio->1/3]

Code {6, {13, 3}} - small deviations from hex-grid

revisitAndTrinetPlots[3,6,13,3,2000,GraphPlot3D]

Code {4, {17, 8}} - uniform random revisit indicator

revisitAndTrinetPlots[3,4,17,8,5000,GraphPlot3D]

Code {5, {9, 8}} - uniform random revisit indicator

revisitAndTrinetPlots[3,5,9,8,5000,GraphPlot3D]

Node-growth rate for the two 'white codes'

{fitting4178,fitting598}

Next steps

Investigate properties (resilience, self-healing ability...) and applications of two 'white noise' codes

Use causal network concept to investigate subjective (vs. objective) view of growing universe

Drop planarity requirement, and add rule T3 (==> complete set)

References

T. Bolognesi, 'Planar trivalent network computation', in J. Durand-lose, M. Margenstern (eds.), Machines, Computations and Universality, Proceedings of MCU 2007, Lecure Notes in Computer Science, N. X, Springer 2007.

T. Bolognesi, 'Planar trinet dynamics with two rewrite-rules', ISTI Tech. Report X-2007, CNR-ISTI, Pisa.

S. Wolfram, A New Kind of Science, Wolfram Media, 2002 [Ch. 9]