Exploring Computational Irreducibility and the Predictability of Complex Systems using Mathematica
University of Houston Law Center
This talk exposits in some detail the methodology developed in a fascinating recent paper by Israeli and Goldenfeld, and shows how Mathematica may be used to explore and extend their work. The purpose of this effort is to make their work more accessible and to permit a broader audience to conduct at least many of the relevant experiments.
Their paper attempts to shows that if certain micriscopic details are blurred together, for many elementary cellular automata, the long run behavior always emulates certain other cellular automaton. Indeed, sometimes these approximating cellular automata exhibit behavior that is less complex than that of the original. And this is true even with respect to some (but apparently not all) Class 3 cellular automata that exhibit complex behavior. The paper thus suggests that, although some automata may be computationally irreducible, others hitherto placed in that category may have their behavior approximated (and thus reduced in some sense) using other cellular automata. The paper thus speculates as to whether Wolfram’s classifications of automata and the understanding of computational irreducibility he presented in A New Kind of Science may need some refinement.
This translational scholarship is important because cellular automata can help explicate the behavior not only of physical systems, but biological and social systems as well. And perhaps because Mathematica is such a natural language for the study of cellular automata, the code for accomplishing the translation proves relatively simple. To be sure, speed issues associated with Mathematica make it difficult as a practical matter to replicate the most complex experiments conducted by Israeli and Goldenfeld. This limitation might be softened to some extent by faster hardware, patience, or perhaps algorithms that exploit Mathematica more effectively than has been possible in this initial foray. The analysis here suggests, however, that there may be more fundamental problems of computational explosion and irreducibility with trying to find approximating cellular automata that rely on larger block size. Many cellular automata may retain their secrets.
(April 20, 2004)