YouTube Deep Summary

Ants. I love ants. And I, like many people that watch this channel, am probably a little bit awesome, and I love watching videos of ant simulations. This video is about my own ant simulator, but secretly, it's a video about touring machines. My simulator is a free website that you can go play with right now. It was programmed with AI. I have a full video on how it was made. If you haven't seen it, then I command that you go watch it. But the actual algorithm here was invented by a human named Chris Lton, an artificial life researcher that created some of the coolest things I've ever seen and then dropped from the field in the '9s. I hope you're doing well, Chris. You made some cool stuff. This is Lon's ant. No, not LinkedIn's aunt. That's a very different thing. Here's how it works. The ant lives on a grid of black and white cells. It moves around on that grid, changing cell colors as it goes, like it's leaving pheromone trails. It has a current direction and depending on the color of the cell it's currently on, it decides whether to turn left or right and how to change the color of the cell. The rules for Len's ant are if it's white, change it to black and turn left. If it's black, change it to white and turn right. You can invert those colors or turns however you want and it will do the same thing. Following these simple rules, the ant initially seems to move kind of randomly. Even though this is a fully deterministic program, at some point it makes this almost symmetrical shape, but then continues in a mostly random pattern. Then after 10,000 steps, something remarkable happens. It gets stuck in a loop and builds this structure out infinitely. This is called a highway, and it is a classically emergent structure. In my simulator, the grid borders wrap around, so it will eventually collide with itself. It is an odd and unexpected thing that such simple rules produce such a mix of chaos and order. But the reason I made this simulator is because I wanted to see what other weird things I can get these ants to do. Indeed, with real ants, things get much more interesting when you have lots of them. So, what happens if we start with two of Lankton's ants right next to each other, both facing to the right? Almost immediately, they start to kind of work together, building a border that extends outward forever. Very unexpected. Even more interesting, when they eventually wrap around the edges of the grid and collide, they can start backtracking and deconstruct everything they've built. A weird property of LinkedIn's ants is that they can sometimes do this perfect backtracking deconstruction. When they meet again in the middle, they start over, and they will do this forever. Even weirder, this border building behavior happens with any even number of ants all in a row facing the same direction of the row. [Music] It doesn't work for odd numbers of ants, though. Why? Beats me. It just is bizarre behavior. Two ants in a row facing up rather than to the side get stuck in an infinite dance. Four of them arranged in a square, all facing the same direction, make a little traveling party that moves endlessly in one direction without leaving a trace. Most other configurations just end up making a mess. That will be a common theme here. But there is still unexpected order here. Remember that these are all just following that same stupidly simple rule as before. Yet, you cannot foresee what they will do until you let them do it. We can come up with far more complex behaviors by introducing different cell colors, different movement types, and different logic. You can use these rule string things to encode ant behavior. They work pretty well, but they cannot encode all possible behaviors. So, I just skipped ahead to make a universal rule set using state machines. I didn't invent these obviously, but I've set up my own syntax with a lot of AI help. The ant's brain is a state machine or a finite state automaton which is a way of programming arbitrary logic. You can think of the state as the ant's state of mind or its current mode. Its action now depends on both the color of the current cell and the state it is currently in. All of which decides how to move, what color to write, and what internal state to change to next. So, it won't always do the same thing when it's on the same color because it can be in a different state of mind. Here is some state machine logic written as a JSON object. It has two states and can read and write two colors, black and white, just like before. Each state has its own set of actions for each color. We always start in state zero, the first one, and we read black, which is color zero. So, for state zero, color zero. This is the action. right color one white move right and change to state one we are now in state one the second one so we now follow these rules we read black again so state one color zero write black move right and go back to state zero and I think you get the idea this is what happens when you run this logic over and over and over I have also defined the special state negative one to be the halted state where it will permanently stop the state machine is effectively a program and the grid acts as the memory that the program is reading and writing to by definition. That makes these ants turing machines only with a two-dimensional grid memory rather than the classical one-dimensional tape. We call them termites spelled with a u in reference to turing machines and Greg Turk, one of the guys who originally invented this paradigm. Termites are universal with enough states and enough memory. They can compute any computable program. They are a visualization of computer programs in execution. When they repeat behaviors like this, they're performing a loop or recursion. Multiple ants are the equivalent of multi-threading with many programs sharing the same memory. As you add more states and more colors, you explode the number of possible state color combinations. I've artificially limited the number of colors to 12. There's only so many distinct colors, but you can randomize with up to 1,000 states. I've also added lots of different kinds of movement. L for left, R for right, U for Uturn, go the opposite of the current direction, and N for no turn. Just move straight in the current direction. These are all relative moves. They depend on the ant's direction. But you can also use absolute moves. North, south, east, and west denoted with arrow characters. These do not care about the ants direction. Finally, there is S for stay, don't move at all, and question mark for random, which selects a random absolute move. The randomize button will randomly mix and match these movements, colors, and states to create some very complex ant behaviors. Typically, they're not that interesting. Most will just fill up the grid with noise. But if you just keep randomizing, you can find some really interesting ones or manually craft them yourself. You can save the rule to a file and load it up later or share it on my Discord. I'll make a channel for it. Yes, they can occasionally make some, let's say, politically charged symbols, which I am not interested in seeing on my Discord server. I've saved a bunch of cool ones in the presets drop down here. So, let's take a look. I call this one the constructor. It just makes a neat spiral pattern and then it keeps building around in a seemingly organized, deliberate way for a while at least. I found it by just randomizing over and over and over. That's how I spend my free time. But the others, like this Archimedes spiral, were discovered by other people and published online. I just stole the rule. It was extremely useful to use AI to reconstruct these. It's actually kind of the perfect AI task. It's also a good sanity check that the program is written correctly, that the rules are being applied properly. If they weren't, these patterns would not just be slightly wrong, they would be completely wrong. They wouldn't work at all. Now, while it was a lot of fun to make this simulator with AI, I do sort of feel robbed of the experience of making it myself, of figuring out the algorithm and crafting the rules. I don't understand it as well as I would have if I had made it all myself. Also, you may have noticed there are little lingering bugs in this program, especially visual artifacts that have been very difficult to iron out with AI programming. On the other hand, I probably would never have made this at all without AI. It's a give and take, I guess. Some ants make symmetrical patterns like this one, which is extremely rare since the ant must build each symmetrical side independently. There is no natural guarantee of symmetry, and even this is only occasionally symmetrical. Now, here's an interesting question. This ant makes a structure that looks like it's bounded to this small area. It never grows beyond a certain limit. But is it actually bounded forever? It certainly looks like it, but maybe after a billion billion billion steps, it starts building a highway like Lton's ant, or it just continues inching its way outwards. As far as I can tell, we don't know the answer to this. Despite their simplicity, it is extremely hard to tell what these ants will do. An especially beautiful one, maybe my favorite, is this snowflake, which is also symmetrical almost. It's just a bit off. You can see that here in the center. Regardless, it's incredible that such a thing is possible by building one cell at a time. Given that these are universal touring machines, I think it should be possible to build a perfectly symmetrical snowflake. But no such rule has been found. In fact, I think it should be possible to build any given image like say a smiley face. This was a fully AI generated rule. Is it not super cute? It actually isn't that hard to write a rule that can make a given image. It just needs to go cell by cell, row by row, and lay down the right color for each pixel of the target image. I'm pretty sure that would work. Now, to prove that these ants really are touring machines, we can build some simple touring machine programs by simply restricting the ants movement to east and west, side to side. We also restrict the colors to black and white, one and zero. This simulates the one-dimensional memory tape that touring machines read and write from. Theoretically, the tape should be infinite, which it's not in this simulator, but you get the idea. With these ants, we can reconstruct the so-called busy beaver programs. These are a bit abstract, so bear with me here, but intuitively, a busy beaver is the most complex touring machine that you can build with a fixed number of states that will eventually halt. Of all the programs that don't run forever, Busy Beavers run the longest. So, take Busy Beaver 3. Its state machine has only three states and it runs longer than any other three-state program before eventually halting. There are plenty of three-state programs that run forever, but they don't count. A Busy Beaver must eventually halt. Busy Beaver 4 looks like this. It has four states and runs for 107 steps. And here is the recently discovered Busy Beaver 5. It runs for 47,176,870 steps before halting. It's actually so complex that it cannot run properly here. It's too big and it overlaps with itself. Busy Beaver 6 is unknown and probably will be forever. The search space becomes enormous and the candidate programs run for far far far too long. Maybe I'll make a video on busy beavers in the future. I definitely want to make something about Turing completeness. expect that in the year 2079. And to close out, you can make it so there are many ants, each with their own individual random rules. Since they can use different colors, if an ant encounters a color that is not explicitly defined in its rule set, it will treat it as color zero, black. Now, I don't know about you, but this is starting to look very biological to me, like an ecosystem. I think there is an evolution simulation waiting to be built here. something like if an ant produces enough of a certain color, it will reproduce itself and mutate its offspring's rules. I think that might be too simple and probably lead to huge overpopulation. So, there needs to be a way of callulling their numbers. I'll play around with it and maybe with AI help, I can build something like that within the century. But that's it for now. If you make anything cool with this simulation, please post it on my Discord. And thanks to my patrons for making this possible. I'll leave you with some cool footage. Thanks for watching and I'll see you later. [Music] [Music] [Music]