5 ms·

Langton’s ant

102 points by scapecast 3y ago

tectec 3y ago
Wow, that brings me back. My older brother wrote a Langton's ant program in QBasic, and one of my earliest computer memories was watching that thing go.
gkbrk 3y ago
Langton's ant is really cool, especially considering the extremely simple rules. - At a white square, turn 90 degrees clockwise, flip the color of the square, move forward one unit. - At a black square, turn 90 degrees counter-clockwise, flip the color of the square, move forward one unit. If you look at the images and animations, you might think that it becomes repetitive quickly, and nothing interesting happens. But that is only if you have an infinite grid. If you have a grid that wraps to the opposite side on the edges, it interacts with its own path a lot more. This produces very chaotic and "random" results. In fact, I've made a toy PRNG based on Langton's ant, and it does quite well on PractRand. It's not a performance king, far from it, but still really cool that two simple rules can do that. It would be a fun project to make a (probably very slow) cipher based on Langton's ant.
qubex 3y ago
There’s a good discussion of this in one of my favourite books: William Gary Flake’s The Computational Beauty of Nature (1998).
mg 3y ago
I always considered Rule 110 the simplest system (code complexity wise) that is turing complete: https://en.wikipedia.org/wiki/Rule_110 https://en.wikipedia.org/wiki/Rule_110 I wonder if the Langton's ant algorithm (say in Javascript) is shorter. My gut feeling is that it's about the same size. But maybe Langton's ant is shorter because it only needs a single loop. In pseudo-code it is super simple: 10 INVERT(X,Y) 20 IF GETCOL(X,Y): TURNLEFT() 30 ELSE : TURNRIGHT() 40 STEPFORWARD() 50 GOTO 10 But an actual implementation would be quite a few more lines.
- chriswarbo 3y ago
  > I always considered Rule 110 the simplest system (code complexity wise) that is turing complete It can get a bit subjective, when trying to compare really simple systems. > an actual implementation would be quite a few more lines The simplest Turing-complete system to implement that I've come across is FlipJump ( https://esolangs.org/wiki/FlipJump https://esolangs.org/wiki/FlipJump ). The easiest Turing-complete system I've implemented is BitBitJump, which is older than FlipJump and slightly more complex ( https://esolangs.org/wiki/BitBitJump https://esolangs.org/wiki/BitBitJump ). I used it as a simple way to enumerate the output of all programs: implementation at http://www.chriswarbo.net/js/optimisation/levin_bbj.js http://www.chriswarbo.net/js/optimisation/levin_bbj.js and visualisation/explanation here http://www.chriswarbo.net/projects/optimisation/levin.html http://www.chriswarbo.net/projects/optimisation/levin.html (Technically these aren't Turing-complete, in the same way that C isn't Turing complete: the amount of memory they can reference is bounded by their word size. This can be fixed by allowing I/O to external storage. My program enumeration loops through all word sizes ;) )
rhdunn 3y ago
There are some interesting patterns/behaviours with Langton's ants. In a wrap around world (e.g. moving off the left/right will enter the other side), the ant will collide with its "hive" (starting blob) or "highway" (diagonal pattern) and repeat a hive-highway construction cycle. With two ants, depending on their starting position, they will end up in one of 3 patterns: 1. A hive-highway pattern like one ant; 2. As 1, but will collide with each other, then undo their construction until they go back to the beginning and then repeat this pattern; 3. Race around each other in an expanding diamond pattern. If the world is a wrap around world, when they reach one edge, they will start to undo/shrink the diamond, generating an expanding-collapsing diamond pattern. It's also interesting playing around with more colours/states, and different rules (180deg turn, no turn). With these generalized turmites, I've seen them create/use "super highway" constructs. -- A "super highway" is a straight line of a single colour where a turmite's behviour for that colour is to not turn. -- It will then race forward along that highway.
SeanAnderson 3y ago
This is so cool! Does the term "ant" here have any real-world implications to the behavior of ants, or is it simply a creative term? Obviously ants are known to build highways, but that's through use of pheromone trails rather than a very simple process of turning, right? But I guess the black/white configuration is a binary representation of a pheromone trail? So, maybe?
chkas 3y ago
https://easylang.dev/ide/#run=len%20f%5B%5D%20100%20*%20100%0Afunc%20show%20.%20.%0A%20%20%20clear%0A%20%20%20for%20i%20to%20len%20f%5B%5D%0A%20%20%20%20%20%20if%20f%5Bi%5D%20%3D%201%0A%20%20%20%20%20%20%20%20%20x%20%3D%20(i%20-%201)%20mod%20100%0A%20%20%20%20%20%20%20%20%20y%20%3D%20(i%20-%201)%20div%20100%0A%20%20%20%20%20%20%20%20%20move%20x%20y%0A%20%20%20%20%20%20%20%20%20rect%201%201%0A%20%20%20%20%20%20.%0A%20%20%20.%0A.%0Aind%20%3D%20100%20*%2060%20%2B%2050%0Adir%20%3D%203%0Adir%5B%5D%20%3D%20%5B%201%20100%20-1%20-100%20%5D%0Afor%20cnt%20to%2012000%0A%20%20%20f%5Bind%5D%20%3D%201%20-%20f%5Bind%5D%0A%20%20%20dir%20%3D%20(dir%20%2B%202%20*%20f%5Bind%5D)%20mod%204%20%2B%201%0A%20%20%20ind%20%2B%3D%20dir%5Bdir%5D%0A%20%20%20call%20show%0A%20%20%20sleep%200.005%0A.%0A https://easylang.dev/ide/#run=len%20f%5B%5D%20100%20*%20100%...
- tromp 3y ago
  I like the result after just the first 52 steps: https://easylang.dev/ide/#run=len%20f%5B%5D%20100%20*%20100%0Afunc%20show%20.%20.%0A%20%20%20clear%0A%20%20%20for%20i%20to%20len%20f%5B%5D%0A%20%20%20%20%20%20if%20f%5Bi%5D%20%3D%201%0A%20%20%20%20%20%20%20%20%20x%20%3D%20(i%20-%201)%20mod%20100%0A%20%20%20%20%20%20%20%20%20y%20%3D%20(i%20-%201)%20div%20100%0A%20%20%20%20%20%20%20%20%20move%20x%20y%0A%20%20%20%20%20%20%20%20%20rect%201%201%0A%20%20%20%20%20%20.%0A%20%20%20.%0A.%0Aind%20%3D%20100%20*%2060%20%2B%2050%0Adir%20%3D%203%0Adir%5B%5D%20%3D%20%5B%201%20100%20-1%20-100%20%5D%0Afor%20cnt%20to%2052%0A%20%20%20f%5Bind%5D%20%3D%201%20-%20f%5Bind%5D%0A%20%20%20dir%20%3D%20(dir%20%2B%202%20*%20f%5Bind%5D)%20mod%204%20%2B%201%0A%20%20%20ind%20%2B%3D%20dir%5Bdir%5D%0A%20%20%20call%20show%0A%20%20%20sleep%200.02%0A.%0A https://easylang.dev/ide/#run=len%20f%5B%5D%20100%20*%20100%...
ChintanGhate 3y ago
Here's my implementation from 2014 that let's you spawn more ants on the grid. http://code-art.chintanghate.me/LangtonsAnt.html http://code-art.chintanghate.me/LangtonsAnt.html
javier_e06 3y ago
There must be a minecraft version of this critter somewhere.
StrictDabbler 3y ago
I used to play around with Langton's Ant a lot. The longer patterns remind me of the climbable game assets in "Below the Root" and "The Jungle Book", early games by Dale Disharoon/DeSharone that I played on an Apple II compatible, though they were available on DOS and C64 as well. I'd always assumed that Dale based his vines on Langton's Ant but the timeline doesn't add up. Dale's games came out several years earlier. It is an interesting aesthetic subset of digital noise. Worth noting that Dale also worked on the strange Legend of Zelda CDi games. He had an unusual arc. https://www.uvlist.net/game-173637-Below+the+Root https://www.uvlist.net/game-173637-Below+the+Root http://blog.hardcoregaming101.net/2012/09/dale-desharone-unspoken-legend.html http://blog.hardcoregaming101.net/2012/09/dale-desharone-uns...
elevaet 3y ago
I prefer Langton's Phage
mitchellpkt 3y ago
I keep wondering about the dynamics of Langton's ant within an infinite adversarial environment. The game I have in mind retains the standard behavior and movement patterns of Langton's ant. However, it introduces an adversarial component: upon the ant's first encounter with any given tile, an adversary determines the initial color of the tile, either black or white. The adversary's influence is constrained to this initial tile color determination, without any additional intervention capabilities. The adversarial objective is twofold: primary is the prevention of 'highway' construction by the ant, and secondary, if the primary objective cannot be fully achieved, is to disrupt the 'highways' as swiftly as possible post-formation. I do not have a good intuition for who has the upper hand here. The adversary can be deliberate, but its influence is strictly limited to controlling initial conditions of the board. Maybe this falls under the Cohen-Kong Theorem, or a potential extension of it. I'm not sure whether that applies here since the adversary may provide a board with finite support or may choose to instead provide a board (or board-generating procedure) with infinite support.
- mcphage 3y ago
  Basically, does the ant have a finite loop? I would be surprised if there wasn't one.
  - mitchellpkt 3y ago
    No idea. Hmm, off the cuff maybe I’d conjecture that there cannot exist any initial configurations such that the ant gets stuck in a loop of finite length for infinite iterations. On any Nth iteration, the ant has only touched <= N tiles. Suppose we do a thought experiment where we create a second board that is empty except for the initial states of the touched tiles up to the Nth step. This second board has finite support, and so the usual theorems kick in, and consequently the ant will eventually start building a highway that would carry it away from the initial loop. I’m just making up guesses though, I have no clue if that is right.
- NackerHughes 3y ago
  Since the movement of Langton's Ant is entirely deterministic, it would be possible in this scenario to make the Ant go wherever the adversary pleases. The initial settings of the pixels can be carefully engineered to facilitate any arbitrary pattern of motion. The ant's movement can be easily calculated ahead of time to help with getting the initial pixel colours right.
dang 3y ago
Related: Langton's Ant - https://news.ycombinator.com/item?id=20123626 https://news.ycombinator.com/item?id=20123626 - June 2019 (25 comments) Hexagonal Langton's Ant 2 – Colors, Gliders and Highways - https://news.ycombinator.com/item?id=10324517 https://news.ycombinator.com/item?id=10324517 - Oct 2015 (13 comments) Langton's ant - https://news.ycombinator.com/item?id=8265482 https://news.ycombinator.com/item?id=8265482 - Sept 2014 (42 comments) Langton's ant - https://news.ycombinator.com/item?id=2230459 https://news.ycombinator.com/item?id=2230459 - Feb 2011 (20 comments)
lproven 3y ago
Nice. I implemented this in Sinclair BASIC on my ZX Spectrum about 35 years ago. :-) On checking, I see it was brand new stuff at the time!
YeGoblynQueenne 3y ago
Hah. That's a good memory. An implementation (simulation?) of Langton's Ant was the first program I wrote when I was learning COBOL for my mainframe job at >BIG FIN CORP< back in 2014. See, COBOL doesn't have a console, and there weren't any graphical capabilities to speak off on the system I worked on, so I just "animated" the simulation by producing multiple static screens. But it worked. I seem to have lost the source though, when I moved from that job.
TRiG_Ireland 3y ago
I was introduced to Langton's ant by the Science of Discworld books, which used it as an example of emergent phenomena.

102 points by scapecast 3y ago

Wow, that brings me back. My older brother wrote a Langton's ant program in QBasic, and one of my earliest computer memories was watching that thing go.

gkbrk 3y ago

Langton's ant is really cool, especially considering the extremely simple rules. - At a white square, turn 90 degrees clockwise, flip the color of the square, move forward one unit. - At a black square, turn 90 degrees counter-clockwise, flip the color of the square, move forward one unit. If you look at the images and animations, you might think that it becomes repetitive quickly, and nothing interesting happens. But that is only if you have an infinite grid. If you have a grid that wraps to the opposite side on the edges, it interacts with its own path a lot more. This produces very chaotic and "random" results. In fact, I've made a toy PRNG based on Langton's ant, and it does quite well on PractRand. It's not a performance king, far from it, but still really cool that two simple rules can do that. It would be a fun project to make a (probably very slow) cipher based on Langton's ant.

qubex 3y ago

There’s a good discussion of this in one of my favourite books: William Gary Flake’s The Computational Beauty of Nature (1998).

mg 3y ago

I always considered Rule 110 the simplest system (code complexity wise) that is turing complete: https://en.wikipedia.org/wiki/Rule_110 https://en.wikipedia.org/wiki/Rule_110 I wonder if the Langton's ant algorithm (say in Javascript) is shorter. My gut feeling is that it's about the same size. But maybe Langton's ant is shorter because it only needs a single loop. In pseudo-code it is super simple: 10 INVERT(X,Y) 20 IF GETCOL(X,Y): TURNLEFT() 30 ELSE : TURNRIGHT() 40 STEPFORWARD() 50 GOTO 10 But an actual implementation would be quite a few more lines.

chriswarbo 3y ago
> I always considered Rule 110 the simplest system (code complexity wise) that is turing complete It can get a bit subjective, when trying to compare really simple systems. > an actual implementation would be quite a few more lines The simplest Turing-complete system to implement that I've come across is FlipJump ( https://esolangs.org/wiki/FlipJump https://esolangs.org/wiki/FlipJump ). The easiest Turing-complete system I've implemented is BitBitJump, which is older than FlipJump and slightly more complex ( https://esolangs.org/wiki/BitBitJump https://esolangs.org/wiki/BitBitJump ). I used it as a simple way to enumerate the output of all programs: implementation at http://www.chriswarbo.net/js/optimisation/levin_bbj.js http://www.chriswarbo.net/js/optimisation/levin_bbj.js and visualisation/explanation here http://www.chriswarbo.net/projects/optimisation/levin.html http://www.chriswarbo.net/projects/optimisation/levin.html (Technically these aren't Turing-complete, in the same way that C isn't Turing complete: the amount of memory they can reference is bounded by their word size. This can be fixed by allowing I/O to external storage. My program enumeration loops through all word sizes ;) )

rhdunn 3y ago

There are some interesting patterns/behaviours with Langton's ants. In a wrap around world (e.g. moving off the left/right will enter the other side), the ant will collide with its "hive" (starting blob) or "highway" (diagonal pattern) and repeat a hive-highway construction cycle. With two ants, depending on their starting position, they will end up in one of 3 patterns: 1. A hive-highway pattern like one ant; 2. As 1, but will collide with each other, then undo their construction until they go back to the beginning and then repeat this pattern; 3. Race around each other in an expanding diamond pattern. If the world is a wrap around world, when they reach one edge, they will start to undo/shrink the diamond, generating an expanding-collapsing diamond pattern. It's also interesting playing around with more colours/states, and different rules (180deg turn, no turn). With these generalized turmites, I've seen them create/use "super highway" constructs. -- A "super highway" is a straight line of a single colour where a turmite's behviour for that colour is to not turn. -- It will then race forward along that highway.

SeanAnderson 3y ago

This is so cool! Does the term "ant" here have any real-world implications to the behavior of ants, or is it simply a creative term? Obviously ants are known to build highways, but that's through use of pheromone trails rather than a very simple process of turning, right? But I guess the black/white configuration is a binary representation of a pheromone trail? So, maybe?

chkas 3y ago

https://easylang.dev/ide/#run=len%20f%5B%5D%20100%20*%20100%0Afunc%20show%20.%20.%0A%20%20%20clear%0A%20%20%20for%20i%20to%20len%20f%5B%5D%0A%20%20%20%20%20%20if%20f%5Bi%5D%20%3D%201%0A%20%20%20%20%20%20%20%20%20x%20%3D%20(i%20-%201)%20mod%20100%0A%20%20%20%20%20%20%20%20%20y%20%3D%20(i%20-%201)%20div%20100%0A%20%20%20%20%20%20%20%20%20move%20x%20y%0A%20%20%20%20%20%20%20%20%20rect%201%201%0A%20%20%20%20%20%20.%0A%20%20%20.%0A.%0Aind%20%3D%20100%20*%2060%20%2B%2050%0Adir%20%3D%203%0Adir%5B%5D%20%3D%20%5B%201%20100%20-1%20-100%20%5D%0Afor%20cnt%20to%2012000%0A%20%20%20f%5Bind%5D%20%3D%201%20-%20f%5Bind%5D%0A%20%20%20dir%20%3D%20(dir%20%2B%202%20*%20f%5Bind%5D)%20mod%204%20%2B%201%0A%20%20%20ind%20%2B%3D%20dir%5Bdir%5D%0A%20%20%20call%20show%0A%20%20%20sleep%200.005%0A.%0A https://easylang.dev/ide/#run=len%20f%5B%5D%20100%20*%20100%...

tromp 3y ago
I like the result after just the first 52 steps: https://easylang.dev/ide/#run=len%20f%5B%5D%20100%20*%20100%0Afunc%20show%20.%20.%0A%20%20%20clear%0A%20%20%20for%20i%20to%20len%20f%5B%5D%0A%20%20%20%20%20%20if%20f%5Bi%5D%20%3D%201%0A%20%20%20%20%20%20%20%20%20x%20%3D%20(i%20-%201)%20mod%20100%0A%20%20%20%20%20%20%20%20%20y%20%3D%20(i%20-%201)%20div%20100%0A%20%20%20%20%20%20%20%20%20move%20x%20y%0A%20%20%20%20%20%20%20%20%20rect%201%201%0A%20%20%20%20%20%20.%0A%20%20%20.%0A.%0Aind%20%3D%20100%20*%2060%20%2B%2050%0Adir%20%3D%203%0Adir%5B%5D%20%3D%20%5B%201%20100%20-1%20-100%20%5D%0Afor%20cnt%20to%2052%0A%20%20%20f%5Bind%5D%20%3D%201%20-%20f%5Bind%5D%0A%20%20%20dir%20%3D%20(dir%20%2B%202%20*%20f%5Bind%5D)%20mod%204%20%2B%201%0A%20%20%20ind%20%2B%3D%20dir%5Bdir%5D%0A%20%20%20call%20show%0A%20%20%20sleep%200.02%0A.%0A https://easylang.dev/ide/#run=len%20f%5B%5D%20100%20*%20100%...

ChintanGhate 3y ago

Here's my implementation from 2014 that let's you spawn more ants on the grid. http://code-art.chintanghate.me/LangtonsAnt.html http://code-art.chintanghate.me/LangtonsAnt.html

javier_e06 3y ago

There must be a minecraft version of this critter somewhere.

StrictDabbler 3y ago

I used to play around with Langton's Ant a lot. The longer patterns remind me of the climbable game assets in "Below the Root" and "The Jungle Book", early games by Dale Disharoon/DeSharone that I played on an Apple II compatible, though they were available on DOS and C64 as well. I'd always assumed that Dale based his vines on Langton's Ant but the timeline doesn't add up. Dale's games came out several years earlier. It is an interesting aesthetic subset of digital noise. Worth noting that Dale also worked on the strange Legend of Zelda CDi games. He had an unusual arc. https://www.uvlist.net/game-173637-Below+the+Root https://www.uvlist.net/game-173637-Below+the+Root http://blog.hardcoregaming101.net/2012/09/dale-desharone-unspoken-legend.html http://blog.hardcoregaming101.net/2012/09/dale-desharone-uns...

elevaet 3y ago

I prefer Langton's Phage

mitchellpkt 3y ago

I keep wondering about the dynamics of Langton's ant within an infinite adversarial environment. The game I have in mind retains the standard behavior and movement patterns of Langton's ant. However, it introduces an adversarial component: upon the ant's first encounter with any given tile, an adversary determines the initial color of the tile, either black or white. The adversary's influence is constrained to this initial tile color determination, without any additional intervention capabilities. The adversarial objective is twofold: primary is the prevention of 'highway' construction by the ant, and secondary, if the primary objective cannot be fully achieved, is to disrupt the 'highways' as swiftly as possible post-formation. I do not have a good intuition for who has the upper hand here. The adversary can be deliberate, but its influence is strictly limited to controlling initial conditions of the board. Maybe this falls under the Cohen-Kong Theorem, or a potential extension of it. I'm not sure whether that applies here since the adversary may provide a board with finite support or may choose to instead provide a board (or board-generating procedure) with infinite support.

mcphage 3y ago
Basically, does the ant have a finite loop? I would be surprised if there wasn't one.
- mitchellpkt 3y ago
  No idea. Hmm, off the cuff maybe I’d conjecture that there cannot exist any initial configurations such that the ant gets stuck in a loop of finite length for infinite iterations. On any Nth iteration, the ant has only touched <= N tiles. Suppose we do a thought experiment where we create a second board that is empty except for the initial states of the touched tiles up to the Nth step. This second board has finite support, and so the usual theorems kick in, and consequently the ant will eventually start building a highway that would carry it away from the initial loop. I’m just making up guesses though, I have no clue if that is right.
NackerHughes 3y ago
Since the movement of Langton's Ant is entirely deterministic, it would be possible in this scenario to make the Ant go wherever the adversary pleases. The initial settings of the pixels can be carefully engineered to facilitate any arbitrary pattern of motion. The ant's movement can be easily calculated ahead of time to help with getting the initial pixel colours right.

dang 3y ago

Related: Langton's Ant - https://news.ycombinator.com/item?id=20123626 https://news.ycombinator.com/item?id=20123626 - June 2019 (25 comments) Hexagonal Langton's Ant 2 – Colors, Gliders and Highways - https://news.ycombinator.com/item?id=10324517 https://news.ycombinator.com/item?id=10324517 - Oct 2015 (13 comments) Langton's ant - https://news.ycombinator.com/item?id=8265482 https://news.ycombinator.com/item?id=8265482 - Sept 2014 (42 comments) Langton's ant - https://news.ycombinator.com/item?id=2230459 https://news.ycombinator.com/item?id=2230459 - Feb 2011 (20 comments)

lproven 3y ago

Nice. I implemented this in Sinclair BASIC on my ZX Spectrum about 35 years ago. :-) On checking, I see it was brand new stuff at the time!

YeGoblynQueenne 3y ago

Hah. That's a good memory. An implementation (simulation?) of Langton's Ant was the first program I wrote when I was learning COBOL for my mainframe job at >BIG FIN CORP< back in 2014. See, COBOL doesn't have a console, and there weren't any graphical capabilities to speak off on the system I worked on, so I just "animated" the simulation by producing multiple static screens. But it worked. I seem to have lost the source though, when I moved from that job.

TRiG_Ireland 3y ago

I was introduced to Langton's ant by the Science of Discworld books, which used it as an example of emergent phenomena.