From Cellular Automata to Grid Automata

Mark Burgin

University of California, Los Angeles

Abstract

Cellular automata have become one of the most popular models for distributed computation, in particular, and distributed processes in general. They are used for a diversity of purposes and are especially promising for representation of various processes in a uniform medium (Wolfram, 2002). Uniform structures, such as cellular automata, are very convenient in many cases, but we can see that things that are around, and especially computing systems, are not uniform. They can be uniform to some extent or uniform in some parts, but such systems are not uniform as a whole. The reason is that different systems and different components of systems have to solve their specific problems. Consequently, they have different structures, which are more appropriate just for their problems. For instance, the memory, control device, and processors of a computer have different structures. However, our experience shows that it is possible to build a diversity of things from very simple elements.

The goal of this work is to study relations between uniform and non-uniform computational systems. Cellular automata are the simplest uniform models of distributed computations and concurrent processes. Grid automata are the most advanced and powerful models of distributed computations and concurrent processes, which synthesize different approaches to modeling and simulation of such processes (Burgin, 2003; 2005).

A grid automaton is a system of automata, which are situated in a grid and called nodes. Some of these automata are connected and interact with one another.

Cellular automata are special cases of grid automata although, in general, grid automata are non-uniform. Our goal is not to change cellular automata by grid automata, but to use cellular automata as the basic level for building hierarchies of grid automata. The reason for doing this is the possibility of reducing complexity, using relevant levels of this hierarchy for system and process description. For instance, computer hardware has several levels of hierarchy: from the lowest logic gate level to the highest level of functional units, such as system memory, CPU, keyboard, monitor, printer, etc.

It is necessary to remark that different authors studied hierarchical cellular automata (cf., for example, Adamides, et al., 1992; Sikdar, et al., 2001). We expand hierarchical computational structures beyond the level of cellular automata.

The goal of this work is to show how to build various computational models (from simple to advanced such as grid automata) utilizing cellular automata. As a result, we develop a computing hierarchy based on cellular automata.

Adamides, E. D., Tsalides, P., and Thanailakis A. (1992). "Hierarchical cellular automata structures," Parallel Computing, 18(5), 517–524. 

Burgin M. (2003). "Cluster Computers and Grid Automata," in Proceedings of the ISCA 17th International Conference: Computers and Their Applications, International Society for Computers and Their Applications, Honolulu, Hawaii, 106–109.

Burgin, M. (2005). Superrecursive Algorithms, New York, Springer.  

Sikdar, B. K., Majumder, P., Mukherjee, M., Ganguly, N., Das, D. K., and Chaudhuri, P. P. (2001). "Hierarchical cellular automata as an on-chip test pattern generator," Fourteenth International Conference on VLSI Design, 403–408.

Wolfram, S. (2002). A New Kind of Science, Champaign, IL, Wolfram Media.