0:46

And, you see that this [COUGH] building of a structure at large scale

Â [COUGH] is like if the whole system is more than the sum of its parts.

Â So emergence of microscopic property out of a simple

Â microscopic dynamic is what people call manifestation of complexity.

Â So cellular automata, they exhibit a lot of complex behavior by having

Â structure patterns at a bigger scale.

Â So today, I would like to illustrate another aspect of

Â complexity out of two rules.

Â And the first one is the game of life,

Â which has been proposed by John Conway in the 1960s.

Â So it's a universe where you have a organism that can be dead or

Â alive, 0 means dead and 1 means alive.

Â And a dead organism can come back to life,

Â provided it has exactly three parents, so it's a bit surprising rule,

Â but that's the way we get some interesting behavior.

Â And a living organism, or living cell,

Â will die if it's surrounded by less than two or more than three neighbors alive.

Â Meaning that this individual, they don't like isolation and

Â they don't like surpopulation.

Â So, we use a square lattice with eight neighbors, so

Â that's the [INAUDIBLE] neighborhood in only two states, zero and one.

Â And you can observe on this picture the time evolution

Â of an initial random situation.

Â 3:02

Let's do it one more.

Â You will see at the top of the screen you have

Â this structure that's actually moving.

Â So those are called gliders, and they are actually organized system

Â of five cells which you see here in detail, so it's just this glider isolated.

Â So if you put a time t0, you have this configuration of [COUGH] cells alive.

Â You can apply the rule, as I just mentioned on the previous slide.

Â And you see that the next time you get this configuration,

Â which then turn into this one, this one, and then finally,

Â after the [COUGH] four step, you get the exact same configuration as initially,

Â but moved within the space, so it moves back and right, by one cell.

Â So it takes five iteration to move in the space.

Â So what's interesting here is that in the rule that we discussed in

Â the previous slides, there's nothing like movement.

Â But here you can produce an arrangement of cells which,

Â by specific structure, has a new potential, it has a potentiality to move.

Â So this new object which is a combination of elementary [COUGH]

Â cells has developed a new capability, which is movement.

Â And that's very interesting in term of understanding complexity,

Â because you can see that by putting together simple things that can do simple

Â things, I can create a new object that can do more complicated things,

Â or the new functionality which are beyond what we put in the system.

Â And of course, we could be tempted to think that that's the secret of life.

Â To develop new functionality out of simple component.

Â But we will of course not go that far.

Â But we can still explore the game of life.

Â And discover that in addition to glider, you have other object that you can build.

Â And if you search Internet you can find an example of what's called a glider gun,

Â so it's actually this structure of cells that you can see here,

Â which keep producing gliders.

Â So if you run this, you will see that every few iteration, you have a new

Â glider that is produced, and so on which of course keep propagating into space.

Â But you can go one step further.

Â You can also find a configuration which is actually a system which produce a gun for

Â gliders, and so on and so on.

Â So we can build all kind of structure which are of increasing complexity,

Â in term of the number of cells and their spatial arrangement, but

Â their functionality keep increasing.

Â 5:55

And actually what you [COUGH] discover with this game of life,

Â it's what we call a universal computer, it mean that you always have an initial

Â condition of the game of life, which can reproduce any electronic circuit.

Â So it can basically, you could be at a computer,

Â out of initial condition of your game of life, and

Â it will simulate this logical gates like AND [COUGH] gate, XOR gate.

Â And out of this you can do any calculation that a natural computer can do.

Â Of course, it's much less effective, but

Â still, there's no limit to the computation you can do with the game of life.

Â And then if you browse the web, you will also find very nice example where you can

Â use a game of life to compute the prime numbers.

Â So it looks a bit surprising, but this a very interesting

Â illustration of this universality that is behind that.

Â But anyway, what we want to illustrate here is the fact that out of a very simple

Â component, we can build more complex component that do more

Â than the sum of the little element that you use.

Â [COUGH] The emergence of new functionality, new properties.

Â And [COUGH] I'd like to illustrate another aspect which I think has

Â some importance in the scientific methodology,

Â which is illustrated by the model called Langton's Ant.

Â And so this ant is just a fictitious animal.

Â It's a dot on a lattice that will move across a set of cells.

Â And it has a very simple rule of motion which is illustrated on this picture.

Â So, the ant is represented as an arrow from the direction in which it moves.

Â And so when it reach a cell which here is gray,

Â then the rule is that the ant turns left, so it will go up.

Â But also it change the color of the cell you just crossed.

Â Okay.

Â Now if it enter the cell which is white Then you turn right and also toggle the.

Â And that's all.

Â So, with this you can do a simulation and see how your ants will evolve.

Â So, suppose I take an initial

Â space where all the cell are wide except one, which is this one.

Â So, it could be any one.

Â But just for the example, this one.

Â And we start with this ants coming here.

Â So, it's entering a white cell.

Â So, it should turn right and color the cell.

Â Now, it's entering a colored cell, so it should turn in the other direction,

Â which is this, and change the color of the cell.

Â And it goes on like this.

Â So, it can play a little bit.

Â Okay?

Â 9:06

So, you see the yellow dot is the ant.

Â And the blue are the color of the cells.

Â So, you see that it's a rather chaotic motion.

Â And you could think, well, okay, not interesting until suddenly, at some point,

Â you have a very special movement, which is called a highway.

Â So, there's a highly organized movement of the ant

Â which makes it move in a straight line.

Â Of course, in a bit complicated way, like a sewing machine,

Â I would say going in a zig-zag.

Â But still it's a way to go to infinite.

Â And, again, this is a deterministic rule.

Â So, if I repeat it I will get exactly the same approach.

Â 9:48

So, that's what you observed in our animation.

Â So, just chaotic movement.

Â But suddenly, at this time,

Â which is around 10,000, then you start this highway.

Â So, the ant starts building this structure which takes it far away.

Â Okay?

Â So, that's maybe not expected from the rule that I gave you.

Â So, a question we can ask is could I prevent the ant to go to infinity?

Â Could I prevent this ant to build this highway?

Â And, of course, the idea would be to put some of this colored cells along it's way

Â so it will force the ant to stay in a limited space.

Â So, mathematician, they thought of this problem and

Â they actually demonstrate that it's impossible to go to infinity.

Â And the demonstration is just illustrated in this picture.

Â So, since you have square lattice,

Â 12:30

So, now you can also say, well, I can put more than one ant and

Â see how they interact.

Â And the only thing you have to do is to deal with the case where you have two,

Â three, or four ants on the same cells which are coming from different direction.

Â So then, it's just a matter of counting how many

Â ants you have to decide to change another color.

Â If you have an odd number of cells, of ant on the same cells,

Â you don't change the color.

Â If it's an even one you change the color.

Â So, let me also illustrate this on an animation.

Â You see that things go much faster.

Â You start also building highways.

Â But what's very interesting, I don't know if you noticed that this highway

Â was actually built by one ant and

Â then another ant could really move extremely fast on this pass,

Â then catch up with first ant and destroy the movement.

Â So, let me try to replay it so you can pay attention to what happened.

Â The highway's built and suddenly there's ant that will run into this and

Â destroy the movement.

Â So, what you observed on this simple simulation

Â is that with many ants you create the highway much earlier.

Â So, it's kind of a co-operative dynamics.

Â But it's all a destructive dynamic because some of this highway can be destroyed.

Â 14:01

So, another thing I would like to illustrate is

Â we saw that with one ant, you know that the single ant has to go to infinity.

Â Okay?

Â What happened when you have, let's say, two ants?

Â So, this is an example where you see the trajectory in yellow, the two ants.

Â So, it's a bit intricated, But

Â you have two trajectory that you can guess on the image.

Â So, we start to be more and more complicated.

Â But suddenly it goes back to the initial state.

Â So, let me play it again.

Â You see that the trajectory seems to be chaotic.

Â And at some point you just undo what it was doing, and

Â we go back to the initial state.

Â That would mean that if I kept running the simulation I will get

Â an oscillating system.

Â Okay?

Â So then, if I have an oscillating system,

Â I can definitely prove that with two ants I don't have to go to infinity.

Â I can stay in a finite region.

Â So, I think what's the interesting conclusion we can get from this model.

Â I think, it has some impact on the way you think about science.

Â So, first, it's a system where you know very well the law that govern the system

Â because definitely it has been artificially created by a.

Â So, we basically build this rule according to our convenience.

Â And so, it mean that we know the fundamental law of nature, okay, for

Â this system.

Â But still, it doesn't allow us to predict a detailed aspect of this dynamic.

Â For instance, we are totally unable to predict, theoretically,

Â at what time the first highway will appears.

Â We can observe the system, of course.

Â But we can have no mathematics that tells us when it will happen.

Â So it means that even though you know perfectly well

Â the macroscopic behavior of a system,

Â you may be totally unable to predict the microscopic behavior.

Â The only solution to know what will happen is to observe the system.

Â So for the ant we have just to sit in front of a computer.

Â And to wait until the first highway appears and then we say oh,

Â that's the time at which it happened, okay?

Â So of course it would be a very bad news if it would be exactly the same thing for

Â all systems, think of the weather forecast.

Â So we are very happy to be able to predict the forecast for

Â tomorrow in less time than waiting tomorrow.

Â But if I apply the same situation as for

Â the ant, it would mean that if I wanted to know what's the weather tomorrow,

Â I just have to wait until tomorrow and observe, so.

Â But here you see that some example,

Â some problems, they cannot be computed faster than the observation.

Â It's just too complicated.

Â And that's an example of a dynamical in system where, so far, either we have not

Â been smart enough to be able to predict, or there's no way to predict it still.

Â I would say an open question,

Â yet there's a few thing that we could guess or know about our ant.

Â Is the fact that it has to go to infinity, or

Â that some oscillatory motion is possible.

Â But if you think of how we could get this info,

Â it's only from the symmetry of the rule.

Â So basically, we could find what very fundamental law

Â are associated to this microscopic rules.

Â And from those we can derive some very general results about

Â time irreversibility or the fact that you have to go to infinity.

Â But you don't know the detail, you don't know when.

Â So again, we see that it's often the symmetry, or the conservation law,

Â or some particularity of the rule that can let you do prediction.

Â But maybe you cannot do everything you want.

Â And I'd like just to come back to these examples that I showed you

Â in our first module on cellular automata, and you've seen these patterns.

Â And the question is are those patterns complex?

Â Are they also so complex that we cannot

Â predict what they will be until I'm actually observing them?

Â And in that case the answer is no.

Â Actually, I can find an algorithms which compute faster than the itself.

Â Actually if you run your cellular automata, which is a n by

Â 19:04

It's because observe that if you [COUGH] look at your rule at some

Â specific time namely, when the time interval is a power of 2,

Â you see that you exactly reproduce your initial motif with some translation.

Â So, this parity rule does only one thing at power of 2 iteration time.

Â You take the initial configuration, you move it left,

Â right, down and up by a given amount.

Â And then you do a superposition with your previous image.

Â So that's why when you have exactly a power of 2 number of iteration,

Â the image is very clear.

Â Now if it's not the power of 2, then you just have to decompose your number of

Â iteration into a sum of power of 2, which is logarithmic operation.

Â And then you can just sum up everything and you know exactly the result.

Â So, that's an example where you don't have to wait for

Â the simulation to finish to know what's the result.

Â You have mathematics that allows you to go faster.

Â And of course, that's nice if we want to do prediction.

Â