The World of Simple Programs

At the beginning of the last chapter we asked the basic question of what simple programs typically do. And as a first step towards answering this question we looked at several specific examples of a class of programs known as cellular automata. The basic types of behavior that we found are illustrated in the pictures on the next page. In the first of these there is pure repetition, and a very simple pattern is formed. In the second, there are many intricate details, but at an overall level there is still a very regular nested structure that emerges.

In the third picture, however, one no longer sees such regularity, and instead there is behavior that seems in many respects random. And finally in the fourth picture there is what appears to be still more complex behavior—with elaborate localized structures being generated that interact in complex ways.

At the outset there was no indication that simple programs could ever produce behavior so diverse and often complex. But having now seen these examples, the question becomes how typical they are. Is it only cellular automata with very specific underlying rules that produce such behavior? Or is it in fact common in all sorts of simple programs?

My purpose in this chapter is to answer this question by looking at a wide range of different kinds of programs. And in a sense my approach is to work like a naturalist—exploring and studying the various forms that exist in the world of simple programs.

I start by considering more general cellular automata, and then I go on to consider a whole sequence of other kinds of programs—with underlying structures further and further away from the array of black and white cells in the cellular automata of the previous chapter.

And what I discover is that whatever kind of underlying rules one uses, the behavior that emerges turns out to be remarkably similar to the basic examples that we have already seen in cellular automata. Throughout the world of simple programs, it seems, there is great universality in the types of overall behavior that can be produced. And in a sense it is ultimately this that makes it possible for me to construct the coherent new kind of science that I describe in this book—and to use it to elucidate a large number of phenomena, independent of the particular details of the systems in which they occur.

The core of the chapter is the discovery that simple rules can lead to immense complexity. This interactive demo allows you to explore the behavior of any of the 256 "elementary" cellular automaton rules. See for yourself how a tiny change in the rule can shift behavior from simple repetition to apparent randomness.

Repetition and nesting are widespread themes in many cellular automata. But as we saw in the previous chapter, it is also possible for cellular automata to produce patterns that seem in many respects random. And out of the 256 rules discussed here, it turns out that 10 yield such apparent randomness. There are three basic forms, as illustrated on the facing page.

Beyond randomness, the last example in the previous chapter was rule 110: a cellular automaton whose behavior becomes partitioned into a complex mixture of regular and irregular parts. This particular cellular automaton is essentially unique among the 256 rules considered here: of the four cases in which such behavior is seen, all are equivalent if one just interchanges the roles of left and right or black and white.

The central discovery of this chapter is that the phenomenon of complexity is not unique to cellular automata. It emerges in a vast range of other simple programs, from mobile automata to Turing machines. Below you can see demonstrations of these systems, which despite having entirely different structures, can exhibit similar complex behaviors.

The exploration of these diverse systems leads to several profound conclusions. The phenomenon of complexity is quite universal and independent of the specific details of a system. The threshold for complexity is surprisingly low—even very simple rules can produce behavior of great complexity. And finally, adding more complexity to the rules does not necessarily yield more complex behavior.

This universality is what makes it possible to construct a coherent new kind of science, implying that general principles can govern the behavior of a wide range of systems, independent of their precise details.