computational irreducibility
{{Short description|Concept proposed by Stephen Wolfram}}
{{Multiple issues|
{{Primary sources|date=April 2020}}
{{Original research|date=April 2020}}
{{More citations needed|date=May 2019}}
}}
Computational irreducibility suggests certain computational processes cannot be simplified such that the only way to determine the outcome of such a process is to go through each step of its computation. It is one of the main ideas proposed by Stephen Wolfram in his 2002 book A New Kind of Science, although the concept goes back to studies from the 1980s.{{Cite web |date=2022-06-06 |title=Multicomputational Irreducibility—Wolfram Physics Bulletins |url=https://bulletins.wolframphysics.org/2022/06/multicomputational-irreducibility/ |access-date=2025-03-23 |website=bulletins.wolframphysics.org |language=en}}
The idea
{{Expand section|date=January 2022}} Many physical systems are complex enough that they cannot be effectively measured. Even simpler programs contain a great diversity of behavior. Therefore no model can predict, using only initial conditions, 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 (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 are normally computationally irreducible.{{Cite web |title=Stephen Wolfram: A New Kind of Science {{!}} Online—Table of Contents |url=https://www.wolframscience.com/nks/ |access-date=2025-02-03 |website=www.wolframscience.com |language=en}}
Computational irreducibility explains why many natural systems are hard to predict or simulate. The Principle of Computational Equivalence implies these systems are as computationally powerful as any designed computer.
Implications
- There is 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 indescribable by reasonably "simple" laws.
Analysis
Navot Israeli and Nigel Goldenfeld found that some less complex systems behaved simply and predictably (thus, they allowed approximations). 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.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 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.
See also
External links and references
- Weisstein, Eric W., et al., "[http://mathworld.wolfram.com/ComputationalIrreducibility.html Computational irreducibility]". MathWorld—A Wolfram Web Resource.
- Wolfram, Stephen, "[http://www.wolframscience.com/nksonline A New Kind of Science]". Wolfram Media, Inc., May 14, 2002. {{ISBN|1-57955-008-8}}
- Wolfram, Stephen, "[http://www.wolframscience.com/nksonline/page-737 Computational irreducibility]". A New Kind of Science.
- Wolfram, Stephen, "[http://www.wolframscience.com/nksonline/page-1132a-text History of computational irreducibility]". A New Kind of Science.
- Wolfram, Stephen, "[http://www.wolframscience.com/reference/notes/1132a History of computational irreducibility notes]". A New Kind of Science.
- Wolfram, Stephen, "[http://www.stephenwolfram.com/publications/articles/physics/85-undecidability/2/text.html Undecidability and intractability in theoretical physics]". Physical Review Letters, 1985.
- Israeli, Navot, and Nigel Goldenfeld, "[https://arxiv.org/abs/nlin.CG/0309047 On computational irreducibility and the predictability of complex physical systems]". Physical Review Letters, 2004.
- "{{cite web|url=http://www.cna.org/isaac/Glossb.htm#ComputI|title=Computational Irreducibility|publisher=ISAAC/EINSTein research and development|archiveurl=https://web.archive.org/web/20111211073322/https://www.cna.org/isaac/Glossb.htm|archivedate=2011-12-11}}
- Berger, David, "[https://web.archive.org/web/20040513114212/http://serendip.brynmawr.edu/bookshelves/wolfram.html Stephen Wolfram, A New Kind of Science]". Serendip's Bookshelves.
- "[http://focus.aps.org/story/v13/st10 Complexity is Elusive]". Physical Review Letters, March 4, 2004.
- Tomasson, Gunnar, "[http://forum.wolframscience.com/archive/topic/113-1.html Scientific Theory and Computational Irreducibility]". A New Kind of Science: The NKS Forum.