Cellular Automata and Rule 30 (Stephen Wolfram) | AI Podcast Clips

So in 2002, you published a new kind of science to which sort of, on a personal level, I can credit my love for cellular automata and computation in general. I think a lot of others can as well. Can you briefly describe the vision, the hope, the main idea presented in this 1200 page book?

Sure, although it took 1200 pages to say in the book. So, no, the real idea, it's kind of a good way to get into it, is to look at sort of the arc of history and to look at what's happened in kind of the development of science. I mean, there was this sort of big idea in science about 300 years ago that was, let's use mathematical equations to try and describe things in the world. Let's use sort of the formal idea of mathematical equations to describe what might be happening in the world, rather than, for example, just using sort of logical augmentation and so on. Let's have a formal theory about that. And so there'd been this 300 year run of using mathematical equations to describe the natural world, which had worked pretty well. But I got interested in how one could generalize that notion. You know, there is a formal theory, there are definite rules, but what structure could those rules have? And, and so what I got interested in was let's generalize beyond the sort of purely mathematical rules, and we now have this sort of notion of programming and computing and so on. Let's use the kinds of rules that can be embodied in programs as a sort of generalization of the ones that can exist in mathematics as a way to describe the world. And so my kind of favorite version of these kinds of simple rules are these things called cellular automata. And so typical case.

So wait, what are cellular automata?

Fair enough. So typical case of a cellular automaton, it's an array of cells. It's just a line of discrete cells. Each cell is either black or white. And in a series of steps that you can represent as lines going down a page, you're updating the color of each cell according to a rule that depends on the color of the cell above it and to its left and right. So it's really simple. So a thing might be, you know, if the cell and its right neighbor are not the same, or the cell on the left is black or something, then make it black on the next step, and if not, make it white. Typical rule, that rule. I'm not sure I said it exactly right, but a rule very much like what I just said has the feature that if you started off from just One black cell at the top. It makes this extremely complicated pattern. So some rules you get a very simple pattern. Some rules you have, the rule is simple. You start them off from a sort of simple seed. You just get this very simple pattern. But other rules, and this was the big surprise when I started actually just doing the simple computer experiments to find out what happens is that they produce very complicated patterns of behavior. So for example, this Rule 30 rule has the feature you started off from. Just one black cell at the top makes this very random pattern. If you look like at the center column of cells, you get a series of values. You know, it goes black, white, black, black, whatever it is, that sequence seems for all practical purposes random. So it's kind of like in math, you know, you compute the digits of PI, 3.1415926, whatever those digits once computed. I mean, the scheme for computing PI, it's the ratio of the circumference to diameter of a circle. Very well defined. But yet once you've generated those digits, they seem for all practical purposes completely random. And so it is with Rule 30 that even though the rule is very simple, much simpler, much more sort of computationally obvious than the rule for generating digits of PI, even with a rule that simple, you're still generating immensely complicated behavior.

Yeah, so if we could just pause on that. I think you probably said it and looked at it so long you forgot the magic of it. Or perhaps you don't, you still feel the magic. But to me, if you never seen sort of, I would say, what is it? A one dimensional, essentially automata. Right. And, and you were to guess what you would see if you have some cells that only respond to its neighbors.

Right.

If you were to guess what kind of things you would see, like my, my initial guess, like even when I first like open your book, A New Kind of Science. Right. My initial guess is you would see. I mean, it would be very simple stuff.

Right.

And I think it's a magical experience to realize the kind of complexity you mentioned. Rule 30, still your favorite cellular automaton.

Still my favorite rule. Yes.

It, you get complexity, immense complexity. You get arbitrary complexity.

Yes.

And when you say randomness down middle column, you know, that's just what one cool way to say that there's incredible complexity. And that's just, just, I mean, that's a magical idea. However, you start to interpret it, all the reducibility discussions, all that. But it's just, I think that has profound philosophical kind of notions around it too. It's not just, oh, Yeah, I mean, it's transformational about how you see the world. I think for me it was transformational. I don't know, we can, we can have all kinds of discussions about computation and so on, but just, you know, I sometimes think if I were on a desert island and was, I don't know, maybe it was some psychedelics or something, but if I had to take one book, I mean, new kind of science would be it. Because you can just enjoy that notion for some reason. It's a deeply profound notion, at least to me.

I find it that way. Yeah, I mean, look, it was a very intuition breaking thing to discover. I mean, it's kind of like you point the computational telescope out there and suddenly you see, I don't know, in the past it's kind of like moons of Jupiter or something. But suddenly you see something that's kind of very unexpected. And Rule 30 was very unexpected for me. And the big challenge at a personal level was to not ignore it. I mean, people, you know, in other words, you might say, you know, it's a bug.

What would you say? Yeah, what would you say?

Yeah, I mean, I.

What are we looking at, by the way?

Well, I was just generating here I'll actually generate a Rule 30 pattern. So that's the rule for Rule 30. And it says, for example, it says here, if you have a black cell in the middle and a black cell to the left and white cell to the right, then the cell on the next step will be white. And so here's the actual pattern that you get starting off from a single black cell at the top there.

And then that's the initial state, initial.

Condition, that's the initial thing. You just start off from that and then you're going down the page and at every step you're just applying this rule to find out the new value that you get. And so you might think, rule that simple. You got to get. There's gotta be some trace of that simplicity here. Okay, we'll run it, let's say for 400 steps. That's what it does. It's kind of aliasing a bit on the screen there, but you can see there's a little bit of regularity over on the left. But there's a lot of stuff here that just looks very complicated, very random. And that's a big sort of shock to. Was a big shock to my intuition at least that that's possible.

The mind immediately starts. Is there a pattern? There must be a repetitive pattern.

Yeah, there must be. That's where the mind So I spent so indeed, that's what I thought at first. And I thought, I thought, well, this is kind of interesting, but, you know, if we run it long enough, we'll see, you know, something will resolve into something simple. And, you know, I did all kinds of analysis of using mathematics, statistics, cryptography, whatever, whatever to try and crack it. And I never succeeded. And after I hadn't succeeded for a while, I started thinking, maybe there's a real phenomenon here that is the reason I'm not succeeding. Maybe. I mean, the thing that for me was sort of a motivating factor was looking at the natural world and seeing all this complexity that exists in the natural world. The question is, where does it come from? What secret does nature have that lets it make all this complexity that we humans, when we engineer things typically are not making? We're typically making things that at least look quite simple to us. And so the shock here was even from something very simple, you're making something that complex, maybe this is getting at sort of the secret that nature has that allows it to make really complex things, even though its underlying rules may not be that complex.

How did it make you feel? If we look at the Newton apple was there, you took a walk and something. It profoundly hit you, or was this a gradual thing, a lobster being boiled?

The truth of every sort of science discovery is it's not that gradual. I mean, I've spent, I happen to be interested in scientific biography kinds of things. And so I've tried to track down how did people come to figure out this or that thing. And there's always a long kind of sort of preparatory. There's a need to be prepared in a mindset which it's possible to see something. I mean, in the case of Rule 30, I realized around June 1, 1984, was kind of a silly story in some ways. I finally had a high resolution laser printer, so I was able. So I thought I'm going to generate a bunch of pictures of the solar automata and I generate this one. And I put it. I was on some plane flight to Europe and I have this with me. And it's like, I really should try to understand this. And this is really, I really don't understand what's going on. And that was kind of the, you know, slowly trying to, trying to see what was happening. It was depressingly unsudden, so to speak, in the sense that a lot of these ideas, like principle of computational equivalence, for example, you know, I thought, well, that's a possible thing. I didn't Know if it's correct, still didn't know for sure that it's correct. But it's sort of a gradual thing that these things gradually kind of become seem more important than one thought. I mean, I think the whole idea of studying the computational universe of simple programs, it took me probably a decade, decade and a half to kind of internalize that. That was really an important idea. And I think, you know, if it turns out we find the whole universe lurking out there in the computational universe, that's a good, you know, it's a good Brownie point or something for the whole idea. But I think that the, the thing that's strange in this whole question about finding this different raw material for making models of things, what's been interesting in the arc of history is for 300 years it's kind of like the mathematical equations approach. It was the winner. It was the thing you want to have a really good model for something, that's what you use. The thing that's been remarkable is just in the last decade or so, I think one can see a transition to using not mathematical equations, but programs as sort of the raw material for making models of stuff. And that's pretty neat. And it's kind of, you know, as somebody who's kind of lived inside this paradigm shift, so to speak, it is bizarre. I mean, no doubt in sort of the history of science that will be seen as an instantaneous paradigm shift, but it sure isn't instantaneous. When it's played out in one's actual life, so to speak, it seems glacial. And it's the kind of thing where it's sort of interesting because in the dynamics of sort of the adoption of ideas like that into different fields, the younger the field, the faster the adoption, typically, because people are not kind of locked in. We're the fifth generation of people who've studied this field and it is the way it is and it can never be any different. And I think that's been know watching that process has been interesting. I mean, I think I'm fortunate that I do stuff mainly because I like doing it. And if I was, that makes me kind of thick skinned about the world's response to what I do. But that's definitely, you know, and anytime you write a book called something like A New Kind of Science, it's kind of the pitchforks will come out from for the old kind of science. And it was interesting dynamics. I have to say that I was fully aware of the fact that when you see sort of incipient paradigm shifts in Science, the vigor of the negative response upon early introduction is a fantastic positive indicator of good long term results. So in other words, if people just don't care, that's not such a good sign. If they're like, oh, this is great, that means you didn't really discover anything interesting.

What fascinating properties of Rule 30 have you discovered over the years? You've recently announced the Rule 30 prizes for solving three key problems. Can you maybe talk about interesting properties that have been kind of revealed, Rule 30 or other cellular automata? And what problems are still before us like the three problems you've announced?

Yeah, yeah, right. So I mean the most interesting thing about cellular automata is that it's hard to figure stuff out about them. And that's in a sense, every time you try and sort of, you try and bash them with some other technique, you say can I crack them? The answer is they seem to be uncrackable. They seem to have the feature that they are, that they're sort of showing irreducible computation. You're not able to say, oh, I know exactly what this is going to do, it's going to do this or that.

But there's specific formulations of that fact.

Yes, right. So I mean, for example, in Rule 30, in the pattern you get, just starting from a single black cell, you get this sort of very sort of random looking pattern. And so one feature of that, just look at the center column. And for example, we used that for a long time to generate randomness in Wolven language, just what Rule 30 produces. Now the question is, can you prove how random it is? So for example, one very simple question. Can you prove that it will never repeat? Nope, we haven't been able to show that it will never repeat. We know that if there are two adjacent columns, we know they can't both repeat. But just knowing whether that center column can ever repeat, we still don't even know that. Another problem that I sort of put in my collection of it's like $30,000 for these three prizes for about Rule 30. I would say this is not one of those. This is one of those cases where the money is not the main point, but it just helps motivate somehow the investigation.

So there's three problems you propose to get through $30,000 if you solve all three, or maybe, I don't know.

No, it's 10,000 for each.

For each.

Right. My.

The problems. That's right. Money is not the thing. The problems themselves are just clean formulations.

It's just, you know, will it ever become periodic. Second problem is, are there an equal.

Number of black and white cells down the middle column?

Down the middle column. And the third problem is a little bit harder to state, which is essentially, is there a way of figuring out what the color of a cell at position T down the center column is with a less computational effort than about T steps? So, in other words, is there a way to jump ahead and say, I know what this is going to do, it's just some mathematical function of T.

Or proving that there is no way.

Or proving there is no way? Yes, but both. I mean, for any one of these, one could prove that. That one could discover, we know what Rule 30 does for a billion steps, and maybe we'll know for a trillion steps before too very long. But maybe at a quadrillion steps, it suddenly becomes repetitive. You might say, how could that possibly happen? But so when I was writing up these prizes, I thought, and this is typical of what happens in the computational universe, I thought, let me find an example where it looks like it's just going to be random forever, but actually it becomes repetitive. And I found one. And it's just, you know, I did a search, I searched, I don't know, maybe a million different rules with some criterion. And this is what's sort of interesting about that, is I kind of have this thing that I say in a kind of silly way about the computational universe, which is, you know, the animals are always smarter than you are. That is, there's always some way one of these computational systems is going to figure out how to do something, even though I can't imagine how it's going to do it. And I didn't think I would find one, that you would think, after all these years, that when I found sort of all possible things, funky things, that I would have gotten my intuition wrapped around the idea that these creatures are always in the computational universe, are always smarter than I'm going to be.

Well, they're equivalently as smart, right?

That's correct. And that makes it. That makes one feel very sort of. It's. It's humbling every time, because every time the thing is, is, you know, you think it's going to do this, or it's not going to be possible to do this. And it turns out it finds a way.

Of course, the promising thing is there's a lot of other rules like Rule 30. It's just Rule 30 is always my.

Favorite because I found it first.

That's right. But the problems are focusing on Rule 30. It's possible that Rule 30 is, is repetitive. After a trillion steps, it is possible. And that doesn't prove anything about the other rules.

It does not.

But this is a good sort of experiment of how you go about trying to prove something about a particular rule.

Yes. And it also. All these things help build intuition. That is, if it turned out that this was repetitive after a trillion steps, that's not what I would expect. And so we learned something from that.

The method to do that, though, would reveal something interesting about the cellular stuff.

No doubt. I mean, although it's sometimes challenging, like the. I put out a prize in 2007 for particular Turing machine. That was the simplest candidate for being a universal Turing machine. And the young chap in England named Alex Smith, after a smallish number of months, said, I've got a proof. And he did. It took a little while to iterate, but he had a proof. Unfortunately, the proof is very. It's a lot of micro details. It's not like you look at it and you say, aha, there's a big new principle. The big new principle is the simplest Turing machine that might have been universal, actually is universal. And it's incredibly much simpler than the Turing machines that people already knew were universal before that. And so that intuitionally, is important because it says computational universality is closer at hand than you might have thought, but the actual methods are not in that particular case, but not terribly illuminated.

It would be nice if the methods would also be elegant.

That's true. Yeah. No, I mean, I think it's one of these things where it's like a lot of. We've talked about earlier kind of opening up AIs and machine learning and things of what's going on inside. And is it just step by step, or can you sort of see the bigger picture more abstractly?

It's unfortunate. I mean, with Fermat's last theorem proof, it's unfortunate that the proof to such an elegant theorem is, is not. I mean, it's, it's not. It doesn't fit into the margins of a page.

That's true. But, you know, one of the things is, that's another consequence of computational irreducibility. This, this fact that there are even quite short results in mathematics whose proofs are arbitrarily long. Yes, that's a, that's a consequence of all this stuff. And it's, It'. It makes one wonder, you know, how come mathematics is possible at all?

Right.

Why is, you know, why is it the case how people manage to navigate doing mathematics through looking at things where they're not just thrown into. It's all undecidable. That's. That's its own. Own separate, Separate story.

And that would be. That would. That would have a poetic beauty to it, as if people were to find something interesting about Rule 30. Because, I mean, there's an emphasis to this particular rule. It wouldn't say anything about the broad irreducibility of all computations, but it would nevertheless put a few smiles on people's faces.

Well, yeah, but to me, it's like, in a sense, establishing the principle of computational equivalence. It's a little bit like doing inductive science anywhere. That is, the more examples you find, the more convinced you are that it's generally true. I mean, we don't get to, you know, whenever we do natural science, we say, well, it's true here that this or that happens. Can we prove that it's true everywhere in the universe? No, we can't. So, you know, it's the same thing here. We're exploring the computational universe, we're establishing facts in the computational universe, and that's sort of a way of inductively concluding general things.