The Wolfram Atlas of Simple Programs The Wolfram Atlas of Simple Programs

System Categories Cellular Automata Turing Machines Mobile Automata Substitution Systems Tag Systems Register Machines Symbolic Systems Systems Based on Numbers Network Systems Multiway Systems Systems Based on Constraints Axiom Systems
About Simple Programs

The programs in the Atlas are among the simplest computational systems possible. But despite their simplicity, they are capable of computations as sophisticated as anything in our universe--and exhibit such a range of behavior that this website has been created to begin documenting it.

These programs are not like those written in familiar languages like C or Java. Instead of the thousand-page specifications typical of commonplace programming languages, the languages of these programs are usually described by a few sentences or a single picture. And while practical languages are designed so that a human can construct predictable structures, those of the Atlas have no such restriction--which is what allows them to so easily exhibit complex and unexpected behavior.

The fact that these systems follow a definite set of rules is their main similarity to concepts we are familiar with from computers. But science is based on the idea that nature also follows a definite set of rules. For the last three hundred years it has been assumed that these rules are mathematical. Yet as the Atlas demonstrates, existing human mathematics has not concerned itself with arbitrarily general systems. And if nature does follow definite rules, the computational system it defines can be expected to share properties which a vast range of other systems. The behavior discovered in the simple programs of the Atlas can therefore be expected to occur in nature--and processes that occur in nature will not be fundamentally different than what can be modelled with abstract systems.

Why this is so may not be immediately obvious. For certainly abstract computer programs and systems in nature are built up from completely different components. But a key unifying idea is that all processes, whether they are produced by human effort or occur spontaneously in nature, can be viewed as computations. And while one may have thought that computations performed by systems can vary as arbitrarily as their underlying setup, the surprising fact is that they do not. Effectively the same behavior emerges in a broad range of systems, completely independent of their details.

The Principle of Computational Equivalence takes this idea further, asserting that almost all processes that are not obviously simple correspond to a computation of equivalent sophistication. From this emerges a new kind of unity: for across a vast range of systems, from simple programs to brains to our whole universe, the principle implies that there is a basic equivalence that makes the same fundamental phenomena occurs, and allows the same basic scientific ideas and methods to be used.

So besides giving new building blocks for understanding the behavior of our Universe, working within the framework of simple programs can also give deep insight into a surprisingly wide array of issues outside of the mathematical formalism of traditional science--from the ultimate scope and limitations of science, to the question of human uniqueness and free will. And because simple programs are already capable of great sophistication, there is rarely a reason to go beyond them. One consequence is that besides experimentally addressing questions of scientific interest, they can be of great value from an educational point of view. On the one hand, if the essence of some powerful idea can be distilled into some simple structure, it will be easier for the mind to absorb. And on the other, the simpler a system is, the more likely it is to appear in a variety of contexts.

Yet despite all the useful applications of simple programs, it is important to keep in mind that NKS is a basic science, with its own set of questions that are worthwhile independently of its various connections. And although the PCE asserts a certain uniformity regardless of individual particularities, it also implies that these particularities are the only thing that make any system--including us humans--special. For they are what lead to the phenomenon of computational irreducibility, and assure that there will be an endless series of questions worth asking - and answering within the structure the Atlas now provides.

Kovas Boguta
Wolfram Science Group

   © Wolfram Research, Inc.