Computational irreducibility
This article needs additional citations for verification. (May 2019) (Learn how and when to remove this template message)

Computational irreducibility is one of the main ideas proposed by Stephen Wolfram in his book A New Kind of Science.
The idea
Wolfram terms the inability to shortcut a program (e.g., a system), or otherwise describe its behavior in a simple way, "computational irreducibility". The empirical fact is that the world of simple programs contains a great diversity of behavior, but, because of undecidability, it is impossible to predict what they will do before essentially running them. The idea demonstrates that there are occurrences where theory's predictions are effectively not possible. Wolfram states several phenomena are normally computationally irreducible.
Computational irreducibility explains observed limitations of existing mainstream science. In cases of computational irreducibility, only observation and experiment can be used. Computational irreducibility may also provide a scientificallybased resolution for free will.
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.
Analysis
Israeli and Goldenfeld found that some less complex systems behaved simply and predictably (thus, they allowed approximations). However, more complex systems were still computationally irreducible and unpredictable. It is unknown what conditions would allow complex phenomena to be described simply and predictably.
See also
 Chaos theory
 Gödel's Theorem
 Computation
 Principle of Computational Equivalence
 Artificial intelligence
 Robert Rosen
 Emergent behaviour
External links and references
 Weisstein, Eric W., et al., "Computational irreducibility". MathWorld—A Wolfram Web Resource.
 Wolfram, Stephen, "A New Kind of Science". Wolfram Media, Inc., May 14, 2002.
ISBN 1579550088
 Wolfram, Stephen, "Computational irreducibility". A New Kind of Science.
 Wolfram, Stephen, "History of computational irreducibility". A New Kind of Science.
 Wolfram, Stephen, "History of computational irreducibility notes". A New Kind of Science.
 Wolfram, Stephen, "Undecidability and intractability in theoretical physics". Physical Review Letters, 1985.
 Israeli, Navot, and Nigel Goldenfeld, "On computational irreducibility and the predictability of complex physical systems". Physical Review Letters, 2004.
 ""Computational Irreducibility". ISAAC/EINSTein research and development. Archived from the original on 20111211.
 Berger, David, "Stephen Wolfram, A New Kind of Science". Serendip's Bookshelves.
 "Complexity is Elusive". Physical Review Letter, March 4, 2004.
 Tomasson, Gunnar, "Scientific Theory and Computational Irreducibility". A New Kind of Science: The NKS Forum.