Computational irreducibility is one of the main ideas proposed by

Stephen Wolfram Stephen Wolfram (; born 29 August 1959) is a British-American computer scientist, physicist, and businessman. He is known for his work in computer science, mathematics, and theoretical physics. In 2012, he was named a fellow of the American Ma ...

in his 2002 book ''

A New Kind of Science ''A New Kind of Science'' is a book by Stephen Wolfram, published by his company Wolfram Research under the imprint Wolfram Media in 2002. It contains an empirical and systematic study of computational systems such as cellular automata. Wolfram c ...

'', although the concept goes back t
studies from the 1980s

The idea

Many

physical systems A physical system is a collection of physical objects. In physics, it is a portion of the physical universe chosen for analysis. Everything outside the system is known as the environment. The environment is ignored except for its effects on the ...

are complex enough that they cannot be effectively measured. Even simpler programs contain a great diversity of

behavior Behavior (American English) or behaviour (British English) is the range of actions and mannerisms made by individuals, organisms, systems or artificial entities in some environment. These systems can include other systems or organisms as wel ...

. Therefore no model can predict using only

initial conditions In mathematics and particularly in dynamic systems, an initial condition, in some contexts called a seed value, is a value of an evolving variable at some point in time designated as the initial time (typically denoted ''t'' = 0). For ...

, exactly what will occur in a given physical system before an experiment is conducted. Because of this problem of undecidability in the formal language of computation, Wolfram terms this inability to "shortcut" a

system A system is a group of Interaction, interacting or interrelated elements that act according to a set of rules to form a unified whole. A system, surrounded and influenced by its environment (systems), environment, is described by its boundaries, ...

(or "program"), or otherwise describe its behavior in a simple way, "computational irreducibility." The idea demonstrates that there are occurrences where theory's predictions are effectively not possible. Wolfram states several

phenomena A phenomenon ( : phenomena) is an observable event. The term came into its modern philosophical usage through Immanuel Kant, who contrasted it with the noumenon, which ''cannot'' be directly observed. Kant was heavily influenced by Gottfried W ...

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 scientifically-based

free will Free will is the capacity of agents to choose between different possible courses of action unimpeded. Free will is closely linked to the concepts of moral responsibility, praise, culpability, sin, and other judgements which apply only to actio ...

Implications

* There is no easy theory for any behavior that seems

complex Complex commonly refers to: * Complexity, the behaviour of a system whose components interact in multiple ways so possible interactions are difficult to describe ** Complex system, a system composed of many components which may interact with each ...

. * 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

Navot Israeli and Nigel Goldenfeld found that some less complex systems behaved simply and predictably (thus, they allowed

approximation An approximation is anything that is intentionally similar but not exactly equality (mathematics), equal to something else. Etymology and usage The word ''approximation'' is derived from Latin ''approximatus'', from ''proximus'' meaning ''very ...

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.

Compatibilism

Marius Krumm and Markus P Muller tie computational irreducibility to

Compatibilism Compatibilism is the belief that free will and determinism are mutually compatible and that it is possible to believe in both without being logically inconsistent. Compatibilists believe that freedom can be present or absent in situations for re ...

.Computational irreducibility and compatibilism: towards a formalization https://arxiv.org/pdf/2101.12033.pdf They refine concepts via the intermediate requirement of a new concept called

computational sourcehood Computation is any type of arithmetic or non-arithmetic calculation that follows a well-defined model (e.g., an algorithm). Mechanical or electronic devices (or, History of computing hardware, historically, people) that perform computations are ...

that demands essentially full and almost-exact representation of features associated with problem or process represented, and a full no-shortcut computation. The approach simplifies conceptualization of the issue via the ''No Shortcuts'' metaphor. This may be analogized to the process of cooking, where all the ingredients in a recipe are required as well as following the 'cooking schedule' to obtain the desired end product. This parallels the issues of the profound distinctions between similarity and identity.

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. ** Wolfram, Stephen, "
Computational irreducibility
'". A New Kind of Science. ** Wolfram, Stephen, "
History of computational irreducibility
'".

. ** Wolfram, Stephen, "
History of computational irreducibility notes
'".

. ** Wolfram, Stephen, "
Undecidability and intractability in theoretical physics
'".

Physical Review Letters ''Physical Review Letters'' (''PRL''), established in 1958, is a peer-reviewed, scientific journal that is published 52 times per year by the American Physical Society. As also confirmed by various measurement standards, which include the ''Journa ...

, 1985. * Israeli, Navot, and

Nigel Goldenfeld Nigel David Goldenfeld (born May 1, 1957) is a Swanlund Chair, Professor of Physics Department in the University of Illinois at Urbana-Champaign (UIUC), the director of the NASA Astrobiology Institute for Universal Biology, and the leader of the ...

, "
On computational irreducibility and the predictability of complex physical systems
'".

, 2004. * " * Berger, David, "
Stephen Wolfram, A New Kind of Science
'". Serendip's Bookshelves. * "
Complexity is Elusive
'". Physical Review Letters, March 4, 2004. * Tomasson, Gunnar, "

'".

: The NKS Forum.

References