One thing about all the systems I've showed so far is that they all just evolve sequentially from one step to the next. Well, here's one that doesn't. [See A New Kind of Science, page 205.]
I call it a multiway system. It has rules for rewriting strings, that get applied in all possible ways. It's kind of like a semi-semi-group. And again, even simple rules give all sorts of complex behavior. [See A New Kind of Science, page 206.]
One doesn't actually have to have any kind of process of evolution at all. Like consider a tiling problem, where one has the constraint that around every cell, only certain neighborhoods are allowed. [See A New Kind of Science, page 213.]
Well, with exactly this setup, it turns out that if one can tile the plane at all, then one can always do it periodically in one of these 171 ways. [See A New Kind of Science, page 214.]
But if one also says that the plane can't be all white, then about the 19 millionth constraint gives this. [See A New Kind of Science, page 219.]
It's the first tiling necessarily nonperiodic tiling. Kind of the minimal square quasicrystal. Or an interesting two-dimensional subshift of finite type.
Well, going a bit further one sees cases like this. [See A New Kind of Science, page 221.]
A tiling forced to make a rule 30 pattern. Which would be pretty interesting to find in a real crystal.
Well, OK, what about numbers? Here are the digit sequences one gets by successively incrementing an integer. [See A New Kind of Science, page 118.]
A simple nested pattern.
Here are powers of two in base two. [See A New Kind of Science, page 119.]
Quite trivial. But here are the powers of 3 in base 2. [See A New Kind of Science, page 119.]
Kind of like a minimal linear congruential pseudorandom generator. And already remarkably complicated--very much like a cellular automaton. And actually, in cases like these, it turns out to be exactly a cellular automaton. [See A New Kind of Science, page 614.]
Here's another example with digits. [See A New Kind of Science, page 126.]
Iterating addition and digit reversal.
Well, OK, what if one deals with integers as a whole, not digit sequences. Let's say one defines a recursive function. Well, again there are remarkably simple ones that give really complex behavior. [See A New Kind of Science, page 130.]
Primitive recursive functions are particularly easy to enumerate. And then I can tell you that this is the very simplest one that gives complex behavior. [See A New Kind of Science, page 908.]
Last summer we had an NKS summer school, and did a class project on recursive functions. Where we found some really neat things. Like here's the very simplest nestedly recursive function with complex behavior.
OK, what about real numbers? Here's a continuous cellular automaton, with values from 0 to 1 at each cell. [See A New Kind of Science, page 157.]
But what about PDEs? Well, most of the PDEs people normally study have rather simple behavior, at least with simple initial conditions. [See A New Kind of Science, page 163.]
Like here's the diffusion equation. And the wave equation. And the sine-Gordon equation.
But a few years ago I decided just to do a systematic search of possible PDEs. Many of them have pathologies. But after a little while I found these. [See A New Kind of Science, page 165.]
They're just simple nonlinear wave equations. But even starting from a little Gaussian they give all this stuff. That looks a bit like rule 30.
Of course, it's hard to know exactly what these PDEs do. We've been using these as test cases for numerical PDE solving in Mathematica for ages. But without already more or less knowing the answer, it's hard for numerical analysis to be sure things are real.
But with the likes of rule 30 it's a different story. [See A New Kind of Science, page 30.]
Because the bits are the bits. And so there's no question one's discovered something real.
And actually it's so straightforward to get, grade schoolers could do it. And I sometimes wonder whether, a bit like these... [See A New Kind of Science, page 43.]
...some Babylonian mosaic of rule 30 might one day be unearthed.
But I doubt it. Because I think if rule 30 had been known in antiquity, science and math would have developed rather differently. Of course, now that one's seen the rule 30 phenomenon, one can go back and find hints of it from really long ago.
Like the primes, for example. The Greeks knew an easy rule for making them. [See A New Kind of Science, page 122.]
But the pattern of primes that comes out is irregular and in some ways quite random.
Or the digits of pi. [See A New Kind of Science, page 137.]
Which seem for all practical purposes random.
There are all sorts of examples. Particularly from recreational math.
But somehow they were always treated as curiosities. That didn't fit together, and didn't really seem to add up to much.
Well, here's the critical fact: they're all signs of a very general phenomenon. That's deep and important. And there's a whole new conceptual framework that can be built around it--a whole new kind of science. [See A New Kind of Science, page 30.]
It changes a lot of things. Like the way we approach modelling.
I mean, for three hundred years there's been this idea that if one wants to make a really good model of something, it should be based on equations. And that certainly worked well for Newton and friends in figuring out orbits of comets. And for lots and lots of things since then. But when we see behavior that really looks complex, it hasn't worked very well.
Now, if one's going to be able to do theoretical science, the systems one studies had better follow definite rules. But why should those rules be based on the constructs we've studied in mathematics: on numbers and calculus and so on? Can't they be more general?
In the past one wouldn't have had much of a way to think about more general rules. But now we have computers, with programs that in effect implement arbitrarily general rules. Of course, the programs we use in practice are long and complicated, set up for particular purposes.
But here's a basic science question that's at the core of the new kind of science I've been building. If one just enumerates simple programs, what do they do?
In computer science we're used to studying programs constructed for particular purposes. But what if we just go out and explore the computational universe?
It's exciting. It's kind of like 400 years ago when telescopes were first invented. One could just point one's telescope somewhere in the sky and see what's out there. Well, now we get to do that in the computational universe.
And actually, being able to do that is one of the main reasons I built Mathematica. People of course use Mathematica a lot to do traditional math, and we're proud of that. But at its core Mathematica is a lot more general. General enough to really let one explore the computational universe.
And it's incredible what happens when one does that. First, one sees all this strange and wonderful flora and fauna. But then--and it took me years-- one gradually builds new principles, and new intuition.
Our normal intuition tends to be that it's complicated to make something complicated. But that's just not true in the general computational universe. Look at rule 30. But in doing things like engineering we usually have the constraint that we have to foresee what the things we build are going to do. And so we've been forced to use only rules that have simple, foreseeable, behavior.
But the point is that nature is under no such constraint. So there's nothing wrong with it using rules like rule 30. And I think that's the secret of how it makes complexity.
Well, OK, so how can we use what we learn from simple programs? We can make technology. New kinds of devices. Or efficient algorithms that don't just have iteration, or recursion, but rule 30 type behavior.
We can also make new kinds of models of things. In the past, if we saw this ...
... we'd probably assume its rules were really complicated. But now we might just search, and find that this is all that's going on.
So, OK, so let's say we have a system in nature. Like a snowflake. [See A New Kind of Science, page 370.]
How do we make a good model of it? Not just a picture, but a model of how it works. Well, snowflakes grow by adding pieces of ice to their surface. And we can make a simple hexagonal cellular automaton that does that. [See A New Kind of Science, page 369.]
Not much like a snowflake. But let's add the next important effect: growth inhibition from latent heat. Let's try the simplest cellular automaton rule that captures that. Here's what we get. [See A New Kind of Science, page 371.]
And here are all the stages. [See A New Kind of Science, page 371.]
Remarkably like real snowflakes. It really seems like we've captured what makes snowflakes have the shapes they do. And we get predictions, like that big snowflakes have little holes in them. Which indeed they do.
OK, but there are obviously details of snowflakes that we haven't captured. But that's always going to happen. Because the whole point of a model is to capture certain features, and idealize everything else away. And depending on what one's interested in, one may pick different features. And so the cellular automaton model is good, for example, if one's interested in finding a snowflake shape distribution. But it's not so useful if one wants to calculate how fast each arm grows at a certain temperature.
There are certainly traditional PDEs for snowflakes. But they're complicated and hard to solve. And the point is that for many questions, a cellular automaton model picks out much more directly what one really needs to know.
And it also lets one generalize, for example enumerating other shapes that might grow. ([See A New Kind of Science, page 373.]
OK. Let's take another example. Fluid turbulence. [See A New Kind of Science, page 377.]
Where does all that randomness in a turbulent flow come from?
Well, one can ask that about randomness in any system. And I think there are really three ways randomness can arise.
First, it can be continually injected from the environment. Like with a boat bobbing on an ocean. Where there's random motion because of the randomness of the ocean.
Usually we'd build a stochastic or probabilistic model for that, with randomness built right in. [See A New Kind of Science, page 591.]
But in recent decades another source of randomness that's been talked about is chaos theory. Where the randomness isn't continually injected, but instead comes from the details of the initial conditions for the system. Like when one tosses a coin or spins a wheel. Where the final outcome depends sensitively on the initial speed. [See A New Kind of Science, page 305.]
Well, there are stronger version of this, where one's effectively taking
numbers that represent initial conditions, and continually excavating higher and
higher order digits from them. Like in the shift map,
x[t+1] = FractionalPart[2 x[t]]. [See A New Kind of Science, page 308.]