A New Kind of Science - Stephen Wolfram

[Music] And it is particularly appropriate that for to for this year's lecture for the 2003 H Paul Rockwood Memorial lecture, we are welcoming here today Steph Wolfram, who has, uh, really made an enormous contribution to computer science, to the science of computation, and also through the development of the Mathematica program, to research in many, many areas of science and mathematics.

Now, uh, the other factor that goes into, uh, Steven's background in lecture is the fact that he comes from physics. In fact, he was the youngest physics PhD in the history of Caltech, won the MacArthur Genius Award, and, uh, was the youngest to receive that. He was at the, uh, as professor at Caltech. He moved to the Institute for Advanced Study, where I first met him, and that from there to the University of Illinois, where he started a center for complex systems research, and finally, uh, starting the company Mathematica, which is now based in Urbana-Champaign. He really, uh, set the standards for mathematics programs. So without any further ado, I would like to introduce the president and CEO of Wolfram Research, the the creator of Mathematica, and the author of A New Kind of Science, Steven.

[Applause]

Wolfram: Well, thank you. Thank you very much, Terry. Um, I'm sure many of you have now seen, uh, this big book somewhere. It took me about 10 years to write it, and I'm, I'm very proud of it. And actually, by now, I hope some of you, at least, have had a chance to actually read it.

Well, what I want to do here today is, is to tell you a little bit about what it says. And, um, actually, what I want to do is to tell you about sort of an intellectual structure that I've spent the better part of the past 20 years building. And I think it's a structure that has some pretty exciting implications, both now and fairly far into the future.

Well, back in the late 1970s, I was a young physicist, mostly working on particle physics, but I also did a certain amount of work on cosmology. And from that, I, I got interested in the question of how structures emerge in our universe, from galaxies on down. Looking at that question, I quickly realized that it was actually an instance of a much more general question: sort of, how does anything complicated get produced in nature?

Well, there are lots of everyday examples: snowflakes, turbulent fluid flows, forms of plants and animals, lots of others. My first assumption was that with all the sort of sophisticated math that I knew from particle physics and so on, I'd easily be able to figure out what was going on with these kind of ordinary, everyday systems. When I actually tried to do it, though, it just didn't seem to work. And, and gradually, I started thinking that perhaps there might be a fundamental problem with, with the whole approach that I was using.

Well, if one looks at history, the idea of using math and mathematical equations to understand nature has been sort of a defining feature of the exact sciences for perhaps 300 years. And certainly, it worked out extremely well for, for Newton and friends in figuring out orbits of comets, and for lots and lots of things since then. But when, somehow, when, when the behavior one's looking at is more complicated, it just doesn't seem to work so well. Gradually, what I began to think was that that was actually why there had never really been a good theory for complicated processes in nature, in, in physics, and particularly in biology and so on. And I got to wondering whether there might somehow be a way to go beyond the usual paradigm of thinking about mathematical equations in, in, in thinking about nature.

Well, that was around 1981, and it so happened that at that time, I had just spent time developing a big software system called SMP, that was in some ways a forerunner of Mathematica. And at the core of SMP was a computer language. And what I'd done to design that language was somehow to try to think about all the computations that people might want to do, and then to try to identify primitives that could be strung together to build up those computations.

Well, that had worked out fairly well, and in fact, in a, in a much evolved form, I think it's now worked out spectacularly well in Mathematica. But anyway, back in 1981, I had the idea that perhaps, just as I'd been able to find primitives for computations people want to do, I might somehow also be able to find primitives for what nature does. And the crucial thing that I realized is that those primitives don't have to be based only on traditional mathematical constructs. I mean, if one's going to be able to do theoretical science, one has to assume that nature follows some kind of definite rules. But why do those rules involve only the kinds of constructs that have been invented in human mathematics, things like numbers and exponentials, calculus and so on? Can't the rules somehow be more general?

Well, in the past, there wouldn't really have been any systematic way to think about such things. But now we have computers, whose programs in effect implement arbitrarily general rules. And the idea I have was that perhaps the kinds of rules that can be embodied in programs might actually be what nature is using.

So what sorts of programs might be relevant? Well, from knowing about mathematical things, I'd assume they have to be at least somewhat complicated. But still, I figured I should at least start by looking at really simple programs. So in practical computing, we used to fairly long and complicated programs that are specifically set up for particular tasks. But what I wanted to know about were really simple, short programs, say, one's just chosen at random. So what, what do programs like that do? It's sort of the simplest possible computer experiment: you run the simplest programs and see how they behave.

Well, back in 1981, I, I came up with particular kinds of programs to try that are known as cellular automata. So here's how a simple cellular automaton works: one starts off with a row of cells, each either black or white. Then the cellular automaton evolves down the page, with the color of each cell on each step being determined by a definite rule from the color of the cell and its neighbors on the step before.

Well, in this particular case, the rule is really simple. It just says that a cell will be black whenever it or its neighbors were black on the, on the row before. And what happens is just that we get a simple, uniform black pattern. Well, we can use that icon at the bottom there to represent the rule, the program that we're using. So what happens if we change the rule a bit? Well, now, instead of getting just a uniform black pattern, we get a checkerboard. So far, none of this is terribly surprising. We're using very simple rules, we're getting simple patterns out.

Okay, let's try another rule. It's the same setup as before, but what's going on here? We, we don't seem to be getting any kind of simple repeating pattern. Let's run it a bit longer. It gets pretty intricate. We can see, though, that it's very regular. It's, it's, it's just a self-similar or fractal pattern, just formed from identical nested pieces.

Well, one might think that if one has a simple rule, and one starts from just a single black cell, then one would always have to get a pattern that somehow very regular like this. At least back in 1982, that's what I assumed was true. But one day, I decided to try a very systematic experiment and just run every single one of the 256 possible simplest cellular automata rules. So when I got to rule number 30, this is what I saw.

So what's going on here? Well, let's run it some more. Well, there's a bit of regularity over there on the left, but otherwise, this looks really complicated. Actually, kind of random. Well, when I first saw this, I thought it might just be a problem with our visual system, that that really there were regularities, but we just couldn't see them. So I ran all sorts of elaborate mathematical and statistical tests, and what I found was that, no, so far as I could tell, something like the center column of cells here really was perfectly random.

Well, this is rather amazing. We have a very simple rule, we're starting off from a single black cell, but what we're getting out is an incredibly complicated pattern. Seems in many ways random. So it just doesn't seem right. We put so little in, yet we're getting so much out. It's, it's not what our ordinary intuition says should happen. I mean, in our everyday experience, and say, in doing engineering, what we're used to is that to make something complicated, we somehow have to start off with complicated plans or use complicated rules. But what we're seeing here is that actually, even extremely simple rules can produce incredibly complicated behavior.

Well, it took me years to come to terms with this phenomenon, and in fact, it's gradually overturned almost everything I, I thought I knew about the foundations of science. And it's what's led me to spend the past 15 years building a new intellectual structure, really, a, a new kind of science.

Well, okay, so, so having seen rule 30, what more can happen? Here's another one of the 256 simplest cellular automata. This is rule 110. So this one grows only on the left. What's it doing? So let's run it a little bit longer. It's not making any kind of uniform randomness. Instead, we can see little complicated structures running around. We can ask, what, what's going to happen? Well, the only way to find out seems to be to just keep running the system. Are we going to get more of the little structures, or are they all going to die out? What's going to happen? Well, after 2,780 steps, we finally get the answer. At least in this case, we basically end up with just one structure. But it, it's kind of amazing. Everything we get just starting from one little black cell and then following a really simple rule.

Well, in the mid-1980s, I'd studied a bunch of cellular automata and I'd seen these basic phenomena, but I wasn't sure whether they were somehow specific to cellular automata or more general. And I had the practical problem that there wasn't any easy way to set up all the very different types of computer experiments that I'd have to do to find that out. In fact, that was one of the main reasons that I started building Mathematica. I wanted, once and for all, to make a system that I could use to do all the computations and all the computer experiments I'd ever want.

Well, for 5 years, the, the task of building Mathematica and our company pretty much consumed me. But finally, in 1991, I decided I could start looking at my questions in science again. Actually, it was, it was really incredible. Things that had taken me days to do before now took minutes. It was easy to do all the experiments I wanted. I mean, I, I guess it was a little how it must have felt when telescopes or microscopes were first invented. One could just sort of point them somewhere and almost immediately see a whole world of, of new phenomena, like little microscopic creatures swimming around in pond water and so on.

Well, in the computational world, one just pointed Mathematica somewhere and suddenly one could see all this amazing stuff. So the first question was just, how special are cellular automata? Well, I looked at lots of cellular automata and often saw very complicated behavior. What about programs with, with different setups, though? Like, here's a Turing machine, for example. It's got a row of cells like a cellular automaton, but unlike a cellular automaton, only one cell gets updated at each step, but that cell moves around. Well, the first quite a few Turing machines only do these kinds of things, but if one keeps going, still with very simple rules, then suddenly one sees this, the same kind of complexity that we saw in cellular automata.

So what about other kinds of programs? Well, I looked at many, many different kinds: sequential substitution systems that rewrite strings like an iterated text editor; register machines, kind of like idealized minimal idealizations of machine language; also symbolic systems, like generalizations of combinators or kind of minimal idealizations of Mathematica. It's the same story in two dimensions, in, in cellular automata or in Turing machines, or for that matter, in three dimensions. Every time, one sees the same thing: even with very simple rules, one can get extremely complicated behavior. One doesn't even need rules that specify an explicit process of evolution. Constraints work too, like, like here's the simplest set of tiling constraints that force a non-periodic pattern, and here are constraints that give a kind of, uh, crystal that's forced to have a rule 30 pattern.

Well, wherever one looks, it's always the same basic thing: incredibly simple rules can give incredibly complicated behavior. It seems to be a very robust and very general phenomenon. But so, how come something that fundamental hadn't been known for ages? Well, partly it's because one can only easily see it by doing lots of computer experiments, and it's only with computers, and particularly with Mathematica, that those have become easy to do. But more important is that with our ordinary intuition, there just didn't seem to be any reason to try the experiments. It seemed so obvious they wouldn't show anything interesting.

Well, now that one's made the clear discovery that simple programs, simple rules can produce complicated behavior, one can go back and find all sorts of hints about it from really long ago. I mean, nearly 25, 200 years ago, for example, the Greeks looked at prime numbers, and there's a fairly simple rule, a fairly simple program for generating all the primes, but the sequence of primes, once generated, looks remarkably irregular and complicated. There's also a fairly simple rule for generating the digits of pi, but once generated, that sequence looks to us completely random. And actually, there are lots of cases of this kind of thing with numbers. I mean, here's what happens if you write out successive powers of three in base 2, kind of a, a minimal version of a linear congruential random number generator, and already amazingly complicated.

Well, you can also make very complicated sequences from simple integer occurrences. And here, for example, is the simplest primitive recursive function that has complex behavior.

Well, what about other systems based on numbers? What about, for example, those favorite things from traditional mathematical science, partial differential equations? Does their continuous character make them work differently? Well, the ones people usually study show only rather simple behavior. But doing an automated search through the space of possible symbolic equations, I ended up finding these creatures. They're just simple nonlinear PDEs, but even with very simple initial conditions, they end up doing all sorts of complicated things. Actually, it's a little hard to tell exactly what they do. I mean, we, we use these PDEs to test our ever-improving state-of-the-art PDE solving capabilities in, in Mathematica. But with continuous systems, there's always a problem because you end up having to discretize them. And without already more or less knowing the answer, it's hard to tell whether what you're seeing is something real. That's probably why, among mathematicians, numerical experiments can sometimes have kind of a bad name. But in a discrete system like rule 30, there are no issues like that. The bits are the bits, and one can see that one's, one can tell that one's seeing a real phenomenon. Actually, I think rule 30 is so simple to set up, there's really no reason the Babylonians couldn't have done it. And, and I sometimes wonder whether, a bit like these, some ancient mosaic of rule 30 might one day be unearthed. But I rather think that if rule 30 had actually been known in antiquity, a lot of ideas about science and nature would have developed somewhat differently. Because as it is, it's always seemed like a big mystery how nature could manage, apparently so effortlessly, to produce so much that seems to us so complex. I mean, it's like nature has some special secret that allows it to make things that are much more complex than we as humans normally build. And often, it's seemed like that must be evidence that there's something somehow beyond human intelligence involved. But once one sees in rule 30, it suggests a very different explanation. It suggests that all it takes is for things in nature to follow the rules of typical simple programs, and then it's almost inevitable that, like in the case of rule 30, their behavior can be highly complex. I mean, the way we as humans are used to doing engineering and to building things, we tend to operate under the constraint that we have to foresee what the things we're building are going to do. And that means that we've ended up being forced to use only a very special set of programs that always happen to have simple, foreseeable behavior. But the point is that nature is presumably under no such constraint. So that means that there's nothing wrong with it using something like rule 30 and that way inevitably producing all sorts of complexity.

Well, once one starts thinking in terms of simple programs, it's kind of amazing how easily one can start to understand the essential features of what's going on in all sorts of systems in nature. So let's, uh, talk about a simple example: snowflakes. Crystals start by growing, start grow by starting from a seed, and then successively adding pieces of solid. And one can try to capture that with a simple two-dimensional cellular automaton. I mean, imagine a grid where every cell either has solid in it or not. Then start from a seed and have a rule that says solid will be added at any cell that's adjacent to one that's already solid. So here's what one gets. It's, it's an ordinary-looking faceted crystal here on, on a square grid.

Well, one can do the same kind of thing on a hexagonal grid. But for snowflakes, there's obviously an important effect missing here. And what that is, is that when a piece of ice solidifies from water vapor, there's some latent heat released, and that inhibits more ice from solidifying nearby. Well, what's the simplest way to capture that effect? One can just change the cellular automaton to say that ice gets added only if the number of neighboring cells that are already ice is exactly one. Okay, so what happens then? Well, here's the answer, and these are all the stages that one sees. And these look an awful lot like real snowflakes. It really seems like we've captured the basic mechanism that makes snowflakes have the shapes they do. And we get various predictions, like the big snowflakes will have little holes in them from where arms collided and so on, which indeed they do.

Okay, but even though the pictures we've got look a lot like real snowflakes, there are obviously details that are different. One thing one has to understand, though, is that that's always going to happen with a model, because the whole point of a model is to capture certain essential features of a system and to idealize away everything else. And depending on what one's interested in, one may pick different features to, to, to capture. So the cellular automaton model is good, for example, if one's interested in the basic question of why snowflakes have complicated shapes, or what the distribution of shapes in some snowflake population will be. But it's not so useful if one's trying to answer a question like, specifically, how fast each arm will grow at a certain temperature.

I might say that there's actually a general confusion about models that often seems to surface when people first hear about cellular automata. They'll say, "Okay, it's very nice that cellular automata can reproduce what snowflakes do, but of course, real snowflakes aren't actually made from cellular automata cells." Well, the whole point of a model is that it's supposed to be an abstract way of reproducing what a system does. It's not supposed to be the system itself. I mean, when we have differential equations that describe how the Earth moves around the sun, we don't imagine that inside the Earth there are all sorts of little mathematicians solving differential equations. Instead, it's just that the differential equations represent abstractly the way the Earth moves. And it's, it's exactly the same thing with, with models based on cellular automata. I mean, the cells and rules abstractly represent certain features of a system. And again, what abstract representation, what type of model is best depends on what one's interested in. In the case of snowflakes, there are certainly traditional differential equations that could be used, but they're complicated and hard to solve. And if what one's actually interested in is the basic question of why snowflakes have complicated shapes, the cellular automaton model is, is a much better way to get at that.

Okay, let's take another example. Let's talk about fluid turbulence. So whenever there's an obstacle in a fast-moving fluid, the pattern of flow around it looks complicated and, and quite random. But where does that randomness come from? Well, one can ask the same question about randomness in any system. And I think there are really three basic ways that randomness can arise. The one that's traditionally most talked about is that the randomness can come from external perturbations from the environment. I mean, an example is a, a boat bobbing on an ocean. The boat itself doesn't produce randomness; it just moves randomly because it's exposed to all the randomness of the ocean. It's the same kind of thing in Brownian motion, where the randomness comes from lots of microscopic molecules randomly bouncing around, or an electronic noise, where one's listening to much amplified random thermal motion.

Well, in the last 20 years or so, another way to get randomness that's often been talked about is the one from chaos theory. And the idea there is not to have randomness continually injected into a system, but instead to have it fed in only at the beginning from the details of the initial conditions for the system. So think about tossing a coin or spinning a wheel. Once it's started, there's no randomness in how it moves, but which way it'll be pointed when it stops depends sensitively on what its initial speed was. And if it was started, say, by hand, there'll always be a little randomness in that, so one won't be able to predict the outcome.

Well, there are more elaborate versions of this where one's effectively taking numbers that represent the initial conditions for a system and successively excavating higher and higher order digits in them. And from the perspective of ordinary continuous mathematics, there's some trickiness in accounting for where the randomness comes from. There. Looked at in terms of programs, though, it's very clear that the randomness one gets out is just randomness that one put in in the detailed pattern of digits in the initial conditions. So again, this ends up being an explanation that says, essentially, randomness comes from outside the system that one's looking at.

Okay, well, so is there any other possibility? Well, it turns out that there is. Just look at rule 30 here. One doesn't have any randomness initially. One, one just has a single black cell, and one doesn't have any subsequent input from the outside. But what happens is that the evolution of the system just intrinsically generates apparent randomness.

Okay, so, so what about fluid turbulence? Where does randomness come from there? Well, with the traditional differential equation way of modeling fluids, it's very difficult to find out. But one can make a simple cellular automaton model where it's much easier. Well, so remember that at the lowest level, a fluid just consists of a bunch of molecules bouncing around. And actually, we know that the details aren't too important, because air and water and all sorts of other fluids that have completely different microscopic structures still show the same continuum fluid behavior. So knowing that, we can try to just make a minimal model for the underlying molecules, just have them, for example, on a discrete grid with discrete velocities and so on.

Well, if one does that, one both gets a rather nice practical way to do fluid dynamics, and one can start addressing some fundamental questions. And what one seems to find is that there's no need for, for randomness from the environment or randomness from initial conditions. One can get randomness from intrinsic randomness generation from something like rule 30.

Well, okay, so what if one's trying to make models of fluid turbulence? It's kind of important to know where the randomness in it comes from. An intrinsic randomness generation makes at least one immediate prediction: it says that in a carefully enough controlled experiment, the turbulence should be exactly repeatable. So if the randomness comes from the environment or from details of initial conditions, it'll inevitably be different in different runs of the experiment. But if it's like rule 30, then it'll always be the same every time one runs the experiment.

Well, one can ask about randomness in all sorts of systems, like in finance, for example, where the most obvious feature of almost any market is that the prices in it seem to fluctuate quite randomly. So where does that randomness come from? Some of it is surely from the environment, but some of it is probably intrinsically generated. And knowing that is important if you want, for example, to know if you can predict it.

Well, back in physics, one place randomness has been discussed a lot is the second law of thermodynamics, that the law of entropy increase. A lot is known about it, but there's still sort of a basic mystery about how the laws of physics can be reversible, yet in our everyday experience, we see so much apparent irreversibility. And I think that intrinsic randomness generation finally gives one a way to explain that. It's a slightly long story, but it's basically that things like rule 30 can so encrypt the data associated with initial conditions that no realistic experiments or observations can ever decode it and see how to go backwards.

Well, okay, that's a little about physics. What about biology? Well, there's certainly a lot of complexity in biology, and, and people often assume that it's kind of of a higher level than in physics. And usually they figure that's somehow because of adaptation and natural selection. But in reality, it's never been clear why natural selection should actually lead to much complexity at all. And that's probably why, at least outside of science, many people have thought there must be something else going on. The question is, what is it?

Well, I think that actually, it's just the abstract fact that we discovered with rule 30 and so on, that among simple programs, it's actually very easy to get complexity. I mean, of course, the complete genetic program for a typical organism is pretty long and complicated. For us humans, it happens to be about the same length, for example, as the source code for Mathematica. But it's increasingly clear that lots of the most obvious aspects of forms and patterns in biology are actually governed by rather small programs. And looking at, for example, these kinds of regularities that, that one sees in biological systems, that doesn't seem too surprising. When one sees more complicated stuff, though, traditional intuition tends to suggest that somehow it must have been difficult to get. And that, um, for example, with the natural selection picture, there's sort of the idea that it must be be the result of a long and difficult process of optimization or of trying to fit into some complicated ecological niche.

Well, I actually think that that's not where many of the most obvious examples of complexity in biology come from. I mean, natural selection seems to be quite good at operating on small numbers of smooth parameters, you know, lengthening one bone, shortening another, and so on. When there's more complexity involved, though, it's very hard for natural selection to operate well. And instead, what I think one ends up seeing is much more just the outcome of typical randomly chosen genetic programs.

So let me give you an example. Here are some mollusk shells with pretty complicated pigmentation patterns on them. Well, in the past, one might have assumed that to get things as complicated as this must be difficult, and that somehow it must be the result of a sophisticated biological optimization process. But if you look at these patterns, they look incredibly similar to patterns we get from cellular automata, like rule 30.

Well, in the actual shell, the pattern is laid down by a line of pigment-producing cells on, on the growing edge of the shell. And it seems that what happens can be captured rather well by cellular automaton rule. So why one rule and not another? Well, if one looks at different species, one sees all sorts of different patterns. But the neat thing is that there are definite classes of patterns that one sees that correspond remarkably well with the classes of behavior that one sees in cellular automata. So it's sort of as if the mollusks of the world are just sampling the space of possible simple programs, and we just get to see the results of those programs displayed on their shells.

Well, with sort of all the emphasis on natural selection, one's kind of gotten used to the idea that there can't be much of a fundamental theory in biology, and that the things one sees in current organisms must just reflect detailed accidents in the history of biological evolution. But what the mollusk shell example suggests is that things might actually be different, and that instead, it might be reasonable to think of different types of organisms as somehow uniformly sampling a whole space of possible programs.

So let me give one more example: shapes of leaves. One might think that these are too diverse to explain in any uniform way. But actually, it turns out that there's a simple type of program that seems to capture almost all of them. It just involves successive repeated branchings. And what's remarkable here is that the limiting shapes one gets look just like actual leaves, sometimes smooth, sometimes jagged, and so on.

Well, here's a simple case where one can actually lay out all of the possible shapes that one gets. And one thing one can see is that varying a parameter can change not only quantitatively, but also qualitatively, what kind of leaf one gets, and therefore also potentially change how it can function biologically. Well, to be a little more sophisticated, one can kind of summarize features of possible leaves in a parameter space set that turns out to be a rather interesting, simpler linear analog of the Mandelbrot set. And from the properties of this set, one can deduce all sorts of features of leaves and their likely evolution.

Well, okay, there's a lot to say about how one can use ideas about simple programs to capture what's going on in biology, both at the macroscopic levels of the kind I've been talking about and at molecular levels. Let me, let me now turn for a few minutes back to physics, and in particular, fundamental physics, for which we don't immediately need a picture.

Well, traditional mathematical approaches have obviously had lots of success there, but still, they haven't been able to give us a truly fundamental theory of physics. And I suspect that the reason for that is that one really needs more primitives, not just the ones from traditional mathematics, but also the more general ones that one can have in programs. And now that we've seen that very simple programs can produce immensely rich and complex behavior, one can't help wondering whether perhaps all of the amazing things that we see in our universe couldn't just be the result of some particular simple program.

Well, that would be pretty exciting to have a little program that's a precise ultimate model of our universe, so that if one just runs that program long enough, it'll reproduce every single thing that happens in our universe. But, okay, what might such a program be like? Well, one thing that's kind of inevitable is that very few familiar features of our universe will immediately be visible in the program. I mean, there just isn't room. I mean, if the program is small, there's no way to fit in separate identifiable pieces that represent electrons or gravity or even space or time. And in fact, I think that if the program is going to be really small, it sort of has to have the very least possible structure already built in. And for example, I think a cellular automaton already has far too much structure built in. For example, it's got a whole rigid array of cells laid out in space, and it also separates the notion of space from the notion of states of cells. And I don't think one even needs that. I mean, in ordinary physics, space is a kind of background on top of which matter and everything else exists. But I think that in an ultimate model, one needs only space. I don't think one needs any other basic concepts.

Well, okay, so given that, what might space be? I mean, we normally think of space as just being something that is, not something that has any kind of underlying structure. But I think it's actually a little like what happens with fluids. I mean, our everyday experience is that something like water is a continuous fluid, but we actually know that underneath it's made up of lots of lots of little discrete molecules. And I think that something similar is happening with space, and that at a small enough scale, space is just a huge collection of discrete points. And actually, I think it's really a giant network with a, with a changing pattern of connections between points, where where all that's specified is how each point, each node, is connected to others.

Well, in the end, there'll probably be lots of ways to formulate it, but a simple one is just to say that each point is connected to exactly three other points, making a trivalent network. Well, okay, so, so how can anything like space as we know it come from this? Actually, it's quite easy. And in fact, one can have networks that correspond to space in any number of dimensions. I mean, here are some examples. This is, this is one dimension, two dimensions, three dimensions. What's important here is that all these are just trivalent networks. The only thing that's different is the pattern of connections between the nodes.

Well, I've drawn these to make the correspondence with ordinary space clear, but it's important to realize that there's absolutely no intrinsic information in the actual network about how it should be drawn. It's just a bunch of nodes with a certain pattern of connections.

Well, okay, given a pattern of connections, how do we tell whether it corresponds to one-dimensional, two-dimensional, three-dimensional, or whatever space? It's actually quite easy. Think, think about starting at a particular node, then go to all nodes that take one connection to reach, then two, then three, and so on. Well, what one's doing here is to form some kind of circle or sphere or something. And then the thing to do is just to ask how many nodes there are inside that after one's gone, say, our connection. Well, in two dimensions, it'll be roughly the area of a circle, pi r squared. In three dimensions, the volume of a sphere, 4/3 pi r cubed, and so on. And in general, in D dimensions, it'll be something that grows like r to the D. So given a network, that's how one can tell how many dimensions one's in.

Okay, well, so that's a little bit about space. So what about time? In the usual mathematical formulation of physics, space and time are always very much the same kind of thing. I mean, just different variables corresponding to different dimensions. But when one looks at programs, they seem much more different. I mean, in a, in a cellular automaton, for example, one moves in space by going from one cell to another, but one moves in time by actually applying the cellular automaton rule.

Okay, so, so can space and time really be that different? It's all rather tricky, but I think that at the lowest level, they are. I mean, it's definitely not like in a cellular automaton, though, because in a cellular automaton, there's some kind of global clock, with each cell getting updated in parallel at every tick. Well, it's hard to imagine how such a global clock could exist in our universe.

Okay, so, so what might actually be going on? Well, here's something that at first seems crazy. I mean, how about if the universe works like a Turing machine, or what I call a mobile automaton, where at each step, there's only one cell that's getting updated? So there, there's no problem with synchronization here, because there's only one place where nothing happens at a time. But so, so how can this possibly be right? I mean, after all, we normally have the impression that everything in the universe is going through time together. I mean, I certainly don't have the impression that what's happening, for example, is that first I'm getting updated, then you're getting updated, and so on. But the point is, how would I know? Because until I'm updated, I can't tell whether you've been updated or not.

Well, okay, so if one follows this all the way through, one realizes that all we can actually know about in the end is a kind of causal network of what event influences what other event. And here's an example of how one can go from an underlying sequence of updates, in this case in a mobile automaton, to a causal network. And the important thing here is that even though the updates only affect one cell at a time, the final causal network corresponds to something kind of uniform in spacetime.

Okay, so, so how might time work in the, in the context of the space networks that I talked about before? Well, the obvious thing is to imagine that there's an updating rule that says that whenever there's a piece of network that has a particular form, it should get replaced by a piece of network with another form. So here are examples of rules like that. There's an immediate problem, though. I mean, if there are several places in the network where a particular rule could apply, where should one update first? In general, different updating orders will lead to different causal networks, and one will get a sort of whole tree of possible histories for the universe. And then to say what actually happens in our universe, one will somehow have to, to have more information to say what branch one's on.

Well, I don't consider that very plausible. And it turns out that there's actually another rather subtle possibility. It turns out that with the appropriate kinds of underlying rules, it actually doesn't matter what order they get applied in. There's what I call causal invariance. That means that the causal network one gets out is always the same. Well, for those of you who know about such things, this is related to the so-called confluence or Church-Rosser properties in rewrite systems. It's also related to the way that Mathematica manages to find canonical forms for expressions. But anyway, there are conditions about avoiding overlaps and so on, which turn out, for example, to allow rules based on graphs like these. And whenever one uses just these graphs, for example, one has causal invariance. And that means that in a sense, there's always just a single thread of time in the universe.

Well, okay, in addition to making there be a single thread of time, this setup has another important consequence. It turns out to immediately imply that special relativity must hold. So it's a slightly complicated story. For those of you who know about such things, let me just say that different updating orders correspond to different space-like hypersurfaces, and that's why, subject to various tricky issues of limits and averages and so on, causal invariance implies relativistic invariance.

Well, okay, let's go on. What, what about general relativity, the standard theory for gravity? One needs to start off by talking about curvature in space. Here's an example of a network that corresponds to flat two-dimensional space. What happens, though, if we change the connections, so we mix some heptagons or some pentagons into those hexagons? The answer is that we get a space that bulges out or bulges in.

Well, remember that in 2D, the number of nodes we get by going out a distance r is supposed to grow like r squared. Well, in ordinary flat space, it's exactly r squared. But in curved space, there's a correction term, and it turns out that that's proportional to the so-called Ricci scalar curvature. Well, that's already kind of interesting, because the Ricci scalar of curvature is exactly a thing that appears in the Einstein equations that specify the structure of spacetime in general relativity. The whole story is quite complicated. We actually need to look at curvature not just in space, but in spacetime defined by causal networks. But it then turns out that the growth rates of volumes of space-time cones are related to the so-called Ricci tensor. And then with certain microscopic randomness and other conditions, it looks like one can derive conditions on the Ricci tensor, and guess what? They seem to be exactly the Einstein equations.

Well, so there are many issues and caveats, but it's rather exciting. It seems like from almost nothing, one's been able to derive a major feature of our universe, namely general relativity and gravity.

Okay, so another major thing in our universe is particles like electrons and photons and so on. Well, remember that all we have in the universe is space. So how can we get particles? Well, here's how it can work in something like a cellular automaton. Here's a particular cellular automaton. It happens to be our friend rule 110. We start off at the top from random initial colors of cells, but what we see is that the system quickly organizes itself into a few persistent localized structures. And these localized structures act just like particles. So, for example, here's a collision between them. Two particles come in, then after a certain amount of interaction, a, a whole bunch of particles come out. It almost looks like an explicit version of a Feynman diagram in particle physics.

Well, okay, so how does something like this work in a network? What, what happens is that the particles end up being based on on definite little tangles, like kind of non-planar pieces in otherwise planar graphs.

Well, okay, so talking about particles brings up quantum mechanics. Quantum mechanics is really a big bundle of mathematical results and constructs. It's certainly not easy to see how to derive it all from the underlying theory I've been talking about. And actually, just to make things even, even more complicated, my guess is that it'll in the end be easier to derive quantum field theory than quantum mechanics, just like it's easier to go from molecular dynamics to fluid mechanics than to rigid body mechanics. But still, we can see a few things quite easily. The way quantum mechanics is usually set up, it has a kind of fundamental randomness built in. My theory is completely deterministic, but the point is that it makes its own randomness. And actually, that randomness is crucial, not only in giving quantum mechanics, but even in building up things like space and time.

Well, one might think that with the underlying determinism in my theory, there couldn't be the kinds of correlations that one needs to violate Bell's inequalities to get what's observed in quantum mechanics. But it turns out that that conclusion relies on some basic assumptions about spacetime. And with my network setup, it's actually quite easy to, at least imagine, getting the correlations that one wants. Roughly, it can happen just by there being a few kind of long-distance network connections between particles that just aren't part of the usual 3+1 dimensional spacetime structure.

In fact, it's, it's quite amazing how many known features of physics one seems to be able to get rather easily from the kind of simple programs I've been talking about. And, and I must say that it makes me increasingly hopeful that it'll really be possible to find a single simple program that really is the ultimate program for the universe. I mean, there are lots of technical difficulties, lots of tools that have to be built. In fact, you can, you can watch for those in, in future versions of Mathematica. But I, I think in the end, it's going to work, and it's going to be pretty exciting.

Well, okay, I, I wanted to come back now to the original discovery that really launched everything I've been talking about: the discovery that even simple programs like rule 30 can produce immensely complex behavior. So why does that happen? What's the fundamental reason? Well, to answer that, one needs to set up a somewhat new conceptual framework. And the basis of that is to think about all processes as computations. The initial conditions for a system are the input, and the behavior that's generated is the output.

Well, sometimes the computations are ones that we kind of immediately know the point of. Like, here's a cellular automaton that computes the square of any number. You give it a block of n cells at the top, and it generates a block of n squared cells at the bottom. And here's a cellular automaton that generates the primes. But actually, any cellular automaton can be thought of as doing a computation. It just isn't necessarily a computation that we kind of know the point of beforehand.

Okay, so we have all sorts of systems, and they do all sorts of computations. But how do all these computations compare? Well, we might have thought that every different system would always do a completely different kind of computation. So that, for example, if I wanted to do addition, one would buy an adding machine. If I wanted to do exponentiation, one would buy an exponentiation machine. But the remarkable idea that's now about 70 years old is that no, that's not necessary. Instead, it's possible to make a universal machine that can do any computation, if it's just fed the right input. Of course, that's been a pretty important idea because it's the idea that makes software possible, and really, it's the idea that launched

The whole computer revolution, strangely enough, though it's not an idea that's in the past, had much effect on the foundations of natural science. But one of the things that comes out of what I've done is that it actually has some very important implications there too.

Okay, so let's talk about what it means to be a universal system. Basic, basically, it's that with appropriate input, the system can be programmed to act like any other system. So here's an example of that: a universal cellular automaton. And the idea here is that by changing initial conditions, this single cellular automaton can be made to act like any other cellular automaton.

Okay, so here it's behaving like rule 254, which happens to make a simple uniform pattern. Here it's behaving like rule 90. Here it's behaving like rule 30. And remember, each of these pictures is of the same universal cellular automaton with the same underlying rules. But what's happening is that by giving different initial conditions, we're effectively programming the universal cellular automaton to emulate all sorts of other cellular automata. And in fact, it's able to emulate absolutely any other cellular automaton with rules of any size.

Now, one might have thought that a system would only be able to emulate systems that were somehow simpler than itself. But the existence of universality says that we can have a fixed system that can emulate any other system, however complicated that may be. So, in a sense, once one's got to a system that's universal, one's maxed out from a computational point of view. One's got a system that can do essentially any computation, however sophisticated.

Okay, so what about all these various cellular automata, like rule 30, or all the systems that we see in nature? How sophisticated are the computations that they're doing? Well, I spent a long time thinking about this and accumulating all sorts of evidence. And what I ended up concluding is something that at first seems pretty surprising. I call it the principle of computational equivalence. It's a very general principle. And in its roughest form, what it says is this: that essentially, anytime the behavior of a system looks to us complex, it will end up corresponding to a computation of exactly equivalent sophistication.

So, if we see behavior that's repetitive or nested, then it's pretty obvious that it corresponds to a simple computation. But what the principle of computational equivalence says is that when we don't see those kinds of regularities, we're almost always seeing a process that's, in a sense, maximally computationally sophisticated.

Now, at first, that's pretty surprising, because we might have thought that the sophistication of the computations that get done would depend on the sophistication of the rules that got put in. But the principle of computational equivalence says it doesn't. And that immediately gives us a prediction. It says that even though their rules are extremely simple, systems like rule 30 should be computationally universal.

Well, normally we'd imagine that to achieve something as sophisticated as computational universality, we'd somehow need sophisticated underlying rules. And certainly, the computers that we use, that are universal, have CPU chips with millions of gates and so on. But the principle of computational equivalence says you don't need all of that. It says that even cellular automata with very simple rules should be universal.

Well, here's one of them. This is rule 110. I, I showed it earlier. It's got a fairly simple rule, but as you can see, it does some fairly complicated things. It's got all those little structures running around that seem like they might be doing logic operations or something. But, you know, one can assemble them to get something one can see as universal.

Well, one day, I think it's going to be possible to automate most of the process of figuring that out. Unfortunately, I did not have that automation. So I, I had to get a human assistant of mine to do it instead. But after a lot of painstaking work, one gets the result that rule 110 is indeed universal. Well, that's just what the principle of computational equivalence said should be true. But it's really a remarkable thing, because it means that this little rule can, in effect, produce behavior that's as complex as any system. One doesn't need anything like a whole computer CPU to do universal computation. One just needs this little rule.

And that has some very important consequences when it comes to thinking about nature, because we wouldn't expect to find whole computer CPUs just lying around in nature. But we definitely can expect to find things with rules like 110. And that means, for example, that lots of everyday systems in nature are likely to be universal.

By the way, in the past, this was the simplest Turing machine that was known to be universal. But now one can see that this much simpler Turing machine is actually universal. And in fact, I suspect that one can go even further, and that actually this Turing machine will end up being the very simplest possible one that's universal.

Well, there's a lot to say about what the principle of computational equivalence is and what it means. One thing it does is to make Church's thesis definite by saying that there really is a hard upper limit on the computations that can be done in our universe. But the place where the principle really starts to get teeth is when it says that not only is there an upper limit, but that upper limit is actually reached most of the time with incredibly simple rules.

One will often get just simple behavior, that's say, repetitive or nested. But the point is that if one makes the rules even a tiny bit more complicated, then the principle of computational equivalence says that one immediately crosses a threshold and ends up with a system that's maximally computationally sophisticated.

But actually, the principle goes even further than that. Normally, when one talks about universal computation, one imagines being able to set up whatever initial conditions one wants. But the principle of computational equivalence says that that's not necessary, because it says that even when the initial conditions are simple, they'll still usually be maximally sophisticated computation going on.

Okay, so, so what does all this mean? Well, the first thing, it first of all, it gives us a way to answer the original question of how something like rule 30 manages to show behavior that seems so complex. The main point is that there's always a competition between an observer and a system they're observing. And if the observer is somehow computationally more sophisticated than the system, then they can, in a sense, decode what the system is doing, so it'll look simple to them. But what the principle of computational equivalence says is that in most cases, the observer will be exactly computationally equivalent to the system they're observing. And that's why the behavior of the system will inevitably seem to them complex.

Well, a related consequence of the principle of computational equivalence is a very important phenomenon that I call computational irreducibility. Let's say, you know the rules and the initial conditions for a system. Well, then you can certainly work out what the system will do by explicitly running it. But the question is, whether you can somehow shortcut that process? Can you, for example, just work out a formula for what will happen in the system without ever explicitly having to trace each step? If you can, then what it means is that you can figure out what the system will do with a lot less computational effort than it takes the system itself. And that kind of computational reducibility is at the core of most traditional theoretical science. I mean, if you want to work out where an idealized Earth will be a million years from now, you don't have to trace all its million orbits. You just have to plug a number into a formula and get a result.

But the problem is, what happens if the behavior is more complex? If a system is repetitive or even nested, it's easy to shortcut things. What about a case like this? There's certainly no obvious way to shortcut this. And in fact, I think it's computationally irreducible. There's essentially no way to work out what the system will do by any procedure that takes less computational effort than just running the system and seeing what happens.

Well, in traditional theoretical science, there's sort of been an idealization made that the observer is infinitely computationally powerful relative to the system they're observing. But the point is that when there's complex behavior, the principle of computational equivalence says that instead, the system is just as computationally sophisticated as the observer. And that's what leads to computational irreducibility. And that's, in a sense, why traditional theoretical science hasn't been able to make more progress. When one sees complexity, there are always pockets of reducibility where one can make progress, but there's always a core of computational irreducibility.

Well, I think computational irreducibility is a pretty important phenomenon that's relevant even beyond what are normally viewed as purely scientific issues, like, for example, to the problem of free will. I mean, it's always seemed mysterious how we manage to act in ways that seem free of obvious predictive laws, if it's the case that our brains actually follow definite underlying laws. But I think at least a crucial ingredient of the answer is computational irreducibility. That even with definite underlying laws, there can still be no effective way to predict what a system will do, except in effect just by running the system and seeing what happens.

Well, computational irreducibility can also be viewed as what leads to the phenomenon of undecidability, originally discovered in the 1930s. I mean, look at this cellular automaton, for example, and ask the question: starting from a given initial condition, will the pattern that's produced eventually die out, or will it just keep going forever? In this case here, just running the cellular automaton tells one that after 36 steps, the pattern dies out. In this case, though, it takes 1,007 steps to find that out. And in these cases, even after 10 million steps, it's still not clear what's going to happen. And the point is that if there's computational irreducibility, there's no way to shortcut this evolution. So there's no finite computation at all that can always figure out what will happen after an infinite time. And that means that one has to say that it's, in general, formally undecidable what will happen.

Well, undecidability has been known about in mathematics and in computer science for quite a long time. But with the principle of computational equivalence, one realizes now that it's also relevant to natural science. I mean, if one asks questions about infinite time or infinite size limits, the answers can be undecidable, like whether a body will ever escape in a gravitational three-body problem, or whether some idealized biological cell line will grow forever or eventually die out, or whether there's a way to arrange some complicated molecule into a crystal below a certain temperature. And actually, I expect that when there are things that seem so random that they just have to be tabulated in things like chemical tables, it's a sign that there's computational irreducibility at work.

Well, there's another big place where I think computational irreducibility is very important, and that's in the foundations of mathematics. I mean, it may sound kind of obvious, but it's really a deep observation about mathematics that it's often hard to do, yet it's based on pretty simple axioms. In fact, right here are the ones for essentially all of current mathematics. But even though these axioms are simple, proofs of things like the Four Color Theorem or Fermat's Last Theorem are really long. And it turns out that one can think of that as just another case of the phenomenon of computational irreducibility.

So let me show you a little example about how that works. Here's an example of a simple proof in mathematics. These are some axioms up here, in this case specifying equivalences in logic. And this is a proof. It starts from one expression at the top, then keeps on using the axioms, and eventually proves the theorem that the expression at the top is equivalent to the one at the bottom.

Well, okay, so as a kind of minimal idealization of mathematics, one can imagine that the axioms just define transformations between strings. So with the axioms at the bottom here, these are proofs of a few theorems. So how long do the proofs need to be? Well, here's a picture for three axiom systems showing the network of all possible transformations. And the way this works, every possible path through each network corresponds to the proof of some theorem.

Well, the point is that the shortest path from one particular string to another may be really long. And that means that the theorem that the strings are equivalent has only a really long proof. Well, when people were thinking about formalizing mathematics a century ago, they kind of assumed that in any given axiom system, it had always eventually be possible to give a proof of whether a particular statement was true or false. So it was a big shock in 1931 when Gödel's theorem showed that that wasn't true for Peano arithmetic, the standard formal axiom system for ordinary integer arithmetic. What Gödel actually did, though, was to look at the kind of funky self-referential statement: "This statement is unprovable." Well, just by what it says, the statement fairly obviously can't be proved true or false. But as such, it doesn't seem like a statement in arithmetic. And Gödel's real achievement was essentially to show that arithmetic is universal, so that in particular, it can encode his funky statement.

Well, for the foundations of math, Gödel's theorem was a pretty big deal. But somehow, in all these years, it's never seemed too relevant to most of the things working mathematicians deal with. And if you needed something like Gödel's funky statement to get undecidability, that wouldn't be surprising. But here's the thing: the principle of computational equivalence should be general enough to apply to systems in mathematics. And it then says that computational irreducibility and undecidability should actually not be rare at all.

So where are all these undecidable statements in mathematics? Well, it's been known for quite a while that there are integer equations, so-called Diophantine equations, about which there are undecidable statements. Here's an actual example: a Diophantine equation explicitly set up to emulate rule 110. Well, this is obviously pretty complicated and not something that would sort of show up every day. But what about simpler Diophantine equations? Well, here are a bunch. Linear Diophantine equations were cracked in antiquity. Quadratic ones around 1800. And so far, another kind seems to be cracked roughly every 50 or 100 years. But I'm guessing that that's actually not going to go on, and that actually many of the currently unsolved problems in number theory will turn out to be undecidable.

Okay, but why has so much math then successfully been done without running into undecidability? I think it's kind of like theoretical physics. It's tended to stick to places where there's computational reducibility and where its methods can make progress. But at least in recent times, mathematics has prided itself on somehow being very general. So then why haven't rule 30 and rule 110 and all the other phenomena I've talked about and found in simple programs shown up?

Well, I think part of the reason is that mathematics isn't really quite as general as advertised. I mean, to see what it could be, one could just imagine enumerating possible axiom systems. And for example, this shows what theorems are true for a sequence of different axiom systems. It's like a sort of ultimately desiccated form of mathematics. The axioms go down the left here, the theorems go across the top, and there's a black dot every time there's a theorem that's true for a particular axiom system. So, is there something special about the actual axiom systems that get used in mathematics? Perhaps something that makes undecidability less rampant?

Well, if one looks at axiom systems from textbooks, they're usually pretty complicated. Like, here's logic, for instance. Well, it's been known for 100 years that one doesn't have to have those three different operators in there. The single NAND operator, or Sheffer stroke, is enough. But the obvious axiom system with that is still pretty complicated. Well, from all the intuition that I built up about simple programs, I suspected that there should actually be a really simple axiom system for logic, probably with just one axiom. And so I searched for it, and eventually I found it. And I know that this is the very simplest possible axiom system for logic. Here's the proof, by the way, needless to say, generated by computer.

Well, knowing this, I can say that if one just enumerates axiom systems, logic will be about the 50,000th one that one finds. But what about all the other ones? Well, most of them are perfectly reasonable axiom systems too. They just don't happen to be known fields of mathematics. And actually, I think that mathematics as it's developed has been, in a sense, tremendously constrained. At some level, it's really still pretty much just various direct generalizations of the arithmetic and geometry that got studied in ancient Babylon.

Well, if one starts looking at simple programs and just doing experiments, one immediately sees a much wider world, kind of a huge generalization of what mathematics has been so far.

Okay, well, let me now turn to a somewhat different topic. I, I want to talk about what the principle of computational equivalence says about, sort of, a big question: our place in the universe. It's sort of always been natural for us to think that we as humans are very special. But the history of science keeps on showing us ways in which we're not. For example, 400 years ago, we found out that our Earth isn't at a special place in the universe. And a century and a half ago, we found out that there wasn't anything special about the origin of our species. Well, every time we lose something in specialness, science gets more general, because it can drop another footnote that says, "Except in the case of humans." But right now, we still often think that we're special in our level of complexity or our computational ability. But one of the big statements that the principle of computational equivalence makes is that that isn't right. It says that there are lots of simple abstract systems and systems in nature that are exactly equivalent in terms of their computational sophistication.

Well, one sometimes has that impression anyway. For example, when one says something like, "The weather has a mind of its own." But what the principle of computational equivalence now says is that yes, fluid turbulence in the atmosphere will correspond to as sophisticated a computation as anything we do. So we're not special that way.

Well, one of the things this has a consequence for is the search for extraterrestrial intelligence. There's sort of been an idea that if we saw a signal that was produced by sophisticated computation, then there'd be no choice but to conclude that it came from a sophisticated extraterrestrial intelligence, some sort of extraterrestrial civilization. Well, the principle of computational equivalence says no. It's actually easy to do sophisticated computations, and lots of things in nature do them. It doesn't take our whole biological development and civilization to manage it. And that's, by the way, sort of why it's so hard to distinguish random radio noise from some kind of intelligent, compressed, encrypted signal.

Well, okay, so, so where does this leave us? It's, it's sort of interesting to think about how we interact with the ultimate limits of technology. I don't have any doubt that there'll be a time, potentially quite soon, when it'll be possible to capture all the important features of human thinking in pieces of solid-state electronics. And no doubt, things will get more and more efficient until everything is on an atomic scale, so that our processes of human thinking are just implemented by individual electrons whizzing around in lumps of something.

Well, of course, there are electrons whizzing around in all sorts of complicated patterns in ordinary pieces of rock too. And what the principle of computational equivalence tells us is that we can't expect the patterns made by the ones that represent human thinking to be ultimately any more sophisticated than those that occur naturally in something like a rock. That there isn't, sort of, any abstract essence of human intelligence that one can identify. But what, of course, is still special about us is all our details and all our history. And in a sense, it's the principle of computational equivalence that shows us that that history can really add up to something. Because if everything was computationally reducible, then, in a sense, nothing could be achieved by history. We'd always be able to get to the same endpoint without all that effort.

It's sort of interesting what the principle of computational equivalence ends up saying. It kind of encapsulates both the great strength and the great weakness of science. Because on one hand, it says that all the wonders of our universe can be captured by simple rules. Yet, it also says that there's ultimately no way to know the consequence of those rules except, in effect, just to watch and see how they unfold.

Well, it's remarkable to me what's, what's grown from those little computer experiments I did in the early 1980s. It's been very exciting. You know, when I actually started writing my book in 1991, I thought that it would not take very long. But I just kept on discovering more and more things. I kept on looking at different areas. I kept on finding all this wonderful stuff. One thing, though, was really scary: it seemed like I just kept on finding things that disagreed with, with existing conventional wisdom that, at least I'd always believed. And actually, sort of having the confidence to see beyond that was one of the biggest personal challenges in, in what I did.

People who've looked at the notes part of my book will know that I put a lot of effort into tracking down history. And one of the main reasons for that was that that was how I finally got convinced about things. I figured out by knowing enough about history to see why a field took the path it did, rather than the one I now think it could have done.

Well, back in the 1980s, I used to write academic papers about what I was doing. And I think it's fair to say that they were well received. They certainly started some, some big literature trees and so on. But by the 1990s, particularly with Mathematica, I was beginning to discover new things very quickly. And soon I had material for many tens, perhaps hundreds of papers. Most of all, I was beginning to build up a pretty big intellectual structure. And it was very clear that a bunch of papers scattered across all sorts of fields wouldn't be able to communicate that. So I decided I had to just keep working until I finished and until I could present everything in, in a single coherent way.

It took a lot of personal focus to do that. But even though I was the CEO of a very active company, I, I ended up working on my science every day and every night for, for more than 10 years. I talked to experts when I needed to, particularly about history. But mostly I just kept to myself, and I kept on polishing everything until I could really explain it clearly. And gradually, I filled in all the parts of the book I wanted to write. And finally, early last year, the, the writing was finished.

Well, one problem was that the book I'd made didn't really fit very well any of the usual existing models in the publishing industry. So I ended up deciding it was easier just to publish it through, through our own company.

Well, one of the big questions is always then, how many copies to print? Well, we talked to some people, and needless to say, the responses were all over the map. Some were saying, you know, "This is terrific stuff, print lots of them." Others were saying, you know, "You're crazy, nobody's going to be interested." Well, in the end, I, I decided to print 50,000 copies. And on May 14th of last year, they were done, and, and the book was officially published. What happened was rather exciting. By the, by the end of the day on May 14th, all the 50,000 copies we had printed were spoken for.

Well, then things really started happening. A huge response in many communities and in the media. Some of it very sensible, some of it pretty wild and woolly. And really, all the classic signs of the early stages of a paradigm shift. Well, as a student of the history of science, I've certainly read a lot about paradigm shifts. But it's rather scary to see one up close, to see the kind of actual dynamics and emotions of the whole thing that you never see when you just learn the science and the ideas years later.

Of course, it helps me personally that I've seen some of this before, because when Mathematica came out in 1988, I think it's fair to say that it led to something of a paradigm shift too. And as usual, there was a certain amount of turbulence at the beginning. But gradually, almost visibly, it worked itself out. And now, nearly 15 years later, it's like, hasn't it always been this way? Of course, there's still much more to come with Mathematica, particularly when some of the ideas in Mathematica about symbolic programming and so on really get absorbed. But the new paradigm shift is much, much bigger, and it'll certainly take many years, many decades, to work its way through. But I think it's off to a really good start.

I mean, of course, there's the usual sort of Kuhn stuff going on: people saying, "This must be just like thing X that I've seen before," or, "No, no, nothing like this can possibly be right," or, "This just isn't science the way I think of science." Well, it took me 20 years to come to terms with what I discovered. And so far, the book has been out for less than a year. But I'm really impressed at how fast lots of people are understanding things and, and really starting to work on things. I mean, I, I wrote the book very carefully, and it's nice to know that there are lots of people who read it cover to cover multiple times.

By the way, I might mention that if you're just dipping into the book, do be sure to read not only the beginning but also the end of the main text. And don't forget the notes. The, the whole second half of the book is historical and technical notes about all kinds of things. And if there's some particular area you know well, you might just start off by looking at the notes about it. That seems to be a good way for many specialized folk to, to get into the book.

One thing that's great about the technical notes was that I was able to use Mathematica notation, which ended up working out really well. It let me say a lot in each line, really clearly. And of course, it also has the huge advantage that not only can you read it, you can also actually run it. And in fact, you can download all the programs from the book with test examples and so on from, from the Wolfram Science website. By the way, in version 4.2 of Mathematica, which came out soon after the book, we added a very efficient built-in cellular automaton function, kind of as a way to commemorate the book coming out.

Well, within the book, a lot of the presentation is very graphical. And of course, all the graphics were made by Mathematica programs. And it turns out that with some nifty new technology of ours, we've been able to take those programs and make a standalone piece of software from them. It's called NK S Explorer, and it lets anyone reproduce the main pictures in the book and then go on do their own experiments. Actually, it's kind of amazing how easily one can discover new stuff with NK S Explorer. It's a lot of fun, and there's, there's a lot of science to be done with it.

You know, my, my book is really just the beginning. I mean, it's been exciting over the past six months to see just how many people have gotten energized to work on the ideas in it. Actually, in many ways, it's been quite overwhelming, and it's made me really want to figure out just what the best infrastructure is to make all of this stuff really prosper. We're already organizing some things that have started appearing on the Wolfram Science website. Um, there's quite a bit of reference material related to the book, and there'll gradually be more. There'll also soon be a large collection of open problems, an average of about one for every page of the book. And there'll be a huge repository of information about specific simple programs, about sort of what's out there in the computational world.

You know, one might have thought that once one had finished figuring out all the things in NK S and then writing a book about them, that will be enough. And certainly, in all the extra time I've had from not being in the middle of writing NK S, I'm, I'm having a great time right now working on Mathematica 5 and Mathematica 6, and really digging into all the terrific things that I've really realized one can do with what we've built in Mathematica. And I'm also gradually recovering from the actual process of of writing NK S, not being a, a recluse anymore, and going out and and giving talks and so on, and getting ready to take the next steps to make the ideas in the book grow and prosper in the best possible way in the world, and building more tools to do what I like doing best of all, which is to come up with new ideas and figure out new things.

So, okay, well, what's going to happen with all the stuff I've, I've talked about here today? Today, I think it's going to be a long story played out over at least many decades. But I think three big things will emerge. First, a new area of basic science, like a physics or a chemistry or a mathematics, but concerned with understanding what's out there in the computational world. Second, a whole bunch of applications to science, to technology, and to other things. Lots of new raw material for making models of all sorts of things, including perhaps our whole universe. But also lots of new directions for technology, because now we have all these new mechanisms, not just gears and wheels, but things like rule 30 too, that give us access to many more of the things that nature can do. And that also give us new ways, for example, to approach making algorithms or doing nanotechnology. But there's also kind of a conceptual direction: understanding more about the fundamental character of science and mathematics, and about the place we have in our universe, and in a sense, giving a new framework for thinking about things in general, and a new foundation for a basic thread in education, sort of an alternative to mathematics.

Well, there are just so many possibilities, so many, so many things to be discovered, so much kind of low-hanging fruit to be picked. I, I, I wish I'd been able to tell you more here today. I, I've really only been able to scratch the surface. But I hope I've been able to communicate at least a little of what's in that big book of mine, and what, at least, I've been so excited about all these years. Thank you very much.

[Applause]

You see all kinds of interesting patterns in your cellular automata. Do you see any, uh, patterns that correspond to activated events, to, to what?

To what I'm sorry? Activated events, like in chemistry, for example, the activation, you know, like when you jump over a barrier, for example, a rare event like that?

So what one might say is that, um, in, in this, this is this rule 110 cellular automaton, for example, it's a completely deterministic thing. But occasionally, one might say that if one looks over here, that, uh, that one of these kinds of structures, that what it does when it first collides with something or some such other thing, is a rare event that happens only under very particular circumstances. I mean, another example of that might be, let's take another example here. So one can ask the question, uh, starting from lots of different initial conditions, exponential kinetics related to, what do you observe exponential kinetics related to, to crossing barriers and things?

Yeah, activated events that, that would be a, that would be a, I mean, yes, you can set up cellular automaton kinds of things which do that, because they do it for the sort of the same reasons that you can have things happen with, uh, in optics and places like that, because they effectively obey the same differential equations on an aggregate, in terms of on an aggregate level. But that isn't particularly interesting. I mean, what's more interesting is kind of whether you can, for sort of more combinatorial reasons, see rare, sort of, rare events happen.

Um, I mean, let me give you an example here. So this is a particular cellular automaton rule, and this is showing what happens for lots of different initial conditions. Uh, usually it just dies out, but occasionally, um, it gives it leads to some particular persistent structures. And, and here are all the persistent structures that you can get. And what you see is that, let's say you want to, you're trying to get a structure which is, um, uh, let's say you're trying to get something which which propagates across the system rapidly. Uh, that that doesn't happen very often. It only happens in this very rare case. And if, for example, you look at all possible initial conditions with sort of randomly chosen ones and zeros, the probability that you get something that propagates across the screen like this will be, in a sense, exponentially small, because it occurs only for a particular configuration of ones and zeros that's quite long, and that has probability two to the minus that length of occurrence. So that's the kind of thing.

And actually, it's pretty weird because if you look at, um, different kinds of systems, um, like, for example, here's another one of these, um, these systems where you're seeing where these are some of the kind of persistent structures that occur. You might conclude from looking at this that, well, yes, there can be, I mean, if, if we look at these systems just starting off from random initial conditions, you might say, well, okay, there are these persistent structures that arise in in particular cases, but there'll always be things that just look roughly like this. Okay. Well, it turns out that if you run that system for lots and lots of different initial conditions there, you eventually find an initial condition where, no, it doesn't look anything like that. Instead, the system actually produces this, um, this, this funny kind of single block of, of, uh, of stuff as its output. So, in other words, it's a very rare thing. The probability that you have one of these from random initial conditions is quite small. But if you have a long enough initial condition, at least somewhere you'll get one of these things, and the system will be sort of taken over by that thing.

It's kind of an interesting thing because if you ask for, sort of, ask in statistical physics or something for limits of, of what the system does at large times, what you realize is the presence of these kind of unexpected things showing up prevents one from ever having an ordinary kind of thermodynamic limit for, for one of these kinds of systems. You see what I'm getting at? Is in order to, to make a connection with life, for example, you have to be able to see metastable situations in, in your simulation, right? You know, we are all in metastable situations. How does your, how does your thing, uh, simulate that?

Well, so, so there's a, okay, let me try and say one more thing about this. It's, um, there's a question about, um, let me, let me show you what what happens in, um, this has to do with thermodynamics. And the question is sort of that there's a basic question which is, if the underlying laws for the universe are reversible, how come the things that we see in everyday life are so often irreversible? What it means for the laws to be reversible is that one can as well go backwards as well as forwards from a different given state in the universe. Yet we know from many kinds of things, if we take an object and we let it, you know, we drop it on the floor and it breaks, it's very hard for us to go backwards and reassemble that object. Yet at the level of individual molecules bouncing around, obeying, let's say, laws of mechanics, it's perfectly possible for their motions to be reversed and for what they do to go backwards, just as, just as well as they go forwards.

Well, that kind of phenomenon, it's pretty easy to capture. And one of the kinds of systems I've talked about, this is an example of a cellular automaton that is, um, that is reversible in the sense that, um, it, um, you can, it has a rule that allows you from any given condition here, both to figure out uniquely how to go forwards and to figure out uniquely how to go backwards. And so this is, this is a cellular automaton which microscopically is precisely reversible. What's interesting about it is that if you look, kind of on a large scale, what you see is something that is, while in principle reversible, is in practice very hard to reverse.

Let me, let me show you an example here. This is an example of of running a a similar cellular automaton, um, starting off from, um, that go, um, starting off from, uh, let's see, down, down here, um, there was sort of a simple state that was that was produced here. And one can uniquely go backwards from that simple state. One can uniquely go forwards from that simple state. But once one's got down here, even though in principle one can uniquely go backwards, in practice it's sort of a hard problem of cryptanalysis to figure out exactly how, how one should get back to that initial state.

The thing that I'll say, and, um, then I'll, I'll stop addressing this particular issue, um, is one can ask for different cellular automata, for example, um, what happens with respect to this kind of randomization that we saw in that case. Now, normally, what, um, sometimes the behavior is simple enough that you don't get any randomization, you just get the thing sort of periodically repeating, doing the same thing. Often you get what's sort of typical second law of thermodynamics behavior, that even though you start from something simple, you quickly get apparent randomness, and the thing sort of degenerates into, sort of, the, the motion turns into heat, and you, you get all this kind of irreversible randomness.

Okay, one thing that one can do when one starts looking at these simple programs is one can get a little bit more explicit about how this kind of phenomenon of randomization works. And it turns out that curiously enough, there are some cases in which you do not get the kind of, uh, you, you don't get something that kind of just remains fixed or becomes periodic, nor do you get something that shows the kind of standard randomization of the second law of thermodynamics. Instead, you get a funny kind of thing that seems to have essentially an infinite length of transient, and that contains lots of little pieces that in effect act like metastable states. The usual interpretation of, sort of, law of entropy increase doesn't seem to apply to this particular system. It seems like this system sort of continually generates little metastable pieces that last forever. And it may be that something like this is a reasonable model of some kinds of things that happen in, for example, biological systems, and the way that they kind of, sort of, at least for a very long time, seem to evade the second law of thermodynamics. So that's a little bit on that.

At least if you hear lots of examples of complex patterns generated by programs, say different kinds of leaf patterns, for example, is there any way to explore the space of simple programs that would have given rise to the leaf pattern, the complex pattern? So is there any guidance that you can give in that?

As, right, so, so the question is, how do you find which program it is that can, given a phenomenon, how can you find a simple program that will reproduce that phenomenon? I mean, traditional sort of statistics and, and model fitting and so on, is very much oriented towards fitting parameters, fitting functions to behavior. What we're asking for here is fitting programs to behavior.

Well, unfortunately, there's, there's sort of a piece of bad news about that, which is that it's, it's fundamentally hard, because even given a program, it's very hard to know what it will do. And so, given that fact, going backwards from the phenomenon to the program is sort of inevitably very difficult.

Now, you know, in a sense, what, uh, so there, there sort of, it's not realistic to have a systematic machine that takes phenomena, grinds them up, and finds some programs. And it's interesting to see the various things that we do in perception and analysis, whether it's for visual perception, whether it's for data compression, whether it's for cryptanalysis. All these kinds of things, we can kind of of ask, what do those things, um, how far do those things get in taking a phenomenon and kind of finding things from it? And the answer is, they don't get very far. They do well with with repetition, whether it's for Fourier transforms, frequency spectra, things like that. Um, some things work with nesting, for example, Lempel-Ziv compression works with finding nested patterns and things. Um, some forms of cryptanalysis do that too. But finding, sort of, breaking down these other things, that's not something that, that those methods can can do. And in fact, I, I claim that it's sort of fundamentally difficult.

I mean, you can even look, for example, in mathematics, you can ask the question, um, whether, what kinds of things, sort of, traditional mathematics can do. And, and so, for example, well, if, if you have some kind of periodic pattern, it's very easy to reproduce that with traditional mathematics. I mean, the, the color of a cell at position X, Y is, you know, whatever it is, X plus 2Y mod whatever, whatever it is. In this particular picture, it's a simple formula for something like, um, it, it turns out for something like a nested pattern like this, there's a simple procedure that involves the digit sequences of the coordinates. Or in fact, another thing you can do, I mentioned, well, another thing you can do for these nested patterns, it turns out that at least simple nested patterns, that very simple nested pattern at the top is binomial coefficients mod 2. Even the nested pattern at the bottom, that isn't much more complicated to us visually, turns out to be given by Gaussian polynomials mod 2. And even for for nested patterns, it's not very clear mathematically. Sort of, there's no mathematical analysis technique that will give you the kinds of generalized things that you need for that. And, and in fact, you can, you can look at other kinds of things. You could look at, for example, representing these things in terms of, of, uh, logic functions, and you, you have the same kind of problem.

So I think there's sort of a general result that you can't, that you can't sort of systematically go from the phenomenon to find a simple program that fits it. As a practical matter, what can you do? Well, for instance, one of the things, the first thing you can do is get some intuition about what simple programs can do, so that you can have an idea whether searching a space of simple programs, exhaustively searching through a trillion programs or something, might actually find one that's relevant. The second thing is that, as a practical matter, what, what I've been interested in doing is making a kind of giant atlas of what simple programs actually do, kind of what's out there in the computational world, so that one can, uh, kind of pick that, pick up the things from that atlas to kind of know whether the phenomenon that one's looking at is actually something that's relevant.

I, it's kind of an an analog of something like an organic chemistry database, where sort of the, instead of chemical compounds, one has different simple programs, and one, one sort of asking, what are all the properties of all these simple programs? And, um, and then kind of hoping that, or expecting that when one has a particular phenomenon that one wants, or a particular engineering problem one's trying to solve, that one can kind of go to this atlas and potentially find something that's relevant.

[Music]

[Music]