Langton’s Ant – Numberphile

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.

100 thoughts on “Langton’s Ant – Numberphile”

  1. 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.

  2. It gets even more interesting 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.

  3. 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

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

  5. 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?

  6. Find the difference😈😈😈😈😈😈😈😈😈😈😈😈😈😈😣😈😈😈😈😈😈😈😈😈😈😈😈😈😈😈😈😈😈😈😈😈😈😈😈😈😈😈😈😈

  7. 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

  8. 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.

  9. 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.

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

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

  12. 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.

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

  14. 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?

  15. 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?

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

  17. 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?

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

  19. 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.

  20. 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.

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

  22. 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

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

  24. 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.

  25. 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…

  26. 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.)

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

  28. 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

  29. 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

  30. 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?

  31. 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.

Leave a Reply

Your email address will not be published. Required fields are marked *