Cellular automata

Communication matters

Speaker: Martin Kutrib
Post thumbnail
Rogério took a Leica to shoot Martin

We consider systems of a huge number of interacting finite automata as massively parallel systems. The finite automata (also called cells) are arranged as one-dimensional array and work synchronously at discrete time steps. Naturally, the communication between the cells is necessary for non-trivial computations and, in fact, the amount of communication matters. Here, we focus mainly on measuring the amount of communication quantitatively by the number of messages sent by the cells. Recent results on the computational capacity as well as on decidability problems in such restricted cellular automata are discussed. In particular, fundamental types of communication are considered and the questions of how much communication is necessary to accomplish a certain task and of whether there are communication hierarchies are addressed. Since even for systems with drastically bounded communication many properties are undecidable, another question is to what extent the systems have to be limited in order to regain decidable properties. We present some selected results on these topics and want to draw attention to the overall picture and to some of the main ideas involved.