Elements of a theory of computer simulation I: Sequential CA over random graphs

摘要

This paper is a first step in the development of mathematical foundations for a theory of simulation. We employ sequentially updated cellular automata (sCA) over arbitrary graphs as a paradigmatic framework. In the development of the theory, we focus on the properties of causal dependencies among local mappings in a simulation. Let Y be a graph in which (a) each vertex i has a state xi0, 1 and (b) there exists a local map ƒi defined on the states of the Y-neighbors and xi that returns the state of yi0, 1. Suppose i1, …, in is a permutation of the Y-vertices, then the order of application of the local maps ƒik induces a sequential (or asynchronous) cellular automaton (sCA) over Y. In this paper we introduce a mapping between the base graph Y, over which the sCA is defined and which represents the mutual dependencies of the local maps, and the update graph U(Y), whose vertices are permutations of all Y-vertices. Two permutations π1, π2 are adjacent in U(Y) if they differ in exactly two consecutive coordinates, {ik, ik+1|, and {ik, ik+1 ∉ eY. U(Y) represents a conceptual framework which allows to determine equivalence classes of sCA for a given graph X, independent of the family of local maps (ƒi) 1 ⩽ i ⩽ n. We consider: (a) U as a random variable over Gn,p and analyze the induced random graph U(Gn,p), the update graph, and show (b) that U exhibits properties of a covariant functor.