CombinatorialDynamics
David Hillman
David Hillman
STEP 1: define sets of combinatorial n-dimensional spaces
space sets for 1-d cellular automata
space sets for 1-d cellular automata: revised
oriented space sets
●
all arrows point in the same direction
●
studied in symbolic dynamics (topological conjugacy and flow equivalence of subshifts of finite type)
asymmetrical space sets
3. rules for *
3. rules for *
( * is called an involution )
The graph defines a new space set. The allowed neighborhoods are the length-2 paths. The segments are the directed paths. The spaces are the bi-infinite directed paths or loops. There is a local, invertible map between the old space set and the new one.
Renaming the vertices or edges gives an invertible, local map. The only requirement is that every vertex and edge have a distinct name. Elements in the left-hand graph are mapped to corresponding elements in the right-hand graph.
If the graph has a symmetry then renaming can be used to create a map from the space set to itself.
Clearly a vertex with no edges attached does not appear in any space. So we can add or remove them at will without changing the space set. If the vertex is asymmetrical we must add or remove both orientations of it.
To remove an edge:
1. choose an asymmetrical edge e that connects two distinct vertices
1. choose an asymmetrical edge e that connects two distinct vertices
The map between spaces works by first replacing each length-3 path p mentioned above by u(p), and then replacing all remaining length-2 paths p by u(p).
The map between spaces works by first replacing each length-3 path p mentioned above by u(p), and then replacing all remaining length-2 paths p by u(p).
To add an edge you just do this same thing in reverse.
To add an edge you just do this same thing in reverse.
All maps are generated by the kinds we've already seen.
So to find laws of evolution you just generate maps between space sets
and pick out those that map a space set to itself.
It's easy!
All maps are generated by the kinds we've already seen.
So to find laws of evolution you just generate maps between space sets
and pick out those that map a space set to itself.
It's easy!
I've left out a lot that is interesting:
●
The equivalence problem: which space sets can be mapped to which? Franks (1984) solved this for the most important class of oriented space sets. I recently solved it for the most important class of asymmetric space sets.The answer is related to Witt equivalence classes of integral quadratic forms.The question remains open for symmetric space sets.
●
The linear-algebraic nature of these systems is very deep. They have something to do with hermitian forms and additive categories. This still remains to be worked out.
There are plenty of open questions (especially since so far I'm probably the only person working on most of this), and there's lots of work to be done. Please join in!
Unfortunately I keep not getting around to finishing papers. But I'm glad to communicate with anyone about this subject.
David Hillman
email: dhi@cablespeed.com
email: hillman@wolfram.com
PhD dissertation (1995): Combinatorial Spacetimes
http://xxx.lanl.gov/abs/hep-th/9805066
There are plenty of open questions (especially since so far I'm probably the only person working on most of this), and there's lots of work to be done. Please join in!
Unfortunately I keep not getting around to finishing papers. But I'm glad to communicate with anyone about this subject.
David Hillman
email: dhi@cablespeed.com
email: hillman@wolfram.com
PhD dissertation (1995): Combinatorial Spacetimes
http://xxx.lanl.gov/abs/hep-th/9805066