[MUSIC] Hello everyone. Today we'll continue our course on simulation and modeling of natural processes with a chapter on cellular automata modeling. So the content of this chapter will be mostly based on the book I wrote with my colleague, Michel Droz. So, I'd like to start with some basic definition and concept. And first question we will ask is what is a cellular automaton? There are several definition. I guess the one we want to keep here mostly is decided at its [COUGH] mathematical abstraction of a physical process. In other words, it's a fictitious universe. As we'll see everything is discrete in this little universe that we create. On the other hand, you could also consider cellular automata as a mathematical object, which is interesting for his own sake. And in particular, it's interesting because it connects physics with some calculability question, for instance, universal computation, intractability, algorithmic complexity. And we see that sometimes calculability and physics are closely related. So, to introduce you to cellular automata, I just wanna take a very simple rule, probably one of the most intuitive ones. So, I will consider a chess board. So my space is discretizd in cell, as you can see on this picture. And the cell can have two colors. Either they are white or they are gray. And in this image, I've only one gray cell and everything else is white, okay? So, we say that the possible state of my universe Is 0 or 1 for each position i j of my space. And this state, or these states, will evolve in time according to a rule that I have to specify. And a rule in this very simple example is just to sum up the states of the four neighbors of each cells. That is the cells which are north, east, south, and west of the cell which is updated. And if this sum is even, the central cells become 0. If it's odd, it becomes 1. So let's consider as an example these cells, which is gray, which I assume to be 1. It has four neighbor, which are 0. So 4 times 0 is 0. It's an even number. So, these central cells become 0, it's white now. Now, any of the four neighbors, they see these cells in the neighborhood. And of course their sum is 1, which is a odd number and they become 1, okay? So all the cells are dated at the same time, so it's what we call simultaneous updating, or parallel updating, and you go from a configuration at time t to a configuration at time t + 1. So this rule seems quite uninteresting but surprisingly generate very interesting patterns that you can see on these slides. So here we started at time t = 0, with space which is mostly white, so you don't see all the cells surrounding the central part. Central part is rectangle of about, I think, 8 x 10 black cells. And we just let the system evolve. And for instance here, you have a time a bit later. You see that you get a pattern. So, it's not after one iteration but after 31 iterations. And this is a bit later, and so on, and so on. So you see that you generate many different pattern out of these very simple rules. It looks like we are generating something complex, and I will come back a bit later in a forthcoming module about this question. For now we just learn how we define a rule and what type of picture we can get out of it. So if I wanna be a little bit more formal, I would say that cellular automata is a discrete space A. So you just take your natural space, could be in 1D, 2D, or 3D, and you divide it regularly in cells. Then you assume that you have a discrete time for evolving your system. The system doesn't exist in-between, it has only intrinsically a discrete time. It's not a discretization of a process, it's just by definition some object which evolve discretely. And the states of each of these cell is discrete number, okay? So it belongs to a discrete set S, which can be 0, 1, as the previous example shows, but it can be a bit more values for more complex situation. And then the law that govern this universe is given by what we call an evolution rule or the cellular automata rule, which is a function which is local. So it acts only on a cell and its immediate neighbors. It's homogeneous in the sense that it's the same rule that you apply to all the cell in your systems, and it's defined on the neighborhood. It mean that what are the cell that the central cell can see to decide of its future. As I mentioned, it's synchronous updating, so all the cells take at the same time the decision to evolve according to the configuration of their neighbor. So mathematically, you can write this as a tuple, but we're not gonna use this so much here. So I mentioned that neighborhood is a key aspect of cellular automata. So, there are several neighborhoods that are usually defined and very much used. So this one is called a von Neumann neighborhood. This one is called a Moore neighborhood. So basically it tells you what are the neighbor that this central cell will look at to evolve. So the von Neumann neighborhood, it looks at itself plus it's four neighbor; north, south, east, and west. In the Moore neighborhood, it also use the diagonal cells to decide the future. You have other possible neighborhood that exists, like for instance the Margolus neighborhood or other one that you can build yourself, there's no limit for that. You just define what are the cells that are visible to do the updating rule. Now of course, your space is usually not infinite, especially if you're on a computer, you have to find boundary conditions. The simplest situation is to have periodic boundary condition. I mean that you wrap around a corner of your space, which is illustrated in this 1D case, where you have your system here. So first cell, last cells, and then the left neighbor of this first cell is actually b, which is the last cell. So basically, the right neighbor of b will be a. So you just make a closed loop of this. But you could have a different boundary condition, according to a problem you want to simulate. For instance, you could put a fixed value, here I put 1, anything that you like. You can actually recopy the value you had all ready as a fictitious neighbor. Or you can take the one on your other side to put here, and you can certainly have other ideas. So everything is free to you, but those neighborhood are well-known and used in several simulations. So the definition I gave you for solar automation is something which is purely deterministic. Each time you run the same rule on the same initial condition, you get the same thing, but you could also want to extend this definition to a stochastic cellular automata. And stochastic cellular automata would be when the rule is itself random. It mean that you may have several rules that you apply at a given position with some probability. And actually it's enough just to have an extra bit of information on each cell, which also evolve in time to select which of the rule you want to apply. So it's already somehow included in the original definition, provided you can have a state of a cell which evolve randomly. [COUGH] And we know cellular automata that produce random numbers, so it's It's possible. We also discuss the fact that we have a synchronous updating. Sometimes synchronous updating makes some oscillation in a system, and it might not be very physical sometimes. There's a big debate about whether synchronous or asynchronous updating is better to model a physical system. By definition, a CA is synchronous, but if you want asynchronous updating you just have to select the cells you want to update at a given time step. And again, it's just by adding a new, an extra state to the cell, to tell it whether it will update at this given time. And of course, this extra state has to evolve in time or so, so that on average, all the cell are equally updated. Again, it's something that you can implement directly on your synchronous model, so it's not really a problem in term of definition. It's just a practical way you would of course in your computer use a more efficient way to do this asynchronous updating. Finally, you can say that you want a rule to be different on different position of your space. For instance, you would say that the left part of your space is updated according to rule one, and the right part of the space to rule two. And again, it's enough to have an extra state which tells which rule you apply on which cell. So again, it's not impossible with the definition I gave you before. So when it turns to implementing a cellular automaton in a computer, you have several ways. So one is called the on-the-fly calculation, so for each cell, at each time step you just compute the rule explicitly. So for my parity rule I explain to you before, you just have to do the sum of your four neighbors. I use this sign, the plus with a circle around, to say that's it's the plus modulo 2, so it will actually give me a result which is 0 or 1, according to the sum is even or odd. So, that's a way to compute just by a mathematical formula that you keep repeating. But since, actually you have only a finite set of possible configuration. So your four neighbors, there are four neighbors here, they can only take 16 possible different configurations. So maybe you wanna encode all these 16 possible state to pre-compute all the output. And that's called a lookup table. So what it means that from the value of your neighbor, here four neighbors, you compute an index, which is just a number between 0 and 15, according to this simple formula. And then you get the new state of the cells as just the value of a table for this specific index. So then, if the rule is complicated, you can precompute everything at once and have a very fast implementation. So, it's interesting to just count how many universe I can build out of this idea. So a universe, or a system, is defined by the choice of its evolution rule. So how many rule can I define on my space, okay? So if you can have m state per cells, and each cells is looking at k neighbors, it's simple to see that m to the m to the k is the number of possible rules. So why is that so? m to the k is [COUGH] the number of possible configuration of your k neighbor, knowing that they takes m possible value each, okay. For all these configuration you have to give the output, which is a number belonging to the m possible states. So you have m to the m to the k possible. So it's extremely big, okay. So the space of possible rules, or the possible universe that I can build out of a cellular automata, is extremely large provided that m and k are even small, okay? Actually most of the rule that you build, they are quite uninteresting. So only a few are doing nice things and can be related to physics. And most of the rest, they look like random noise, or they go to zero, or they go to one, or it's not very nice. It's worth mentioning the work done by Wolfram on the one-dimensional cellular automata, where he classify all the possible rules with states zero and one. So actually it should be better to say two possible value than one, sorry for that. And you see yourself and your left and right neighbor, so you can build out of this 256 possible rules, and so you can study all of them. And here you have a sample of four possible type of evolution, which Wolfram classified in four classes, class I, II, III, and IV. So it's a one-dimensional cellular automata, and I'm showing you a 2D picture, so how is it? You should understand this the following way. So the first line that you see here, this is actually the initial condition. Then at time t plus 1, I draw a second line with the second state, and so on and so on and so on. So basically you see a 2D picture developing out of the evolution of a 1D line. So you have system here, everything goes to zero, or potentially everything would go to one. Here you see that goes to a periodic situation. Here, it's more interesting. It goes to something that we may call chaotic, okay? It's a very rich picture. And more interestingly, you see this class four, which has a combination of persistent structure, chaotic behavior, constant states. And that's probably what the most interesting situation, where you see a very rich and complex behavior. So with this I would like to terminate this first module on basic concept and definition. And next time we will discuss a little bit some historical fact about cellular automata, so thank you for your attention. [MUSIC]
