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.