Full episode with Stephen Wolfram (Apr 2020): https://www.youtube.com/watch?v=ez773teNFYA
Clips channel (Lex Clips): https://www.youtube.com/lexclips
Main channel (Lex Fridman): https://www.youtube.com/lexfridman
(more links below)

Podcast full episodes playlist:
https://www.youtube.com/playlist?list=PLrAXtmErZgOdP_8GztsuKi9nrraNbKKp4

Podcasts clips playlist:
https://www.youtube.com/playlist?list=PLrAXtmErZgOeciFP3CBCIEElOJeitOr41

Podcast website:
https://lexfridman.com/ai

Podcast on Apple Podcasts (iTunes):
https://apple.co/2lwqZIr

Podcast on Spotify:
https://spoti.fi/2nEwCF8

Podcast RSS:
https://lexfridman.com/category/ai/feed/

Stephen Wolfram is a computer scientist, mathematician, and theoretical physicist who is the founder and CEO of Wolfram Research, a company behind Mathematica, Wolfram Alpha, Wolfram Language, and the new Wolfram Physics project. He is the author of several books including A New Kind of Science, which on a personal note was one of the most influential books in my journey in computer science and artificial intelligence.

Subscribe to this YouTube channel or connect on:
- Twitter: https://twitter.com/lexfridman
- LinkedIn: https://www.linkedin.com/in/lexfridman
- Facebook: https://www.facebook.com/lexfridman
- Instagram: https://www.instagram.com/lexfridman
- Medium: https://medium.com/@lexfridman
- Support on Patreon: https://www.patreon.com/lexfridman

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.

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 argumentation and so on.

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 1 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.

So typical case of a cellular automaton, it's an array of cells.

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 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.

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 1 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 start off from just 1 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, 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 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 to 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.

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, so cells that only respond to neighbors.

If you were to guess what kind of things you would see, like my initial guess, 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?

And when you say randomness down the middle column, that's just 1 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 notions around it too.

It's not just, I mean, it's transformational about how you see the world.

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 1 book and a new kind of science would be it, because you could just enjoy that notion.

For some reason it's a deeply profound notion, at least to me.

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.

Yeah, I mean, I- What are we looking at, by the way?

I'll actually generate a rule 30 pattern.

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.

That's the initial state, initial condition.

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've got to get the...

There's got to be some trace of that simplicity here.

Okay, we'll run it, let's say, for 400 steps.

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?

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 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?

You know, 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.

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?

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 wrote it 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 1, and I put it 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.

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 1 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, in sort of arc of history is, you know, for 300 years, it's kind of like the, the mathematical equations approach.

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 1 can see a transition to using not mathematical equations, but programs as sort of the raw material for making models of stuff.

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.

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, 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 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.

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, 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 3 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 3 problems you've announced?

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.

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.

But there's specific formulations of that fact.

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 1 feature of that, just look at the center column.

And for example, we use that for a long time to generate randomness in Wolfen language.

Now the question is, can you prove how random it is?

So for example, 1 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 2 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, you know, it's like $30,000 for 3, you know, for these 3 prizes for about rule 30.

I would say that this is not 1 of those, this is 1 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 3 problems you propose, you get $30,000 if you solve all 3, or maybe, I don't know.

The problem is, that's right, money's not the thing.

The problems themselves are just clean formulations of childbirth.

It's just, you know, will it ever become periodic?

Second problem is, are there an equal number of

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 in a 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.

But both, I mean, for any 1 of these, 1 could prove that, 1 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.

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 1 of these computational systems is gonna figure out how to do something, even though I can't imagine how it's gonna do it.

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.

And that makes it, that makes 1 feel very sort of, it's humbling every time.

Because every time the thing is, you think it's gonna do this, so it's not gonna be possible to do this.

Of course the promising thing is there's a lot of other rules like rule 30.

Oh it's my favorite, because I found it first.

But the problems are focusing on rule 30.

It's possible that rule 30 is repetitive after a trillion steps.

And that doesn't prove anything about the other rules.

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-type stuff.

I mean, although it's sometimes challenging, like I put out a prize in 2007 for a particular Turing machine that I, 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, you know, 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 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.

Yeah, no, I mean, I think it's 1 of these things where, I mean, it's like a lot of, we've talked about earlier, kind of, you know, 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's not, it doesn't fit into the margins of a page.

That's true, but you know, 1 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.

And it makes 1 wonder, how come mathematics is possible at all.

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.

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.

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, 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?

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.

See all Lex Fridman transcripts on Youtube

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