Two-State Graph-Rewriting Automata

For a Demonstration of Open-Ended Evolutionary Innovation in a Closed System

Kohji Tomita & Haruhisa Kurokawa
Satoshi Murata

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.

[presentation materials]