Theory of Computational Irreducibility

2016-10-17 ☼ computation

In Stephen Wolfram’s book, A New Kind of Science, Wolfram put forth a theory that complex systems cannot be shortcut by math. In order to obtain the output of a program for a certain step, one must run that program for each step up until the desired step.

While studying cellular automata, Stephen Wolfram discovered that some of the simple programs used to generate cellular automata produced complex output. In his most famous example, named Rule 30, it produced really intricate patterns:

As one can see from the output of Rule 30, the output generated by running this program for 100, 1000, or 10000 more steps cannot be known. It can be computed, but the computation of each step depends on the result of computing the previous step. Therefore, we cannot create a traditional math function for generating the output for any step.

Prior to this discovery, Wolfram’s career as a scientist and engineer led him to believe that complex behavior was only possible through sophisticated programs. Rule 30, however, only consisted of some basic descriptions about how a cell should be shaded given the shading of the neighboring cells.

This set Wolfram on a path to examine our entire universe through this lens. He believes that the most fundamental aspect of our universe is computation. Put another way, our universe is the result of some program that has been running for many steps.

This has profound implications in how we think about intelligence, science, engineering, philosophy, and essentially all fields. It means that the computation responsible for the weather on Earth is no more and no less intelligent than the human brain. Both are the result of computation.

I will continue to explore these aspects in more details in this blog.