1:05

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,

Â 1:36

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.

Â 2:36

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.

Â 3:40

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.

Â 4:03

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.

Â 5:27

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.

Â 6:00

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.

Â 6:16

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.

Â 7:12

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.

Â 8:03

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.

Â 8:25

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.

Â 8:55

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.

Â 9:37

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.

Â 10:13

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.

Â 12:51

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.

Â 14:23

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.

Â