The World of Simple Programs
This chapter from Stephen Wolfram's "A New Kind of Science" explores a fundamental question: what do simple programs typically do? By examining various computational systems, from cellular automata to Turing machines, it reveals a surprising and universal phenomenon: even programs with extremely simple rules can produce behavior of immense complexity. This interactive application allows you to explore these systems and discover the core principles for yourself.
Exploring Cellular Automata
Cellular automata are the first and one of the most compelling examples in the book. They consist of a line of cells, each with a color, that evolves in discrete steps according to a simple rule based on the colors of its neighbors. Below, you can explore the behavior of the 256 "elementary" cellular automata, which use two colors and consider the cell itself and its immediate left and right neighbors.
Classification of Behavior
Despite the vast number of rules, the behaviors they produce can be grouped into four main classes: simple repetition, nesting (fractal patterns), randomness, and complex localized structures. This chart shows the approximate distribution of these behaviors among the 88 unique elementary rules.
Key Examples
Rule 250 (Repetition)
Rule 90 (Nesting)
Rule 30 (Randomness)
Rule 110 (Complexity)
Universality across Different Systems
A key discovery is that the phenomenon of complexity is not unique to cellular automata. The same classes of behavior appear in a vast range of other simple programs, demonstrating a principle of universality. This section provides a glimpse into some of these other systems, showing how different underlying structures can lead to remarkably similar outcomes.
Mobile Automata
Instead of updating all cells at once, a mobile automaton has a single "active cell" that moves and updates its color based on its neighbors. While complex behavior is rarer than in cellular automata, it still emerges, often requiring slightly more complex rules.
An example of a mobile automaton exhibiting complex, seemingly random behavior.
Core Discoveries and Principles
The exploration of these diverse systems leads to several profound conclusions about the nature of computation and complexity. These principles form the foundation of "A New Kind of Science".
Universality of Complexity
Complex behavior is not a rare or special phenomenon. It is a universal feature of computation, appearing across a vast range of systems with different underlying structures.
Low Threshold for Complexity
Extremely simple rules are sufficient to produce the most complex behavior. There is a surprisingly low threshold in rule complexity that, once crossed, unlocks the full potential for complexity.
Complexity Doesn't Imply Complex Rules
Making the underlying rules more complex does not necessarily lead to more complex overall behavior. The essential ingredients for complexity are already present in very simple systems.