Here's a squad of robots armed with confetti guns
We just gave the first robot the order to fire.
It should now communicate the order to the rest of the squad, and they should all fire
at the same time, . . . But we have some constraints that make this
simple task difficult.
The robots can only communicate via body language.
Each robot can only see its two neighbors.
We need to define some finite set of poses, which we'll call 'states'.
To communicate, the robots are only allowed to use the states from our chosen set.
The first state is the initial 'idle' state, And the last is the final firing state.
The robots change their state on the beat.
And they change states according to very simple transition rules.
They have no memory of recent events, so they can only take decisions based on their present
state, and that of their neighbors.
Here's an example rule: If you are idle, the left neighbor is in the 'kick' state, and
the right neighbor is idle, switch to the 'kick' state.
All the robots follow the same rules.
Except the robots at the edges.
They are missing one neighbor, so they have their own rules.
Initially, all the robots are idle.
The transition rules must state that idle robots with idle neighbors remain idle.
A hit on the head switches the first robot to the first non-idle state . . .
And now the rest of our rules kick in, setting off a chain reaction.
Our goal is to find a finite set of states and a set of transition rules such that hitting
the first robot on the head will eventually cause all the robots to reach the firing state
on the same beat.
And . . . the same set of states and rules should work for squads of any finite size.
If you want to think about it, check first some notes in the description, and pause now.
Our solution has two main parts.
Let's explain first one of them.
The first robot is now in a state which we'll call: 'a general'.
The general issues a hand signal, which will propagate to the right.
When it reaches the end, the last robot reflects it back.
Now the solution in full.
The general will emit two signals: a hand signal and a leg signal, . . .
But the leg signal has three steps.
Only now the next robot will pick it up.
The two signals collide exactly in the middle.
The two robots that witness the collision will become generals themselves, . . .
Each to its own side of the row.
We effectively split the row in two.
Everything we just saw will now repeat itself on a smaller scale, and the two parts will
mirror each other.
And we've split our row again.
Now all the robots are generals.
And they all see their neighbors are generals too.
This is the fire signal.
Before we continue, let's replay a part of the last run.
In this step the row is already split to sub-squads of 2 robots each: a general and a solider.
Let's focus on this sub-squad, . . . and play another beat.
The hand signal has reached the end of this sub-squad, and according to our protocol,
the last robot should now reflect it back.
However, it doesn't know it's the last robot of a sub-squad: It sees neighbors on both
sides.
But recall these separator lines act as mirrors.
If there's a hand signal going right, there's another hand signal going left, coming from
the other side.
On the beat, they'll swap, . . . which is the same as reflecting both of them.
The last two beats are straightforward.
Now let's try an odd number of robots.
The two signals collide in a slightly different way: The leg signal is only in its first step.
This tells the robots that their number is odd, and they respond accordingly.
Only one robot became general, and it emits both signals to both sides.
We effectively split the squad into two sub-squads of 4 robots each, with the middle robot belonging
to both sub-squads.
It will use special states allowing it to play a double role.
Let's show the two robots its current state represents, . . . and continue . . .As before,
we continue to split the row into smaller sub-squads.
But note the middle robot again.
It sees two hand signals coming in, and it's going to use some more special states.
It raised both hands, but this time it also turned around.
This represents two robots that are raising their inner hands, meaning two hand signals
coming in.
On the next beat they'll swap.
Now it's emitting the hand signals outwards in both directions.
It so happens it also sees two leg signals coming in from both directions . . . since
this is a signal collision on both sides, it will become a double general again.
Now everybody is a general, and we're done.
Let's try 6 robots.
First we split the squad in two according to the even number rule.
Now each sub-squad of 3 will be split according to the odd number rule.
Now we have 4 sub-squads of two robots each, with two robots playing a double role.And
again, the hand and leg signals collide . . . We'll conclude this video with a few uninterrupted
runs of various sizes.