PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Bolognesi T. Planar trinet dynamics with two rewrite rules. Technical report, 2007.
 
 
Abstract
(English)
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.
Subject Digital physics
Trivalent network
Complexity indicator
Elementary cellular automata
Two-dimensional Turing machine
Turmite
Emergent space
Graph rewriting
NKS
F.1.1 Models of Computation


Icona documento 1) Download Document PDF


Icona documento Open access Icona documento Restricted Icona documento Private

 


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional