A pseudo-random network mobile automaton with linear growth

Bolognesi T.

Digital physics  Network mobile automaton  Trivalent graph  Pseudo-randomness  two-dimensional Turing machine 

Based on the mobile automaton computational paradigm, a (fully deterministic) algorithm is introduced that grows planar graphs while exhibiting surprisingly uniform pseudo-random dynamics. The graph growth rate, as a function of the automaton steps, is O(n), and nicely combines with the O(Sqrt[n]) of a previously introduced algorithm of ours: these two rates are also achieved by two most elementary visit-and-grow procedures with regular dynamics, of which our automata can be viewed as randomized versions. Applications of mobile automata to fundamental physics and quantum gravity have been recently suggested, but other application areas are envisaged as well.

Source: ISTI Technical reports, 2008