Computational irreducibility
Computational irreducibility suggests certain computational processes cannot be simplified and the only way to determine the outcome of a process is to go through each step of its computation. It is one of the main ideas proposed by Stephen Wolfram in his 2002 book A New Kind of Science, although the concept goes back to studies from the 1980s.
The idea
Many systems, both physical and computational, are complex enough that they cannot be effectively modeled. Even simple programs can give rise to a great diversity of behavior. In many cases, no model can predict from initial conditions exactly what will occur in a given system without doing as much computational work as the system itself performs.Wolfram terms this inability to "shortcut" a system, or otherwise describe its behavior in a simple way, "computational irreducibility." The idea argues that there are circumstances where theoretical prediction is intractable. Wolfram describes several phenomena that are normally computationally irreducible.
Computationally irreducibility systems are hard to predict or simulate. The Principle of Computational Equivalence implies these systems are as computationally powerful as any designed computer.
Implications
- There is no easy theory for any behavior that seems complex.
- Complex behavior features can be captured with models that have simple underlying structures.
- An overall system's behavior based on simple structures can still exhibit behavior indescribable by reasonably "simple" laws.