Planar Trinet Computation using Two Rewrite Rules

Tommaso Bolognesi

CNR - Istituto ISTI

Abstract

A deterministic algorithm for the creation of planar trivalent networks ('trinets') is investigated, which is based on the application of two simple rewrite rules. The algorithm differs substantially from those proposed by S. Wolfram in his NKS book as potential models of a dynamic physical space, in the fact that rewrite rule application is not driven by pattern matching but follows a "mobile-control" approach somewhat similar to that of Turing machines. The algorithm also improves on a previous proposal of ours, both by the inclusion of a second rewrite rule, and by a simplified policy for step control and rule selection, which is now completely defined by three parameters. The first two of them, when eliminating symmetry-redundancy, identify a space of 162 possibilities, while the third is a "threshold" that ranges from 3 to infinity, but seems to yield interesting computations only for the first few low values.

A useful behavioral complexity indicator is introduced, called "revisit indicator", that visually reveals the extent to which a given computation is able 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 1D nets much more frequent than 2D nets (these include the regular hexagonal grid). 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 between a ring-like and a string-like structure, with the various cases differing in the details of the basic building block. In two cases only, out of over a thousand we have inspected, a perfectly fair yet remarkably random-like revisit indicator is found, whose trinets exhibit the slowest growth rate. We study this case in some detail. Finally, one case is found and studied that seems to be unique in showing a remarkable mix of regularity and randomness.