Bolognesi T. Planar trivalent network computation. In: 5th International Conference MCU 2007 - Machines, Computations, and Universality (Orleans - France, 10-13 september 2007). Proceedings, pp. 146 - 157. Jerome Durand-Lose, Maurice Margenstern (eds.). (Lecture Notes in Computer Science, vol. 4664). Springer, 2007. |

Abstract (English) |
Confluent rewrite systems for giant trivalent networks have been investigated by S. Wolfram as possible models of space and spacetime, in the ambitious search for the most fundamental, computational laws of physics. We restrict here to planar trivalent nets, which are shown to support Turing-complete computations, and take an even more radical, approach: while operating on network duals, we use just one elementary rewrite rule and drive its application by a simple, fully deterministic algorithm, rather than by pattern-matching. We devise effective visual indicators for exploring the complexity of computations with elementary initial conditions, consisting of thousands of graphs, and expose a rich variety of behaviors, from regular to random-like. Among their features we study, in particular, the dimensionality of the emergent space. | |

URL: | http://www.springerlink.com/content/m624350kj28305u9/?p=bc601d6a17d14da8874eff05b51ea655&pi=12 | |

DOI: | 10.1007/978-3-540-74593-8 | |

Subject | Digital physics Trivalent network Complexity indicator Cellular automata Two-dimensional Turing machine Turmite Emergent space F.1.1 Models of Computation F.1 Computation by Abstract Devices |

1) Download Document PDF |

Open access Restricted Private