See the rest of this article for a detailed description of how to build a working network automaton....

>

__One important note__-- You may have realized in visualizing this that there will be cases in which "conflicts" occur. For example, for a given pair of nodes A and B, A may compute the link A-->B as "on" but B will compute the link B-->A as "off." What do we do in such cases? One option is to choose one of these choices randomly, another option is to have them "cancel out" to "off" or to "sum" them to "on." An even more useful option is to keep

*both*states. We can call this a "superposition" of states. We can represent this "indeterminate" state by a new color of link -- not white or black, but perhaps grey. Our rule can be modified such that each node only sees it's relative state for that link. Over time the network can "collapse" these indeterminate states as nodes come into agreement. For now, let's just keep both states. So every link has two states, one in each direction but nodes can only "see" the links that correspond to their perspectives. This allows for the measurements that nodes make of one another to be relative to their own perspectives. Another way of viewing this is that there actually exists two links between every pair of nodes, one in each direction. Each link has 1 state. This is equivalent to the previous suggestion.

*every other node.*To accomplish this, each node considers every other node to be in its neighborhood. It looks at the state of the link connecting it to each other node at t-1 as well as the state each other node, and possibly of its own state at t-1 as well, and based on these it computes a state for the link from it to that node at time t. By configuring the rule carefully such as system can be made to evolve various network topologies and dynamics over time.

*only*those nodes to which it has links above a certain threshold (or of a certain value or range) at time t-1.

NOTES:

- 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.

## Comments