On the Predictability of Coupled Automata: An Allegory about Chaos
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.
