Computational irreducibility is a profound concept about how the world works. In many complex systems, the only way to know what will happen is to let them run. Simple rules can produce unpredictable complexity, and when no shortcut can predict the outcome faster than executing each step, the system is computationally irreducible.
The concept was proposed by mathematician Stephen Wolfram in his book, A New Kind of Science, which I read early on during my PhD. At some point, I even taught an introductory course on it. The relevant sections from the book are available for free here.
One implication is that a system that is based on simple structures can exhibit behaviors that are not predictable by simple laws. Most of biology is computationally irreducible, which means that we’ll never be able to fully predict how organisms will behave. There will always be something to be learned from real-life experiments.
Another implication is for free will:
For if the evolution of a system corresponds to an irreducible computation then this means that the only way to work out how the system will behave is essentially to perform this computation – with the result that there can fundamentally be no laws that allow one to work out the behavior more directly. And it is this, I believe, that is the ultimate origin of the apparent freedom of human will. For even though all the components of our brains presumably follow definite laws, I strongly suspect that their overall behavior corresponds to an irreducible computation whose outcome can never in effect be found by reasonable laws.
Computational irreducibility doesn’t imply that there isn’t any predictability at all. As Wolfram writes,
Any system that shows overall computational irreducibility there must inevitably be an infinite number of “pockets of computational reducibility”, in effect associated with “simplifying features” of the behavior of the system.
This post is part of the Encyclopedia of Concepts.
Nehaveigur 