Computational irreducibility

Many systems, both physical and computational, are complex enough that they cannot be effectively modeled. Even simple programs can give rise to a great diversity of behavior. In many cases, no model can predict from initial conditions exactly what will occur in a given system without doing as much computational work as the system itself performs. Wolfram terms this inability to "shortcut" a system (or "program"), or otherwise describe its behavior in a simple way, "computational irreducibility." The idea argues that there are circumstances where theoretical prediction is intractable. Wolfram describes several phenomena that are normally computationally irreducible. Computationally irreducibility 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. 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==

• 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". A New Kind of Science. • Wolfram, Stephen, "History of computational irreducibility notes". A New Kind of Science. • Wolfram, Stephen, "Undecidability and intractability in theoretical physics". Physical Review Letters, 1985. • Israeli, Navot, and Nigel Goldenfeld, "On computational irreducibility and the predictability of complex physical systems". Physical Review Letters, 2004. • " • Berger, David, "Stephen Wolfram, A New Kind of Science". Serendip's Bookshelves. • "Complexity is Elusive". Physical Review Letters, March 4, 2004. • Tomasson, Gunnar, "Scientific Theory and Computational Irreducibility". A New Kind of Science: The NKS Forum. ==References==