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

Back to Sam Buss's publications page.