See the rest of this article for a detailed description of how to build a working network automaton....
- Andy Ilachinski, e-mailed a very helpful response to this article in which he provided a number of links to related research on what are called Structurally Dynamic Cellular Automata or SDCA's. What I have proposed above is an approach to making SDCA's in which the neighborhood topologies are the states of the nodes in the network. In other words, each node's state is its local topology. Andy gave me some references to very interesting papers on the subject, including:
* There are some wonderful illustrations of the output of SDCA's in Andy's book "Cellular Automata: A Discrete Universe". These illustrations are exactly what I have been visualizing -- essentially beautiful sequences of the evolution of various topologies based on local rules. They vary from simple geometric symmetries to fascinating complex and chaotic networks. If you are interested in this I can't recommend enough that you take a look at this book. Anyone working on the physics of networks should know about this.
* Steve Majercik wrote a thesis on extensions of SDCA that he also rigorously proved are capable of universal computation.
* A very recent independent "rediscovery" of essentially the same class of topological CA rules in the context of quantum field theory is due to Manfred Requardt
- The rules I am interested in compute the topology of each neighborhood as a function of the topologies of neighborhoods it is connected to. In the most general case (the last rule above), every neighborhood is connected to every other neighborhood, but the links have states as well. By having both node states and link states we can generate very sophisticated rules in which the way that any two nodes interact is a function of their link states (one in each direction). Thus the topologies of neighborhoods are functions of the states of nodes and links that comprise them. As these states change over time the topology of the network evolves. This effectively links the "energy in space" to the "shape of space" -- unifying them at a fundamental level. Everything reduces to topology.
- In the final model that I came to in my thinking on this subject I realized that in the general case every node should have 2 directed links with every other node (on in each direction "to" and "from"). The state of a node is a function of the state of all its links. The state of each link is a function of the state of the node it comes from (or alternatively, of the states of both nodes it connects). I believe this model is capable of containing any topology, including systems in which the topology and geometry of space from the perspective of any location is relative (this is the value of having 2 directed links connecting each pair of nodes -- it enables each node to measure the other independently of the other's measurement of it -- the link can can have a different state in each direction). This is basically a superset of the SDCA concept -- any SDCA can emerge within such a network.