We're at the kitchen table and we have toothpicks. We put down one toothpick and we notice it has two ends.
So at each end we put a toothpick. The toothpicks are all the same length,
ideally. We started with one and we added two, so now we've got three toothpicks. We notice now
there are four ends. So on each end
we put a toothpick. And these toothpicks actually touch.
So those ends are no longer free. And we keep going, we do this forever.
So the next generation, this is the fourth step. We had four free ends,
we're gonna add four more toothpicks.
Those, those two toothpicks met at the middle, so those ends are no longer free. So now there are, there are four ends.
So we add four more toothpicks.
(Brady: Wow, now we've got more ends)
Now we've got eight free ends, so we add eight toothpicks. And we keep going. And the question is, how many toothpicks
do we have after n generations? Is there a formula?
Well, this is a very lovely question. Let me show you. David Applegate, my
former colleague at Bell Labs, made an animation of this and a number of related sequences.
There we see one toothpick. Next we added two toothpicks. Next,
next, this is where we got to, now we're going to add eight. And now we have 12 free ends,
we're going to add twelve toothpicks.
And so on.
So let's watch it run. We see it growing. When we get to power of two
we notice something special happens. We have essentially a square that's full of toothpicks.
There's no room in the middle to add any more toothpicks.
There's a horizontal line of toothpicks at the top and the bottom, and there are four free ends.
So by the rule, at step 17, we're gonna add four toothpicks. The new toothpicks are always blue.
So we've just added four and now if we keep going, and you can see it growing from the corners.
Now the interesting thing is that the growth from the corners after 16 generations
is the same as the growth from the corners after 32. So let's let it run for a bit and admire it.
So we're coming up to a new power of two, 128 generations,
and again it's growing, and it's growing from the corners.
(Brady: Hypnotic, isn't it?) - It's wonderful, yes. But you can do this on your, on your computer at home and you can see it's growing and
it's
obviously a fractal like structure. The growth from the corners is,
has growth from the corners, the corners grow like earlier corners grew, and it grows and grows and grows.
And the question is how many toothpicks do we have after n generations?
And I'll show you in a minute how we analyse this. But there are others
that we were not able to analyse. So when you look at the seagull, in the sky,
it looks like that. So that's actually a toothpick. It happens to be bent and it's got three ends.
The rule is the same, every free end
you add a toothpick, only this time they're gull-wing toothpicks. Now we've got four wingtips,
so we go there. And there, and there, and let's let it run and watch it,
admire it growing.
This is much more difficult.
We have not analysed this. Here the growth from the corners is different at each power of two. It's still every power of two,
it fills up a square as much as it can,
but the growth from the corners is much less predictable.
(Brady: Who even thought to make a gull toothpick? Like where did that idea-) - Omar. Omar Pol.
Yes.
Isn't that wonderful, let me show you a couple of others before I
show you a little bit of the mathematics of the analysis,
which is actually just as pretty as the picture but a different, a different style.
E-toothpick and see how that looks - run.
Yeah. Yes. This is very
Christmasy, snowflakey. And again, we don't understand this at all. We know how to generate it, but we don't have a formula for
how many E's - E toothpicks there are.
We're going back to normal toothpicks now, so here are ten generations, and you notice that after eight generations
we have a square which is almost full. As full as it can be, there's no room to put a toothpick,
there are no free ends in the square. There are only four free ends.
So after eight generations we add four again, it's just like at the beginning. One, two, three, four, we have eight free ends,
so we add eight and we get there and so on. Now in - if we look at a corner, let's
focus on a corner. So after a power of two what we're left with is a
square with no, no holes in it - it's full up. And
at each of the four corners, there's half a toothpick sticking out.
The first step is, all we can do is add one toothpick there.
And we'd of course add one at the other four corners. Now the next generation, this has two free ends,
so we add two toothpicks.
Okay, now we have three free ends so we add three more toothpicks. I'm now at generation, what is it, one, two, three.
We're gonna be able - we've still got three
free ends. We add one,
two,
three.
And now we have one, two, three, four free ends
so we add four toothpicks, and so on. After, I think this is seven steps,
it looks like that. And if you stare at this
you see that it's really made up of three clumps. The corner sequence,
after whatever it was, seven more steps. And this is true for any power of two,
it's not just, you know there if you go up to 128
steps, we still see the same growth.
256 it still starts the same. It grows more and more because there's more room
when we're out at
256, but the beginning is the same, always. When you look at it
you notice that after a power of two beyond where we were, we have three
clumps. And so pay careful attention to how many there are.
We find there's a formula and I was using L for the number in one of these clumps, and
here we've got three clumps, two clumps which are seventh
generational clumps, and one which is eighth generation and we get a formula.
And when we actually
put all the pieces together
we find that
we can explain the corner toothpicks.
I won't really go into the details, but there's a very nice formula which explains, after we've gone
for a power of two plus i
further steps, where i is one, two, three, four, five and so on,
there's a formula for the number in the corner which depends on K, the power of two, and i.
And it's a very nice recurrence.
Once we've noticed this recurrence, that the number - there's, there's a way of writing down how many
toothpicks there are in the corner, in terms of something we already know,
that's enough. We can, we've now essentially cracked the whole problem.
We know ever- almost everything about it.
We have, we can work out - if you want to know the millionth term we can do it easily.
It solved a problem and we wrote a paper about it,
Omar Pol, David Applegate and myself. So that one we solved in the end.
You might say on the scale of things that was a pretty easy
sequence to analyse Now there are a lot of others which are not so easy, like the seagull
toothpick, and the E
toothpick.
There is another couple of easy ones that I think are worth telling you about,
particularly as they involve one of the famous
scientists from Los Alamos, New Mexico,
Stanislaw Ulam. Let's imagine
we have a large piece of squared paper, and
each square is a cell, and we can say that cell is either alive or dead,
it's on or off. Its 0 or 1.
Maybe it's infected or it's not infected, there's a disease spreading.
We want to know how fast the disease is spreading. Or maybe there's some
chemical reaction which is going on. It starts off with one
cell being active and that activates other cells. We want to know how fast does this grow?
it's, it's, it's understandable that this would be something that physicists and chemists and
scientists and maybe nuclear scientists and mathematicians,
people who are studying epidemics and so on, this is of universal interest this question: how fast does
something spread? A very simple version of this is what's called the Ulam-Warburton
cellular automaton and it works on cells. And it's a machine,
that's why it's called an automaton.
It proceeds on its own and the idea is we have to imagine we have a huge piece of graph paper, with
cells, square cells.
And each one is surrounded by eight others, but actually we'll only look at the four nearest neighbours
of the cell. And we're going to start off
where everything is clean. The pristine board - nothing is on.
Suddenly one of the cells gets turned on,
I'll write a 1 instead of a 0, all the other cells are 0. The rule is, for this particular
automaton, you look at a cell near this. It gets turned on
if exactly one of your neighbours is on. This has one neighbour that's on, so it gets turned on. So that one
turns on those four. Okay, now, let's go on. At the next generation
this cell here has two neighbours that are on, so it does not get turned on.
I'll put a zero, likewise that's a zero and that's a zero.
But this cell here does get turned on because it's got only one neighbour that's on.
This is the Ulam-Warburton cellular automaton. So let's have a look at it.
(Brady: Can things get turned off or once you're on-)
No, they - can inversions of this. Of course Conway's Game of Life,
cells turn on and turn off.
These particular ones only turn on. You're either on or off. And once you're on you stay on.
And there it is. It starts off with one cell on, there it is it's blue because it's a new cell.
Ok, next. It turns on its four neighbours and next it turns on four neighbours again,
it did not turn on that one because the rule is you turn on if exactly one of your neighbours
is on. This one has two neighbours that are on so it stays off, it is not infected. If we let it run,
again, it's gonna grow up. And again, you'll notice that every power of two
it's got a full square and it grows from the corners. And again, we can analyse it in the same way.
And this one is even simpler, there's a simple formula for how many cells are on after n generations.
Now we're doing the same thing, but our graph paper isn't squared graph paper anymore, it's
hexagonal
papers. Like the bathroom floors where you see hexagonal tiles.
This is hexagonal tiles, each cell has six neighbours now.
But the rule is the same, you turn on if one of you-
exactly one of your neighbours is on. So watch. If we let it run it goes like this. Again
it has the same property that after a power of two we have a full hexagon and it grows from the corners, but now
something really
annoying or beautiful has happened. The growth from the corners; we're coming up to another power of two here,
watch it grow from the corners. If you stare at this you can see in here
there's a pattern of black and white cells. At the next power of two we see a different pattern,
it does not repeat. It is very complicated.
And over there I have a very large piece of paper with my attempt to analyse it.
Do you want to see it? - (Brady: Yeah, of course!)
Here
This is my attempt - and it's not finished. I haven't given up but I haven't solved it yet.
This starts down here in the corner,
and then it grows. And it grows and it grows and every, you,
if we look here you can see this is sixteen. So this is where we were after eight,
each power of two, we, we get a closed hexagon. I'm just showing you one
sector, one sixth of the whole pizza.
Just a slice. So after sixteen
the, we have that. After 32, it's like that. And then if life
was simple there would be a predictable pattern,
but there isn't. If you look at these squares, the coloured squares,
the red squares there are not like the red squares that we saw earlier. There are some similarities,
so I haven't given up, but
this is really tricky.
I think this one is doable but some of the others, and there are a lot - as you saw there
there are 100 or more
animations that you can look at it, and some of them are very beautiful. I particularly wanted to show you Fredkin's replicator.
A graduate student at the University of Cambridge
asked me if I could solve it.
And I did. It was on the margin of what, what could be solved and what couldn't but it was. The rule is
it's similar to the Olam-Warburton.
You turn on if the number of neighbours
that's on is odd.
Not one, as it was for Olam-Warburton. If it's two you just - you turn off, but an odd number you turn on.
(Brady: Oh I like that. It's like, nice and arbitrary.)
Yeah, well the pictures are beautiful, look at this. Here's the first 16 generations,
and then when you look at 32 generations
you ask can we break it up into pieces
that look like things we've seen earlier? And the answer is yes, you can but it's a little tricky.
And the reason it's called Fredkin's replicator is if you have some shape,
any shape you like,
say that. Then after a certain number of generations, you see two copies of it. It replicates itself.
That's why.
Fredkin being a famous computer scientist at MIT who
studied many things like this.
[Preview] ...Don't think it was worth all that, I've done lots of other mathematical things. And
so I found the Game of Life was sort of overshadowing much more important things and I did not like it...
We agree on that right? Two in three chance you've chosen a goat.
So this scenario of course should be of more interest to us. It's the more likely scenario.