Virtual State Machines in Cellular Automata
Chris Langton
Center for Nonlinear Studies
Los Alamos National Laboratory Los Alamos, NM 87545, USA
Abstract
One of the most important properties of cellular automata is their capacity to support propagating structures. Propagating structures are employed as signals in many CA models of computation. Treating propagating structures as automata elevates the notion of a singal to something that is a computational entity in its own right. These propagating signal-automata are embedded in the very "tape" upon which they compute, and are constituted of the very symbols that they write on the tape in the course of their computation. Thus, signal-automata are both process and data at the same time. They can create, modify, or erase other such automata, and can support distributed computations wherein the operators also serve as operands. As their existence is rather ephemeral when compared to that of the "physical" cells of the lattice that get caught up in their propagation, we refer to signal-automata as "virtual" automata, or virtual state machines (VSM's). In this paper, we look at some examples of VSM systems, explore a programming methodology based on the process of protein synthesis, and discuss the implications for "virtual structure" in the physical world.
