Langton’s ant

https://en.wikipedia.org/wiki/Langton%27s_ant

by scapecast • 3 years ago

102 23 3 years ago

en.wikipedia.org

tectec• 3 years 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• 3 years 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• 3 years 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• 3 years ago

I always considered Rule 110 the simplest system (code complexity wise) that is turing complete:

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• 3 years 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 ).

The easiest Turing-complete system I've implemented is BitBitJump, which is older than FlipJump and slightly more complex ( 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 and visualisation/explanation here 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• 3 years 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• 3 years 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• 3 years ago

https://easylang.dev/ide/#run=len%20f%5B%5D%20100%20*%20100%...

tromp• 3 years ago

I like the result after just the first 52 steps:

https://easylang.dev/ide/#run=len%20f%5B%5D%20100%20*%20100%...

ChintanGhate• 3 years ago

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

javier_e06• 3 years ago

There must be a minecraft version of this critter somewhere.

StrictDabbler• 3 years 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

http://blog.hardcoregaming101.net/2012/09/dale-desharone-uns...

elevaet• 3 years ago

I prefer Langton's Phage

mitchellpkt4• 3 years 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• 3 years ago

Basically, does the ant have a finite loop? I would be surprised if there wasn't one.

mitchellpkt4• 3 years 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• 3 years 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.

mitchellpkt4• 3 years ago

Yep, it's a deterministic perfect information game. To "win" one needs only produce an initial board (or board generating procedure) that achieves certain characteristics, such as bounded highway length even with infinite iterations by the ant.

What I am curious about is whether these boards/procedures exist, and how to find them.

mitchellpkt4• 3 years ago

Update: I wrote a toy python library for evaluating Langton's ant in procedurally-generated infinite adversarial environments.

https://github.com/Mitchellpkt/infinite_adversarial_langtons...

dang• 3 years ago

Langton's Ant - 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 - Oct 2015 (13 comments)

Langton's ant - https://news.ycombinator.com/item?id=8265482 - Sept 2014 (42 comments)

Langton's ant - https://news.ycombinator.com/item?id=2230459 - Feb 2011 (20 comments)

lproven• 3 years 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• 3 years 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• 3 years ago

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

Langton’s ant

Related Stories