Computational irreducibility is one of the main ideas proposed by Stephen Wolfram in his book A New Kind of Science. Stephen Wolfram (born August 29, 1959 in London) is a scientist known for his work in particle physics, cellular automata and computer algebra, and is the author of the computer program Mathematica. ... A New Kind of Science is a controversial book by Stephen Wolfram, published in 2002. ...

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 occurrences where theory's predictions are effectively not possible. Wolfram states several phenomena are normally computationally irreducible. For the Macintosh operating system, which was called System up to version 7. ... Empiricism (greek εμπειρισμός, from empirical, latin experientia - the experience) is generally regarded as being at the heart of the modern scientific method, that our theories should be based on our observations of the world rather than on intuition or faith; that is, empirical research and a posteriori inductive reasoning rather... Fact is the following: Generally a fact is an event that has happened, or a statement that is generally regarded as true — whether one accepts it as real (true) or not. ... Behavior or behaviour refers to the actions or reactions of an object or organism, usually in relation to the environment. ... In logic, a decision problem is determining whether or not there exists a decision procedure or algorithm for a class S of questions requiring a Boolean value (i. ... Prediction of future events is an ancient human wish. ... A phenomenon (plural: phenomena) is an observable event, especially something special (literally something that can be seen from the Greek word phainomenon = observable). ...

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. Free will is the philosophical doctrine that holds that our choices are ultimately up to ourselves. ...

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. An approximation is an inexact representation of something that is still close enough to be useful. ...

See also

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

In mathematical logic, Gödels incompleteness theorems are two celebrated theorems proved by Kurt Gödel in 1931. ... Computation can be defined as finding a solution to a problem from given inputs by means of an algorithm. ... The Principle of computational equivalence is one of the main ideas proposed by Stephen Wolfram in his book A New Kind of Science. ... Artificial intelligence (also known as machine intelligence and often abbreviated as AI) is intelligence exhibited by any manufactured (i. ... Irreducible complexity is a concept which considers that the generally accepted scientific theory that life evolved through biological evolution by natural selection alone is incomplete or flawed, and that some additional mechanism is required to explain the origins of life. ...

External links and references

• Weisstein, Eric W., et al., "Computational irreducibility (http://mathworld.wolfram.com/ComputationalIrreducibility.html)". MathWorld -- A Wolfram Web Resource.
• Wolfram, Stephen, "A New Kind of Science (http://www.wolframscience.com/nksonline)". Wolfram Media, Inc., May 14, 2002. ISBN 1579550088
  • Wolfram, Stephen, "Computational irreducibility (http://www.wolframscience.com/nksonline/page-737)". A New Kind of Science.
  • Wolfram, Stephen, "History of computational irreducibility (http://www.wolframscience.com/nksonline/page-1132a-text)". A New Kind of Science.
  • Wolfram, Stephen, "History of computational irreducibility notes (http://www.wolframscience.com/reference/notes/1132a)". A New Kind of Science.
  • Wolfram, Stephen, "Undecidability and intractability in theoretical physics (http://www.stephenwolfram.com/publications/articles/physics/85-undecidability/2/text.html)". Physics Review Letters, 1985.
• Israeli, Navot, and Nigel Goldenfeld, "On computational irreducibility and the predictability of complex physical systems (http://arxiv.org/abs/nlin.CG/0309047)". Physics Review Letters, 2004.
• "Computational irreducibility (http://www.iscid.org/encyclopedia/Computational_Irreducibility)". ISCID Encyclopedia of Science and Philosophy. 2004. International Society for Complexity, Information, and Design.
• "Computational irreducibility (http://www.cna.org/isaac/Glossb.htm#ComputI)". ISAAC/EINSTein research and development.
• Berger, David, "Stephen Wolfram, A New Kind of Science (http://serendip.brynmawr.edu/bookshelves/wolfram.html)". Serendip's Bookshelves.
• "Complexity is Elusive (http://focus.aps.org/story/v13/st10)". Physics Review Letter, March 4, 2004.
• Tomasson, Gunnar, "Scientific Theory and Computational Irreducibility (http://forum.wolframscience.com/archive/topic/113-1.html)". A New Kind of Science: The NKS Forum.