Complex Systems

On the Predictability of Coupled Automata: An Allegory about Chaos Download PDF

Samuel R. Buss
Christos H. Papadimitriou
Department of Computer Science and Engineering,
University of California at San Diego, La Jolla, CA 92093, USA

John N. Tsitsiklis
Laboratory for Information and Decision Systems,
Massachusetts Institute of Technology, Cambridge, MA 02139, USA

Abstract

We show a sharp dichotomy between systems of identical automata with a symmetric global control whose behavior is easy to predict, and those whose behavior is hard to predict. The division pertains to whether the global control rule is invariant with respect to permutations of the states of the automaton. On the other hand, we show that testing whether the global control rule has this invariance property is an undecidable problem.