A New Kind of Science and the Future of Mathematics (2004)

(AMS/MAA joint invited address at the Joint Mathematics Meetings, Phoenix, Arizona, January 7, 2004)

Thank you for that nice introduction. And thank you for inviting me.

Well, what I'd like to do this morning is to talk about some things I've done over the course of many years--that I think have some significance for mathematics and mathematicians. Mostly I'm just going to sketch things; if you want details, they're mostly in that big book.

Well, I guess it all started with a little computer experiment that I did at the beginning of the 1980s. That I'd like to show you.

Well, I'd been working on some basic problems in physics, and a little bit also in biology. And I'd wanted the simplest possible models. And that led me to a particular kind of very simple model--that turned out to be a version of what had been called a cellular automaton.

Here's how a one- dimensional cellular automaton works. It's got a line of cells, each either black or white. [See A New Kind of Science, page 24.]

And it evolves down the page, in discrete steps. [See A New Kind of Science, page 24.]

Replay Animation

With the color of each cell at each step being determined by a fixed rule-- from the color of the cell and its neighbors on the step before. So that if a sub i is the color of the ith cell at step t:

Well, you can represent that rule by an icon that just shows what happens in each of the 8 possible cases. [See A New Kind of Science, page 24.]

So starting off for example from a single black cell, this rule just gives a simple uniform region of black. [See A New Kind of Science, page 24.]

OK, let's try changing the rule a bit. Here's another example. [See A New Kind of Science, page 25.]

This gives a checkerboard pattern.

So far none of this is at all surprising. We've got very simple rules, and we're getting very simple behavior out.

So is that always how it works? Well, take a look at this. [See A New Kind of Science, page 25.]

It doesn't seem to repeat. Let's run it longer. [See A New Kind of Science, page 26.]

Well, it's a very regular nested fractal pattern.

And perhaps there's a general result: that if the rule and then initial conditions are simple, then the behavior will always have to be correspondingly regular and simple. Well, at least back in 1981 that's what I assumed was true.

But one day I decided to do a systematic experiment. And just to run every single one of the possible simplest cellular automata.

There are 256 of them, and you can number their rules like this. [See A New Kind of Science, page 53.]

And here's what they all do. There's quite a bit of diversity. But mostly the behavior looks pretty simple. Uniform, or repetitive, or at least nested. [See A New Kind of Science, page 55.]

But if you look carefully, there are some cases where other things seem to be going on. The first one is rule 30. [See A New Kind of Science, page 27.]

So let's take a look at that.

It seems quite complicated. It's asymmetric because the rule was. Let's try running it a bit longer. [See A New Kind of Science, page 30.]

Well, there are a bunch of periodic stripes over on the left. But otherwise, this looks really complicated. Actually kind of random.

Well, when I first saw this, I thought it must just be a problem with our visual system. That somehow there is regularity, but our visual system just doesn't pick it up.

So I started trying all sorts of statistical and mathematical methods on it. And there are certainly lots of things one can say about rule 30. It's an onto map. Small perturbations always grow. It has a certain spectrum of periodic points.

And in the pattern here a depth d diagonal has period at most 2^d. On the left, the period's much much lower. But on the right, it's close to the bound.

And let's say one looks at the center vertical column of cells. One can imagine using it to make a (quotes) "random walk". Here are the first million steps. [See A New Kind of Science, page 871.]

It certainly doesn't ever seem to repeat. And if one adds in an occasional neighboring cell, one can prove that. And in fact it seems to pass every standard statistical test of randomness. Including cryptanalytic ones.

And actually we've been using essentially this sequence to make random integers in Mathematica for the past 16 years. And it's passed zillions of tests--even while many other proposed pseudorandom generators have failed. [See A New Kind of Science, page 30.]

But still, rule 30 is so simple underneath, one might figure that out there in the world of math, there has to be *some* way to analyse it.

Well, as a warmup let's take a look at rule 90. [See A New Kind of Science, page 26.]

It turns out this rule just adds neighbors mod 2.

So it makes Pascal's triangle mod 2. [See A New Kind of Science, page 611.]

And that means you can find the color at position x and step t from a binomial coefficient. Or actually also just by taking bitwise ORs of the digits in the integers x and t. [See A New Kind of Science, page 608.]

Well, here's another example like that. Rule 150.

Another additive rule. [See A New Kind of Science, page 611.]

But now dealing with trinomials, not binomials. So it involves Gegenbauer functions. [See A New Kind of Science, page 610.]

Well, any additive rule will give a nested pattern. That I suspect can be described by some generalized hypergeometric function.

But rule 30 isn't additive, and there's no special function that's going to describe it. [See A New Kind of Science, page 30.]

Of course at each step it's just a simple Boolean function. [See A New Kind of Science, page 616.]

Which one can write in several ways.

But the point is that its iterates aren't simple. Iterating rule 90, everything stays pretty simple. [See A New Kind of Science, page 618.]

But iterating rule 30, it doesn't. [See A New Kind of Science, page 618.]

These are the minimal DNF expressions one gets up to 5 steps. And here are the absolute minimal NAND trees up to two steps. [See A New Kind of Science, page 619.]

And one can go on. But the basic story is that there's definitely something real going on. There's definitely something that's stopping us from cracking rule 30. [See A New Kind of Science, page 30.]

But is that interesting? Is it just some isolated curiosity about rule 30? Or is it the first sign of some deep and general phenomenon?

Well, here are some other cellular automata. [See A New Kind of Science, page 67.]

Replay Animation

Very much the same kind of thing happens. In one dimension. Or two dimensions. [See A New Kind of Science, page 174.]

Or three. [See A New Kind of Science, page 183.]

But what about other systems? Cellular automaton rules have lots of special features. So what happens if you give those up?

Here's a Turing machine for example. [See A New Kind of Science, page 78.]

In many ways it's like a cellular automaton. But one difference is that it only ever updates one cell at each step.

Well, the first few thousand Turing machines do only these kinds of things. [See A New Kind of Science, page 79.]

But if one keeps going, still with very simple rules, one gets this. [See A New Kind of Science, page 81.]

The same kind of thing we saw in cellular automata.

And here's an iterated finite automaton that some group theory folk recently got me interested in. [See A New Kind of Science Forum]

Again, same story.

Well, what happens if we don't have a fixed array of cells? Here's a sequential substitution system, that just iteratively rewrites strings. [See A New Kind of Science, page 90.]

And it takes only simple rules to get very complex behavior. [See A New Kind of Science, page 92.]

Here's a rather different type of system: a register machine. [See A New Kind of Science, page 100.]

It's like a minimal idealization of machine language. And this is the smallest register machine with complex behavior.

Here are what I call symbolic systems. [See A New Kind of Science, page 102.]

Kind of minimal idealizations of the underlying structure of Mathematica. Or generalizations of combinators. And again, it's the same story. [See A New Kind of Science, page 104.]