Langton's ant | Hacker News Reader

Langton's ant

en.wikipedia.org

176 pointsguyr20 comments

I've been interested in Langton ants for a good 8 years now, and have been playing with variants on them for a long time. Here's one of my favorites: http://pyvascript.appspot.com/Langton45

Rather than working on 90 degree turns, this does 45 degree angles, and it has a bit more complexity in the command set.

The rules are: + and - turn right and left 45 degrees, * and / turn right and left 90 degrees, ! reverses direction, . does nothing.

You can come up with some really interesting patterns, e.g. http://pyvascript.appspot.com/Langton45?command=*.%2B

Edit: Huh, I guess I never released any of that. I should port it to a modern Pyvascript and throw it up somewhere, as the version this is built against is probably going on 3 years old.

That's really cool. At times it looks like a spider spinning a web. Does it ever reach a state where the behavior becomes constant?

Not really, although you can make stable ants. Doing anything complex and stable, though, is really difficult. After I built that, I spent a couple weeks doing little but trying to create something simple (in terms of commands) and beautiful, that would run indefinitely; I was never really very successful. That said, I may well be the only person that's ever played with 45-degree ants, so there's a good potential for someone else to succeed where I failed.

Out of curiosity, why do you like Pyvascript?

Pyvascript started because I simply didn't like Javascript at the time (and still don't, for most things). I wanted a way to write my entire app in Python and use macros to make my life easier. To that end, I wrote two libraries: Transformana, which allows arbitrary manipulation of the Python AST by macros, and Pyvascript, which utilizes Transformana to compile down to Javascript on the fly. Combining the two allowed me to get all the benefits of Python with the flexibility of Javascript, and macros to make life easy. For example, when used with Pylons you can do _uriOf(SomeController.action) to generate a URL that gets baked into the JS. It also turns Python classes into JS classes, which allowed me to make AJAX calls trivial.

I used Pyvascript heavily for one product and it's fairly battle-hardened at this point, but since I don't really do anything web-wise anymore I haven't done much with it lately.

Also see Conway's Game of Life for an interactive system of complex emergent behaviors from very simple rules:

http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life

http://www.bitstorm.org/gameoflife/

For more fun along these lines, wolfram provides as always:

http://demonstrations.wolfram.com/CellularAutomatonExplorer/

(Cellular Automata is the name for these constructs, langon's ant, the game of life, and so on.)

Wolfram's book "A New Kind of Science" is an interesting take on cellular automata as well, although readers should be warned that it borders on crank science, has tons of hyperbole in it's treatment of CA's potential impact on science, and waters down the contributions of others in the field.

Ray Kurzweil's review:

http://www.kurzweilai.net/reflections-on-stephen-wolfram-s-a...

It is interesting, but, pardon my ignorance, is it appropriate to call this "a behaviour" (in the traditional meaning of this word)? It looks to me like "just" playing with numbers, i.e. normal phenomenon ultimately describable with some math theory. It looks far-fetched to me to describe it with the terms like "simple rules can result to complex emergent behaviour," etc...

I remember there are some number sequences generated by some rules, which seems random at first and then some sub-sequence repeates. Now this looks similar to me, except it seems to more mysterious because someone described it as "ant doing something". ;-)

Yes, it appropriate to call this the behaviour of a mathematical system.

If you want to remove some of your self-described "ignorance" I highly recommend "Complexity: The Emerging Science at the Edge of Order and Chaos". It's a great primer on the origins of study of emergent behavior in chaotic systems, particularly highlighting the work of Chris Langton, Stuart Kaufman, the Santa Fe Institute and several others. GREAT read.

The interesting bit is that the best "math theory" we have for describing the behavior of this system is not much better than just running the simulation. In theory, the system should be "simple" in the sense that it has a low information entropy, as evidenced by its simple rules. And yet, we can't yet derive high-order epiphenomena from the low-order description without the rather brutish, informal, and inexact tactic of cranking through the rules and watching what happens. In short, it's interesting because it does look like it could "describable with some math theory" but so far said math theory has not been found.

>It looks to me like "just" playing with numbers, i.e. normal phenomenon ultimately describable with some math theory.

group theory is dealing with even simpler rules and it was able to reach the state of "math theory", though far from completed. Anything more complicated than that - tiny islands of understanded surronded by narrow seas of "playing with numbers" in the vast oceans of unknown.

>It looks far-fetched to me to describe it with the terms like "simple rules can result to complex emergent behaviour," etc...

>Now this looks similar to me

any proof of "far-fetchedness" or similarity would put you right into the head of the line for the Fields :)

Where can one find chaotic toy algorithms that don't involve Turing machines or cellular automata? (I need one for a project, and I keep running into image processing and biology applications. I actually need a toy one.)

EDIT: Found it: (pseudocode, not Python)

    while x > 1
         case ((x mod 2) == 0):
             x = x / 2
         case ((x mod 3) == 0):
             x = x + 1
         default:
             x = x * 3

The number of iterations it takes to leave the loop is chaotic.

See also, hailstorm numbers - http://en.wikipedia.org/wiki/Collatz_conjecture#Statement_of...

I have a free android live wallpaper, based on them: https://market.android.com/details?id=info.jaisharma.antsliv... . You can create/delete ants, the patterns they draw is always interesting specially since multiple ants affect each other's state and since a human draws ants at random location and time.