A graph-based reflexive artificial chemistry.

The conceptual divide between formal systems of computation and abstract models of chemistry is considered. As an attempt to concretely bridge this divide, a formalism is proposed that describes a constructive artificial chemistry on a space of directed graph structures. The idea for the formalism originates in computer science theory, with the traditional abstraction of a physical machine, the finite-state machine (FSM). In the FSM, the machine (state-transition graph) and input string (series of binary digits) are fundamentally distinct objects, separated by nature of the underlying formalism. This distinction is dissolved in the proposed system, resulting in a construction process that is reflexive: graphs interact with their own topological structure to generate a product. It is argued that this property of reflexivity is a key element missing from earlier model chemistries. Examples demonstrate the continuous emergence complex self-similar topologies, novel reaction pathways, and seemingly open-ended diversity. Implications of these findings are discussed.