Journal article:
Samuel R. Buss and Christos Papadimitriou and John
Tsitsiklis.
"On the predictability of coupled automata: an allegory about
chaos."
Complex Systems 5 (1991) 525-539.
Download article: postscript or PDF.
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.
Earlier conference version:
Samuel R. Buss and Christos Papadimitriou and John
Tsitsiklis.
"On the predictability of coupled automata: an allegory about
chaos."
In Proceedings of the 31st Annual Symposium on Foundations of
Computer Science, volume II (FOCS' 1990), IEEE Computer Society Press, 1990, pp.
788-793..
Download conference article: postscript or PDF.