---
bibtex: @incollection{reisinger2013exploring,
title={Exploring Wolfram’s Notion of Computational Irreducibility with a Two-Dimensional Cellular Automaton},
author={Reisinger, Drew and Martin, Taylor and Blankenship, Mason and Harrison, Christopher and Squires, Jesse and Beavers, Anthony},
booktitle={Irreducibility and Computational Equivalence},
pages={263--272},
year={2013},
publisher={Springer}
}
---
Exploring Wolfram’s Notion of Computational Irreducibility with a Two-Dimensional Cellular Automaton
The notion of computational irreducibility says that a problem is computationally irreducible when the only way to solve it is to traverse a trajectory through a state space step by step using no shortcut. In this paper, we will explore this notion by addressing whether computational irreducibility is a consequence of how a particular problem is represented. To do so, we will examine two versions of a given game that are isomorphic representations of both the play space and the transition rules underlying the game. We will then develop a third isomorph of the play space with transition rules that seem to only be determined in a computationally irreducible manner.
As a consequence, it would seem that representing the play space di↵erently in the third isomorph introduces computational irreducibility into the game where it was previously lacking. If so, we will have shown that, in some cases at least, computational irreducibility depends on the representation of a given problem.
Wolfram (p737) "almost all of [great historical triumphs of theoretical science turn] are based on finding ways to reduce the computational work that has to be done in order to predict how some particular system will behave"
whenever computational irreducibility exists in a system, it means that in e↵ect there can be no way to predict how the system will behave, except by going through almost as many steps of computation as the evolution of the system itself
Computational irreducibility is concerned with systems in which methods to predict the state of a system are no faster than running the system itself.
If we cannot find a “shortcut,” as it were, the system is computationally irreducible. (p3)