Computational irreducibility
Encyclopedia
Computational irreducibility is one of the main ideas proposed by Stephen Wolfram
in his book A New Kind of Science
.
), 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 scientific based resolution for free will
.
s). 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.
Stephen Wolfram
Stephen Wolfram is a British scientist and the chief designer of the Mathematica software application and the Wolfram Alpha computational knowledge engine.- Biography :...
in his book A New Kind of Science
A New Kind of Science
A New Kind of Science is a book by Stephen Wolfram, published in 2002. It contains an empirical and systematic study of computational systems such as cellular automata...
.
The idea
Wolfram terms the inability to shortcut a program (e.g., a systemSystem
System is a set of interacting or interdependent components forming an integrated whole....
), or otherwise describe its behavior in a simple way, "computational irreducibility". The empirical
Empiricism
Empiricism is a theory of knowledge that asserts that knowledge comes only or primarily via sensory experience. One of several views of epistemology, the study of human knowledge, along with rationalism, idealism and historicism, empiricism emphasizes the role of experience and evidence,...
fact
Fact
A fact is something that has really occurred or is actually the case. The usual test for a statement of fact is verifiability, that is whether it can be shown to correspond to experience. Standard reference works are often used to check facts...
is that the world of simple programs contains a great diversity of behavior
Behavior
Behavior or behaviour refers to the actions and mannerisms made by organisms, systems, or artificial entities in conjunction with its environment, which includes the other systems or organisms around as well as the physical environment...
, 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 scientific based resolution for free will
Free will
"To make my own decisions whether I am successful or not due to uncontrollable forces" -Troy MorrisonA pragmatic definition of free willFree will is the ability of agents to make choices free from certain kinds of constraints. The existence of free will and its exact nature and definition have long...
.
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 exhibit behavior undescribeable by reasonably "simple" laws.
Analysis
Israeli and Goldenfeld found that some less complex systems behaved simply and predictably (thus, they allowed approximationApproximation
An approximation is a representation of something that is not exact, but still close enough to be useful. Although approximation is most often applied to numbers, it is also frequently applied to such things as mathematical functions, shapes, and physical laws.Approximations may be used because...
s). 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 theoryChaos theoryChaos theory is a field of study in mathematics, with applications in several disciplines including physics, economics, biology, and philosophy. Chaos theory studies the behavior of dynamical systems that are highly sensitive to initial conditions, an effect which is popularly referred to as the...
- Gödel’s Theorem
- ComputationComputationComputation is defined as any type of calculation. Also defined as use of computer technology in Information processing.Computation is a process following a well-defined model understood and expressed in an algorithm, protocol, network topology, etc...
- Principle of Computational Equivalence
- Artificial intelligenceArtificial intelligenceArtificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
- Robert Rosen
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 1-57955-008-8
- Wolfram, Stephen, "Computational irreducibility". A New Kind of Science.
- Wolfram, Stephen, "History of computational irreducibility". A New Kind of ScienceA New Kind of ScienceA New Kind of Science is a book by Stephen Wolfram, published in 2002. It contains an empirical and systematic study of computational systems such as cellular automata...
. - Wolfram, Stephen, "History of computational irreducibility notes". A New Kind of ScienceA New Kind of ScienceA New Kind of Science is a book by Stephen Wolfram, published in 2002. It contains an empirical and systematic study of computational systems such as cellular automata...
. - Wolfram, Stephen, "Undecidability and intractability in theoretical physics". Physical Review LettersPhysical Review LettersPhysical Review Letters , established in 1958, is a peer reviewed, scientific journal that is published 52 times per year by the American Physical Society...
, 1985.
- Israeli, Navot, and Nigel Goldenfeld, "On computational irreducibility and the predictability of complex physical systems". Physical Review LettersPhysical Review LettersPhysical Review Letters , established in 1958, is a peer reviewed, scientific journal that is published 52 times per year by the American Physical Society...
, 2004.
- "Computational irreducibility". ISAAC/EINSTein research and development.
- 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 ScienceA New Kind of ScienceA New Kind of Science is a book by Stephen Wolfram, published in 2002. It contains an empirical and systematic study of computational systems such as cellular automata...
: The NKS Forum.