Problem 20

What higher-level descriptions of information processing in cellular automata can be given?

Cellular automaton evolution can in principle carry out arbitrary information processing. An important problem of theory and practice is to find a way of organizing this information processing. In specific cases one can devise cellular automaton rules that allow particular computations to be carried out (e.g., [55]). Or one can identify within a cellular automaton structures that can interact so as to mimic the components of conventional digital computers. But all these approaches are strongly based on analogues with conventional serial-processing computers. Information processing in cellular automata occurs however in a fundamentally distributed and parallel fashion, and one must invent a new framework to make use of it. Such a framework would likely be valuable in studying the many physical systems in which information processing is also distributed.

One approach is statistical in nature. It consists in devising and describing attractors for the global evolution of cellular automata. All initial configurations in a particular basin of attraction may be thought of as instances of some pattern, so that their evolution towards the same attractor may be considered as a recognition of the pattern. This approach is probably effective when the basins of attraction are local in space, as in image processing (e.g., [56]). But the construction of attractors for more general problems is likely to be very difficult. An attempt in this direction might be made by considering basins of attraction as sets of sequences corresponding to particular formal languages (cf. [50]).

Another approach is to use symbolic representations for various attributes or components of cellular automaton configurations. But the structures used in conventional computer languages are largely inappropriate. The definite organization of computer memory into named areas, stacks, and so on, is not suitable for cellular automata in which processing elements are not distinguished from memory elements. Rather perhaps data could be represented by an object like a graph, on which transformations can be performed in parallel. But the simple organizing principles that are required still remain to be found. It seems likely that a radically new approach is needed [57].

previous  l  next