- 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 1,200 page book?

- Sure, although it took 1,200 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 argumentation 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. There is a formal theory, there are definite rules, but what structure could those rules have? 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 to, 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 and 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, you know, it's the ratio of the circumference diameter of a circle, very well-defined, but yet when you are, 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 have 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've never seen sort of, I would say, what is it? A one-dimensional, essentially, cellular automata, right? And you were to guess what you would see if you have some sort of cells that only respond to its neighbors. If you were to guess what kind of things you would see, like my initial guess, like even when I first opened your book, A New Kind of Science, right?

My initial guess is you would see, I mean, it would be very simple stuff. And I think it's a magical experience to realize the kind of complexity. You mentioned rule 30, still your favorite cellular automaton? - My favorite rule, yes. - You get complexity, immense complexity. You get arbitrary complexity.

- Yes. - And when you say randomness down the middle column, that's just one cool way to say that there's incredible complexity. And that's 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, I mean, it's transformational about how you see the world. I think for me it was transformational. I don't know, we can have all kinds of discussion 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 'cause you could 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's been, it was a very intuition-breaking thing to discover. I mean, it's kind of like, you know, you point the computational telescope out there and suddenly you see, I don't know, you know, in the past it's kind of like, you know, 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?

- Oh, 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 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 gotta get the, there's gotta be some trace of that simplicity here. Okay, we'll run it, let's say, for 400 steps. It'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. - Your mind immediately starts, is there a pattern? There must be a reparative pattern. - Yeah.

- There must be. That's where the mind goes. - Well, right, so I spent, so indeed, that's what I thought at first. And I thought, well, this is kind of interesting, but if we run it long enough, we'll see, something will resolve into something simple. And I did all kinds of analysis of using mathematics, statistics, cryptography, 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 know, 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, you know, how did people come to figure out this or that thing?

And there's always a long kind of sort of preparatory, you know, there's a need to be prepared and a mindset in which it's possible to see something. I mean, in the case of Rule 30, I was around June 1st, 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 gonna generate a bunch of pictures of the acyllar 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, you know, I really should try to understand this.

And this is really, you know, this is, I really don't understand what's going on. And that was kind of the, you know, slowly trying to see what was happening. It was not, 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 don'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 thing that's strange in this whole question about, you know, finding this different raw material for making models of things.

What's been interesting sort of in the arc of history is, you know, for 300 years, it's kind of like the mathematical equations approach. It was the winner. It was the thing, you know, 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 with 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, you know, watching that process has been interesting. I mean, I think I'm fortunate that I've, I do stuff mainly 'cause 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 any time you write a book called something like "A New Kind of Science," it's kind of the pitchforks will come out for the old kind of science. And it was interesting dynamics. I think that the, 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, it's, you know, 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 some, 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.

They're not, 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, very sort of random looking pattern.

And so one feature of that, just look at the center column. And for example, we use that for a long time to generate randomness in Wolfram 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'll never repeat?

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've sort of put in my collection of, you know, it's like $30,000 for three, you know, for these three prizes for about Rule 30, I would say that this is not one of those, this is one of those cases where the money is not the main point, but it's just, you know, helps motivate somehow the investigation.

- So there's three problems you propose, you get $30,000 if you solve all three, or maybe, I don't know. - No, it's 10,000 for each. - For each, right. The problems, that's right, money's not the thing, the problems themselves are just clean, - Yeah, right. - Formulations of chat box.

- 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 gonna 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, one could discover, we know what rule 30 does for a billion steps, but, 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 gonna be random forever, but actually it becomes repetitive.

And I found one. And it's just, 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, the animals are always smarter than you are.

That is, there's always some way one of these computational systems is gonna figure out how to do something, even though I can't imagine how it's gonna 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 gonna be.

- Well, they're equivalently smart, right? - That's correct. And that makes it, that makes one feel very sort of, it's humbling every time. Because every time the thing is, you know, you think it's gonna do this, so it's not gonna 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-- - Oh, it's my favorite 'cause I found it first. - Yeah, that's right. But the problems are focusing on Rule 30. It's possible that Rule 30 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 learn something from that. - The method to do that, though, would reveal something interesting about the-- - No doubt, no doubt. I mean, although it's sometimes challenging, like I put out a prize in 2007 for a 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, 'cause it says computation universality is closer at hand than you might've thought. But the actual methods are not, in that particular case, were 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, I mean, 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 not, I mean, it doesn't fit into the margins of a page. - That's true.

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

How have people managed to navigate doing mathematics through looking at things where they're not just thrown into, it's all undecidable? That's its own separate story. - And that would be, that would have a poetic beauty to it 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 of, yeah. - Well, yeah, but to me, it's like, in a sense, establishing 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, 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, 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. (upbeat music) (upbeat music) (upbeat music) (upbeat music) (upbeat music) (upbeat music)