All Topics  
Computational irreducibility

 

 
   Email Print
   Bookmark   Link
 

 

Computational irreducibility
 
 
  Topics Computational irreducibility Topic Home

Computational irreducibility is one of the main ideas proposed by Stephen Wolfram
Stephen Wolfram

Stephen Wolfram is a British physicist, mathematician and businessman known for his work in theoretical particle physics, cosmology, cellular automaton, complexity theory, and computer algebra....
 in his book A New Kind of Science
A New Kind of Science

A New Kind of Science is a controversial 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 system
System

System is a set of interacting or interdependent entities, real or abstract, forming an integrated whole.The concept of an "integrated whole" can also be stated in terms of a system embodying a set of relationships which are differentiated from relationships of the set to other elements, and from relationships between an element of the se...
), or otherwise describe its behavior in a simple way, "computational irreducibility". The empirical
Empiricism

In philosophy, empiricism is a theory of knowledge which asserts that knowledge arises from experience. Empiricism is one of several competing views about how we know "things," part of the branch of philosophy called epistemology, or "theory of knowledge"....
 fact
Fact

A fact is something said to be true or supposed to have happened, example: Kiira is mean, FACT. An idea becomes a fact after competent people have tested a hypothesis through the scientific method....
 is that the world of simple programs contains a great diversity of behavior
Behavior

Behavior or behaviour refers to the action s or reactions of an object or organism, usually in Relational theory to the environment. Behavior can be conscious or Unconscious mind, overt or covert, and voluntary or involuntary....
, but, because of undecidability, it is impossible to predict what they will do before essentially running them.






Discussion
Ask a question about 'Computational irreducibility'
Start a new discussion about 'Computational irreducibility'
Answer questions from other users
Full Discussion Forum



Encyclopedia


Computational irreducibility is one of the main ideas proposed by Stephen Wolfram
Stephen Wolfram

Stephen Wolfram is a British physicist, mathematician and businessman known for his work in theoretical particle physics, cosmology, cellular automaton, complexity theory, and computer algebra....
 in his book A New Kind of Science
A New Kind of Science

A New Kind of Science is a controversial 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 system
System

System is a set of interacting or interdependent entities, real or abstract, forming an integrated whole.The concept of an "integrated whole" can also be stated in terms of a system embodying a set of relationships which are differentiated from relationships of the set to other elements, and from relationships between an element of the se...
), or otherwise describe its behavior in a simple way, "computational irreducibility". The empirical
Empiricism

In philosophy, empiricism is a theory of knowledge which asserts that knowledge arises from experience. Empiricism is one of several competing views about how we know "things," part of the branch of philosophy called epistemology, or "theory of knowledge"....
 fact
Fact

A fact is something said to be true or supposed to have happened, example: Kiira is mean, FACT. An idea becomes a fact after competent people have tested a hypothesis through the scientific method....
 is that the world of simple programs contains a great diversity of behavior
Behavior

Behavior or behaviour refers to the action s or reactions of an object or organism, usually in Relational theory to the environment. Behavior can be conscious or Unconscious mind, overt or covert, and voluntary or involuntary....
, 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

The question of free will is whether, and in what sense, rational agents exercise control over their actions and decisions. Addressing this question requires understanding the relationship between freedom and Causality, and determining whether the laws of nature are causally deterministic....
.

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 approximation
Approximation

An approximation is an Accuracy and precision representation of something that is still close enough to be useful. Although approximation is most often applied to numbers, it is also frequently applied to such things as Function , shapes, and physical laws....
s). However, more complex systems were still computationally irreducible and unpredictable. It is unknown what conditions would allow complex phenomenon to be described simply and predictably.

See also


  • Gödel’s Theorem
  • Computation
    Computation

    Computation is a general term for any type of information processing. This includes phenomena ranging from human thinking to calculations with a more narrow meaning....
  • Principle of Computational Equivalence
  • Artificial intelligence
    Artificial intelligence

    Artificial intelligence is the intelligence of machines and the branch of computer science which aims to create it. Major AI textbooks define the field as "the study and design of intelligent agents,"...
  • Robert Rosen
    Robert Rosen

    Robert Rosen was an United States theoretical biologist and professor of Biophysics at Dalhousie University....


External links and references


  • Weisstein, Eric W., et al., "". MathWorld -- A Wolfram Web Resource.
  • Wolfram, Stephen, "". Wolfram Media, Inc., May 14, 2002. ISBN 1-57955-008-8
    • Wolfram, Stephen, "". A New Kind of Science.
    • Wolfram, Stephen, "". A New Kind of Science
      A New Kind of Science

      A New Kind of Science is a controversial book by Stephen Wolfram, published in 2002. It contains an empirical and systematic study of computational systems such as cellular automata....
      .
    • Wolfram, Stephen, "". A New Kind of Science
      A New Kind of Science

      A New Kind of Science is a controversial book by Stephen Wolfram, published in 2002. It contains an empirical and systematic study of computational systems such as cellular automata....
      .
    • Wolfram, Stephen, "". Physics Review Letters, 1985.
  • Israeli, Navot, and Nigel Goldenfeld, "". Physics Review Letters, 2004.


  • "". ISAAC/EINSTein research and development.
  • Berger, David, "". Serendip's Bookshelves.
  • "". Physics Review Letter, March 4, 2004.
  • Tomasson, Gunnar, "". A New Kind of Science
    A New Kind of Science

    A New Kind of Science is a controversial book by Stephen Wolfram, published in 2002. It contains an empirical and systematic study of computational systems such as cellular automata....
    : The NKS Forum.