Two-State Graph-Rewriting Automata
For a Demonstration of Open-Ended Evolutionary Innovation in a Closed System
Kohji Tomita & Haruhisa Kurokawa
National Institute of Advanced Industrial Science and Technology
Tokyo Institute of Technology
Graph-rewriting automata define symbol dynamics on graphs similarly to cellular automata, but the structure is not restricted on lattice space. Structural change is possible along with state transition. Depending on the different rules and initial condition, a variety of processes are possible, including a universal Turing machine with self-replication capability. In this talk, we concentrate on the simplest two-state graph-rewriting automata, and examine their behavior for all possible rules from a fixed initial graph. The result shows that, even with only two states, a wide variety of development processes are possible including self-replicating graphs.