Complex Systems

Cellular Engineering Download PDF

M. Burgin
Department of Mathematics
University of California, Los Angeles
405 Hilgard Avenue
Los Angeles, CA 90095

Abstract

The main goal of this paper is to develop tools for constructing different kinds of abstract automata based on cellular automata. We call this engineering problem cellular engineering. Different levels of computing systems and models are considered. The emphasis is made on the top-level model called a grid automaton. Our goal is to construct grid automata using cellular automata. To achieve this, we develop a specific technology based on multilevel finite automata. It is proved that two-dimensional cellular automata allow the construction of some types of grid automata, as well as Turing machines and pushdown automata.