A Framework For Representing Objects in Cellular Automata

Abstract

Cellular automata consistently grow in relevance to engineering and science as computation becomes more important for design and theoretical analysis. Although cellular automata have been used for a variety of tasks a means of representing objects has not yet been devised. This is a severe limitation for cellular automata as objects are the ultimate means for systematically describing physical systems. In an effort to construct objects in cellular automata a discrete structure called an event-lattice was developed. It refines the definition of an event to have explicit extension in time and space. Using Alfred North Whitehead's conception of what distinguishes an actual entity from an object a framework for objects could be devised under the assumption that a finite volume of space-time contains a finite amount of information. An external binary operation uses a finite set of symbols to give the event-lattice its structure and also acts as a set used to construct objects. The set of occurrences of all objects in the lattice is representable as the free group generated by the set of symbols. This particular structure was inspired by the Lattice Gas Automaton. This conception of objects has a number of agreeable properties beyond the applications of simulation.As the point particle is arguably the most important object for description a point particle model was developed and investigated. An algorithm is identified such that particles may maintain their identities by having unique spatial coordinates at all times. Interactions amongst these particles were generalized and studied using a momentum balance. A discretized form of the Navier-Stokes equation was obtained. When the generalized interactions are organized as a vector the evolution of the system closely resembles the collision step of the Lattice Boltzmann Method which was then retrofitted and used to study the point particle model further. The most important directions for further research are in the compact representations of objects as sequences.