That's rule 150. We can also consider a different rule. This is for example rule 105. Of course because there's 256 possible f rules we're going to run out of them eventually. There's a numbering system that people have invented and so usually when someone says rule 105 you can actually figure out exactly what that look up table will appear as. Here's rule 90. You start to see some of these triangular patterns are quite familiar, the ways in which these triangles interact with each other. But here's the different one, this is rule 110 you can see it's sort of asymmetrical. So even if I begin with the same initial conditions as I ??? for rule 150 Instead of getting a triangle that sort of propagates out evenly in both directions you kind of have asymmetry here, so in fact in Rule 110 a triangle propagates only in one direction and keeps a hard boundary on the other. You can also see here which is kind of fun, it's quite clear now that rule 110 as the triangle propagates off the left edge we have it wrap around to the right edge. So the neighbor of a pixel on the far right-hand side includes a pixel just up and to the right which wraps around to the far left. In fact rule 110 is kind of a magical rule. It's what we call Turing universal. I just put up the lookup table at the top there. But the eight possible things that could happen give it a particular cell that you're wondering what its state is going to be. Rule 110 is interesting because it turns out that it can compute any possible function. It's actually equivalent to a computer, to a piece of Python code. So how does that work, how does that make sense? Well, one way to think of it is this If I imagine let's say a piece of Python code that I want to execute I can of course just put it into a laptop and have it run. But if I'm really clever what I can do is I can take that Python code, turn it into a very long initial condition for rule 110, evolve rule 110 forward, wait for a certain amount of time and then read out at the bottom the output of that piece of Python code. Of course the hard part is figuring out how to turn that Python code Into a line of ones and zeros that form the input to rule 110. It's not that easy. But what Matthew Cook was able to do back in the early 2000s was show that it is at least in principle possible to do that. In fact rule 110 given sufficiently rich initial conditions can perform an arbitrary computation. It is in fact one way to implement a Turing machine if you know this language from computational theory. So how did Matthew do it? Well, it's kind of a fun way to play just to get a sense of how you might do it. Here are two examples of how rule 110 behaves given a particular set of initial conditions. What you can see here, let's just focus on the left panel, is all these different structures that appear you have what are called gliders. So if you look at that sort of polka dot points or that polka dot stripe there Cook called this an A4 glider, and when an A4 glider meets what he calls an Ebar glider which is a much more complicated pattern that propagates to the left the A4 glider and the Ebar glider depending upon exactly how they collide with each other can either be absorbed, can change the state of the Ebar glider, and can lead to reemission. So on the Left-hand side the A4 glider hits the Ebar glider, kind of gets stored there for a while and gets spat out a little bit later that A4 glider continues unimpeded but if it had hit the Ebar glider a little earlier in its evolution in that case what we would have seen is that the Ebar and the A4 glider return into a stationary object, into a C2. And that C2 would stay stationary over time. So what Cook was able to do is show that in fact all these little sort of discreet propagating structures that emerge naturally from rule 110 and there's no magic here in the sense that all of these patterns are produced solely by Rule 110. Playing out the rule for each point what happened for each point is the state of each point is defined by the three units just above it. It's just playing out that rule over and over and over again to produce these lines as they come down the page. What Matthew Cook was able to do was show this is essentially enough to produce what you might now think of as a set of logic gates or way a system could write things to a tape, read things back from the tape, do something to the value of that tape depending upon what it had read, and what else was happening elsewhere in the system. So Rule 110 turns out to be not just a kind of playful way to make cool patterns, but in fact something sufficient to describe arbitrarily complicated systems. So this has been a little introduction to cellular automata. What I've tried to do is first of all of course tell you how it works, tell you what the rules are of this model and then try to give you a sense of ??? is a great diversity of behaviors that we can see here. We saw rule 150 producing these propagating triangles that overlap with each other. We saw an example something like Rule 90, where it also produced that kind of triangle-like pattern but the rules of how those triangles interacted with each other were slightly different, so visually it looked different. Then of course something like Rule 110, which is even crazier. Here if you set things up correctly, not only do you get these propagating objects, these spreading waves or indeed even these packets moving around. But in fact the logic of how those things interact with each other is sufficiently complicated that you can perform an arbitrary computation, that you can actually for example run a piece of Python code or C code or BASIC. So cellular automata are actually much more complicated than the Markov chains we considered in part because whereas the Markov chains the state at one point in time depends solely upon N states just previous here in fact if you look far enough back in time the value of any particular point is influenced by a huge number of inputs from arbitrarily far away. So the cellular automata even though it has the same forgetfullness as the Markov chain and even though the rules themselves are incredibly simple the fact that the one-dimensional line that these rules operate on can be arbitrarily large means that we'll have, it will turn out, a new kind of problem for how to describe the system and in particular a new kind of problem when we come to renormalize the system because what we're going to do now is imagine taking one of these patterns produced by a cellular automata Squinting at it in some way, producing a reduced description of that pattern and then trying to figure out the kinds of rules that that pattern could be described by.