# Langton’s Ant – Numberphile

We’re talking about Langton’s ant, which is a really interesting kind of conceptual idea that someone’s had. It’s an example of what’s called a “cellular automaton” Hello. Hello tiny dog. Oh, it’s a different person [Brady] Sorry about that interruption. Langton’s Ant is an example of what’s called a “cellular automaton”. So it’s a bit like “Game of Life”. Um… So you’ve got a grid of squares, the squares change colour depending on what’s going on in the thing. In the Game of Life, it’s slightly different because the whole thing has a set of rules, and everything changes at the same time. But in Langton’s Ant there is a specific, there’s an ant that lives on the grid, and it walks from square to square, and as it moves, it changes what the squares are doing. It’s an example of something which has a very simple rule, but ends up being really, really complex. So this is a grid, a grid of squares, and I guess– [Brady] Show me how you made it. Show us, give us all your secrets. Uh, okey. Well I got a paper bag, and cut one side of it, and then I printed it on to that, and it didn’t break my printer, which I was very happy about, and then I’ve laminated that so I can rub off. There’s the handles of the paper bag. It’s simple rules. Basically so you start off with a completely blank grid, that looks nothing like an ant. I’ll give it another couple of legs. There we go. So essentially what he does, every turn, is he either turns left 90° or turns right 90°, steps forward, and changes the color of the square as he leaves. What he does depends on what color the square he’s on is. So if he starts off on a white square, He will turn 90° to the right, and step forward, so now he’ll be over here, and as he leaves that square, he will change it from white to black. So that’s now a black square. Now he’s on a white square, so he will turn right again. And he’ll end up on this square facing this way, and he’ll change that square to black as well. And then he’ll keep doing that, so he’ll move, turn right from there, and then end up here facing that way. And we’ll change this one to black. And this is where it starts getting interesting because now he turns right and goes back on to that first square again. So he’s now on there, facing that way, and you can’t quite see him. If he’s on a black square, it’ll turn left. So he’ll now come off this way, and go this way, and as he leaves that square, he changes it from black back to white again. So, essentially, you can keep moving like this, as long as you like, and just continue changing what happens on the board. And if you start with a completely blank square, it’s kind of interesting, so he will start off by making quite simple patterns, and, kind of, things that look a bit symmetrical sometimes, But all, kind of, fairly simple, fairly self-contained. [♫] After a few hundred steps, he starts to just become more chaotic, and eventually what he’s doing looks completely random, and you’re thinking “Is this just going to carry on like this forever?” [♫] And when he get’s to, it’s something like 10000 steps, it’s a number just a bit more than 10000, he suddenly becomes completely regular. So he will start doing, like a column of a diagonal column of things that moves offwards. [♫] It’s like 104-step cycle that repeats and just continues moving diagonally off to a corner. He will carry on to infinity doing that. [♫] And it’s what’s called an attractor. So this diagonal column that he does is something that he will always end up doing. They tried loads of different initial states, loads of setting up the board to start with. He always ends up, eventually, getting to this weird diagonal column thing, and just carries on doing that forever. And I just love that. That’s it’s a thing that he’s drawn to do. [♫] You can start with any grid you want, so you can almost program it like a computer because you know that it will do, you know, whatever it was going to do, given the particular starting configuration. And, I think it was about 2000, someone actually discovered that you can use this to run any computer program. So you can build, kind of, computer logic gates, and that kind of thing within this system. And it is a Universal Turing Machine.

Okay, seems like you could find out the reason for this. Find the sequence that the ant starts this on, and work backwards to figure out how that could be made.

It seems logical that eventually it would hit this sequence, as there are 104 possible combinations to start it, but finding out how those combinations are made may help to prove why the ant always arrives at the highway.

Also, get some of those people who did some awesome stuff in Game of Life, and see if they can find an alternative repetition sequence. This may be the only one under those rules. If that's true, then in an infinite system without a repeating pattern, the ant will, given enough time, create every layout of however many squares possible. If one of those is in the 104 step highway system, obviously the ant will be locked into place.

I love conway's game of life so much I started an instagram account and named it after the game.

2 ants on one grid?

It gets even

moreinteresting if you make the left and right edges connect, and the top and bottom (topological torus). Eventually the ant fills the grid with alternating diagonal stripes, 2 pixels thick.Great!! Awesome!! Wonderful!! THANK YOU!!

I can't concentrate. Audrey made my mind melt from cuteness.

Now that's a nice drawing of an ant.

Nice video btw.

I just followed the 104 step video and noticed if you start with just 15 dark squares the ant will just do the highway: Let Grid Coordinates 0,0 be where the ant starts with it white with ant facing up. start with the following cells darkened (first number column negative=left of origin positive=right, second number=row negative=above, positive=below) -2,1;-2,0;1,0;-2,-1;1,-1;-3,-2;-2,-2;-1,-2;1,-2;-3,-3;0,-3;1,-3;2,-3;-2,-4;-1,-4

As user of the Abo-Base-System of the Video-Marketiing-Mssterplan I`m happy to subwscribe your channel. Greetings! Great Video!

You should get some of the computerfiles to program your ants next time

The highway to hell

You should be able to arrange the board in a way so that the ant at start begins to travel the Highway. It just takes time for the ant itself to arrange. Am I right or am I wrong?

Its not an ant, its qbert

british Sarah Vowell

I now understand how proteins and timing works… I think.

we need more casual comments about the dog. He just wanted to learn about Langston's ant too.

was there something like this to try to find randomness

But WHY? does it always end up this way

Find the differenceπππππππππππππππ£πππππππππππππππππππππππππππππ

The ant has found the purpose of life: The Highway!

it WS beautiful

Please do a video on Monte Carlo simulation!!!!

If someone has code for this give it to me please.

Is it me or the game dust has this ant and vine ??

I was playing with golly a couple of months ago and found that if you have many ants, they don't necessarily go off on a big crazy trip like that, you can get pure cycles

That reminds me a lot of the Syracuse sequence. Very cool.

what? i don't beleive it

…and from the chaos the order rose

I actually found this fascinating enough that I went into excel and wrote a program that does exactly the same thing (for practice in part). Put in the number of steps and watch it go.

Are there any other stable things this ant can do?

And there a nuber of instances where in small numbers of iterations, there's no recognisable pattern. But in large, they apprear. That's interesting.

Possible to enumerate all attractors given the properties of the automata?

omg he actually made all of that simulation by hand

i thought he wrote a simulation

Things can really get interesting when you bring in two ants with certain starting configurations.

0:08 – Attack of the Killer Audrey was the best part of this video. "Hello, tiny dog! 'It's a different person!' "

I need a dinosaur playing asteroids t-shirt

hello tiny dogCan you prove it always does this cycle?

I have devised a 4-ant starting configuration that always goes orthogonally. Can you figure it out?

What if there are more then 2 colers?

3n+1 and langton's ant…

Why???

3:55? You can do stuff like this in Photoshop? Wow who knew…

wait, how can it both always terminate (reach the cyclic execution state) AND be a universal turing machine?

I've tried making a Langton's ant in python, I feel like 32 lines is pretty bloated for such a simple turing machine. if anyone would be willing to give some advice to a noob, PM me and i'll link you to the GitHub.

WAIT A SECOND HALFWAY THROUGH THIS I REALIZED THAT IN POWDERGAME FROM DANBALL THERE'S AN ANT MATERIAL THAT SEEMS LIKE IT DOES THIS

i died at the dog part XD

I wonder if I could get my app translated into an ant program?

Not that it would be useful, just fun.

FFS drop the music. It is annoying.

Was that a teacup chihuahua? I have one that acts exactly like that.

Do you suppose that the "attractor" is like a repeating decimal?

I feel like the patterns that the ant is making could be described as a specific number, with a given rule set having a specific mathematical formula. I'm no mathematician, so maybe someone who's more knowledgeable would have some insight on this?

wouldn't you always get a highway, regardless of what rules the ant is following? I mean, it seams inevitable for the ant to start looping if it keeps moving by the same rules. Those 100k steps before the ant loops, isn't that basically the ants setup as to create conditions that will result in the loop?

Incredible

Audrey!!!!!!

SO I gave an attempt to make Langton's Ant. Took 5 minutes.

I love programming

… So this ant exhibits the same behaviour as a high-school student given a marker pen – eventually, both will mark out crudely phallic shapes.

Did the guys at numberphile really did the whole thing manually?

Too bad the most interesting part (universal turing machine) was at the end.

Oddly peaceful.

What if you start him with the highway? Will he simply keep doing what's there, or will he go about random patterns before commencing into infinity?

is this diagonal pattern, in any sense, linked to what happens in the generation of pseudo-random numbers or cryptography?

have they tried calculating when and where the ant will end up on the highway and changing the color of one of those squares beforehand? it seems like that would break up the construction process and send the ant off course.

Was anyone aware of this before computers were around – I mean had anyone mapped this to 10,000+ moves?

ie it's a Turing machine.

is the highway really the only repeating thing? in the game of life there are hundreds which each can be slightly changed to do that same thing but are considered different.

When i heard the piano, i initialy thought it was playing the ant's notes that inevitably would turn into black midi.

Compass

what will happen if we added 2 ants

I found a simulation where the ant makes a massive square, it doesn't make a road out, instead starts infinitely expanding the square.

Here it is:

Start facing down

LRRRLLLR

and the after an infinite amount of time on the highway the ant econter an other ant and become best friend

I wrote a Langton's Ant screensaver back in the 90's, it was a big hit with the geeks in the office.

I can't help but wonder if the pi's digits could be a result of a similar procedure!

thats so coool

I think I really need to know how this can be a universal Turing machine. I'm gonna go find out as much as I can.

So is the highway actually a halt state? Like, it finishes its calculations and just stops? Like a Turing machine would?

Never really appreciated it before, but the music played during the ant sequences is beautiful!

The highway reminds me of 4 having four letters, and how all numbers when counting the number of letters they had and repeating, would eventually lead to 4.

I wanna make this program, but how do I make it walk randomly?

Warning, edgey faze

And now I will remember Audrey every time I see an ant.

Excellent background music…!

Catiorro

Reminds me of the Collatz conjecture

We are all ants. Born out of a random family, growing out of a random neighborhood, graduating out of a random school, we all become who we really are, doing the same things over and over again…

Reminds me a bit of the 3n + 1 (or Collatz) problem in number theory, where the iterative sequence also seems to run into the same cycle, regardless of which starting number you choose. (To actually prove that is still an open problem, by the way.)

Jeez i look at langtons ant for the first time today and now there are liek 50 reccomended videos about it

why is youtube suggesting 18472647292 videos about langton's ant

i mean i love game of life and this channel dont get me wrong

but like 13 langton's ant video

3:14 normally called a "highway"

can two ants langton ant?

Is the highway the only attractor? Or are there multiple self-sustaining highways?

now introducing, the 3D langton's ant: the tiles can now have 6 colors. on red, yellow, green, cyan, blue and purple, the ant turns clockwise, looking from above, east, north, below, west and south respectively. at the start, everything is red

superb music β€οΈ i imagined the ant screaming MAMA IM BREAKING FREE

0:15 do not apologize i love that dog it is so cute

Ah the ant started it's infinite highway… cue the uplifting music!!!

Issue with random generator?

what happend if there will be 4 ants and each of htem will be in his center of potential square on pattern that they have together?

Yellow nails ?!?

The seemingly correct way of pronouncing automaton bothers me

did any one notice it was making map of Jammu and Kashmir of india

I made a video of Langton's ants "fighting" each other, it's on my channel if anyone's interested

I disagree that the highway is an attractor. It just happens to be a set that perpetuates. There is no "move towards" this point. Many patterns emerge our of the many different ant rulesets.