The Computational irreducibility reference article from the English Wikipedia on 24-Apr-2004 (provided by Fixed Reference: snapshots of Wikipedia from wikipedia.org)

Computational irreducibility

Computational irreducibility is one of the main ideas proposed by Stephen Wolfram in his book A New Kind of Science.

Table of contents

1 The idea 2 Implications 3 Analysis 4 See also 5 External links and references

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 actually running them. The idea demonstrates that there are occurances 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 scientific based resolution for free will.

Implications

• Nearly 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 can exhibit behavior undescribeable by reasonable laws.

Analysis

Israeli and Goldenfeld found that for some some less complex systems, they behaved simply and predictably (thus, finding approximations). Though, more complex systems were still computationally irreducible and unpredictable. It is unknown under what conditions would allow complex phenomenon to be described simply and predictablely.

See also

• Gödel’s Theorem
• Computation
• Principle of Computational Equivalence
• Artificial intelligence

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". Physics Review Letters, 1985.
• Israeli, Navot, and Nigel Goldenfeld, "On computational irreducibility and the predictability of complex physical systems". Physics Review Letters, 2004.
• "Computational irreducibility". ISCID Encyclopedia of Science and Philosophy. 2004. International Society for Complexity, Information, and Design.
• "Computational irreducibility". ISAAC/EINSTein research and development.
• Berger, David, "Stephen Wolfram, A New Kind of Science". Serendip's Bookshelves.
• "Complexity is Elusive". Physics Review Letter, March 4, 2004.
• Tomasson, Gunnar, "Scientific Theory and Computational Irreducibility". A New Kind of Science: The NKS Forum.

This is the "Computational irreducibility" reference article from the English Wikipedia. All text is available under the terms of the GNU Free Documentation License. See also our Disclaimer.