7 ms·

Langton's ant

118 points by _piyush 12y ago

sp332 12y ago
How can it be Turing-complete with only two colors and one state? I thought you needed at least two colors and three states to be Turing-complete. https://en.wikipedia.org/wiki/Wolfram%27s_2-state_3-symbol_Turing_machine https://en.wikipedia.org/wiki/Wolfram%27s_2-state_3-symbol_T...
- JadeNB 12y ago
  I believe that it is the distinction between playing on a 1-dimensional or 2-dimensional grid. EDIT: Also, as the article that you link points out, while all definitions of Turing machines agree on their power as a class, minimality results like this are quite sensitive to the details of the definition. (In particular, the article seems to hedge its bets by saying that that machine may be the smallest universal machine.)
  - Crito 12y ago
    Hmm, I'm not convinced that there should be a difference between 1d grids and 2d grids, since 2d grids are countable and can be represented as 1d grids (just spiral out from any tile on the 2d grid and you'll get a 1d grid. The rules for the ant would have to take this into account, but I don't see any reason why they shouldn't be able to). That's mostly just my intuition though; it is very possible that I am wrong.
    - throwaway_yy2Di 12y ago
      Sure, but you'd need more internal states to deal with the overhead of that simulation. On a 2D grid "up" is a primitive op; in your 1D spiral, "up" is some complicated function that probably needs unbounded memory of its own to compute (i.e., an explicit pair of grid coordinates, stored as an integer). (There's a textbook example where you can add auxiliary memory to a (1D) Turing machine, called a "multi-tape" Turing machine. And you can reduce that to a single-tape Turing machine, but at the cost of blowing up the number of states in the finite automaton).
- da-bacon 12y ago
  2d versus 1d Turing machine apparently. Here is the paper claiming universality: http://www.dim.uchile.cl/~anmoreir/oficial/langton_dam.pdf http://www.dim.uchile.cl/~anmoreir/oficial/langton_dam.pdf
- throwaway_yy2Di 12y ago
  In a sense it really has four "states", since the ant remembers which direction it had previously moved. That's implicit in the clockwise/counterclockwise rule.
  - burtonlang 12y ago
    I would say there are 10 states. Any square can be empty or have an ant, and if the ant is there its direction is known. That gives 5 states of ant presence and direction, and since a square has 2 color states, that's 10 total states.
    - throwaway_yy2Di 12y ago
      I'm counting "states" as the term's used in (tape) Turing machines, where you distinguish the internal states of the finite automaton (tape head) from the memory states of the unbounded tape (symbols or colors). So this ant would be analogous to a 4-state, 2-color Turing machine. The ant has four possible states; each cell of the grid has two.
      - laumars 12y ago
        What about when the ant reaches the edge of his grid? (this part I couldn't find an explanation for on the wiki)
        throwaway_yy2Di 12y ago
        The grid has no edges, it's infinite in all directions!
        laumars 12y ago
        I see. It would be interesting to see this on a finite universe - a curved universe where opposite edges join
  - sp332 12y ago
- deleted 12y ago
  [deleted]
jreimers 12y ago
Interesting "art" can be generated by running the algorithm against a random initial map. Edit: adjusting the density of the initial map seems to result in different patterns appearing in the output http://jsfiddle.net/2yxyno52/4/ http://jsfiddle.net/2yxyno52/4/
MattHeard 12y ago
Langton's ant colony eBook cover generator: each word in the eBook title seeds the initial parameters (location, direction) of an ant and the simulation is run for a large, constant number of steps, producing an interesting and reproducible generated cover.
- sneak 12y ago
  Top Ten Signs You've Been Reading Too Much Hacker News
daeken 12y ago
I've been obsessed with Langton's ant for a good solid decade now. My latest creation is a few years old now, but occasionally I go back and add new commands. It's inspired by Langton's ant, but it operates in 45 degree increments, has the ability to fork, conditionally execute instructions, has colors, and a bunch of other interesting things. You can see it in action at http://demoseen.com/langton/#.FP$!!!!!!!!!!!!!!!!!!!!~ http://demoseen.com/langton/#.FP$!!!!!!!!!!!!!!!!!!!!~ and there's a simple instruction listing at the bottom of the page. It's quite a departure from the original, but you can make absolutely gorgeous images with some simple instructions.
- hrjet 12y ago
  Wow! A suggestion: Adding some sort of inertia calculation. It might lead to very complex and yet smooth looking images.
- mercurial 12y ago
  Beautiful. Thanks!
- jtms 12y ago
  Wow! Very cool... I could play with this for days! Thank you for posting this.
- briandw 12y ago
  This is amazing work. Langton's ant was one of the first programs I wrote in Java around 1996 so it's super fun to see what you've done with it.
- cezarywojcik 12y ago
  This is awesome - lot of fun to play with. This is the best pattern I've been able to come up with so far: http://demoseen.com/langton/#..rr@<>@!!@@ http://demoseen.com/langton/#..rr@<>@!!@@
  - daeken 12y ago
    That's really cool -- I love 'lattice' type patterns. This is my current favorite, because it seems to terminate (stabilize) and then does one last little bit. Runs for a good while before it 'terminates', as well. http://demoseen.com/langton/#.$!~PF!!!! http://demoseen.com/langton/#.$!~PF!!!!.
patkai 12y ago
But what happened to Langton himself? After leaving SFI and the Swarm corp he seems to have disappeared. I met him once - about 12 years ago - and he was the most charming, kind guy who spent three hours and a lunch with me just because I said I don't understand something he said. Then he warned me not to become too much of a generalist and specialise more. He was right, but I didn't listen to him, I was in my 20s and thought I can be a polymath :)
- tim_hutton 12y ago
  I spoke to Glen Ropella of Swarm about him in 2009 when I was writing a paper and Glen said this: "Most of the people I know related to Swarm refer people to me when they're looking for Chris. It's no mystery, though. He decided awhile back to leave the Swarm/SFI community for personal reasons. So, he's out there. He just doesn't want to work on that stuff anymore, at least as of the last time I talked to him. ... He may well want to interact. I don't know. All I know is I haven't heard from him in awhile." Chris, if you're out there: Hi!
  - api 12y ago
    I looked for Langton myself years ago when I was very into artificial life and evolutionary computing. IMHO he's one of the greatest unsung geniuses of the past 25 years. Here's what I consider his greatest work: http://wiki-app2.tudelft.nl/pub/Education/SPM955xABMofCAS/LectureIntroductionToComplexity/Computation_at_the_edge_of_chaos__Langton.pdf http://wiki-app2.tudelft.nl/pub/Education/SPM955xABMofCAS/Le... To give you one example: that paper is why I think Titan is the most likely world in the solar system where we might find present-day complex life. (Other than Earth of course.) Why? There's no liquid water on the surface, and it's too cold! Answer: phase boundaries everywhere. See Fig. 3 from paper. Titan has a hydrocarbon-based "water cycle" with solid, liquid, and gas all existing at the same time, along with what appear to be seasons. Universal computation occurs in the vicinity of phase boundaries, so I would not be terribly surprised if we found "cryolife" there. It would be radically different from our own, but not really... I agree with people like Langton that life should be considered primarily an informatics phenomenon rather than a conventional chemical reaction or physical state. If Titan life were intelligent, they'd regard us as hell-beasts with blood of molten water. :) We could never physically touch, as we would vaporize them and they would freeze us solid. There's a contemporary scientist named Dr. Christoph Adami at Michigan State's new BEACON center who's probably the closest to following in Langton's footsteps. http://www.mmg.msu.edu/adami.html http://www.mmg.msu.edu/adami.html Adami expounded upon these ideas by defining life as "a phase of matter in which the dynamics of information processing overcome those of ordinary matter and energy." I am paraphrasing, and possibly butchering it a little... can't find the original quote, but that's the basic idea. Life is a phase of matter -- one whose behavior is dominated by universal Turing-complete computation. You might call living matter "Turium" or something. The fact that this whole line of reasoning hasn't been taken up more broadly is IMHO some kind of failure of the academic and scientific system.
Kiro 12y ago
I'm looking for an algorithm that is as simple as Langton's ant but with X amount of ants that all compete in some way. Any pointers?
- TuringTest 12y ago
  The Wikipedia article contains several variations, including that one. Check the external links for videos and programs. Interestingly, multiple ants don't need conflict resolution, as two ants sharing the same cell will want to leave it at the same state. https://en.wikipedia.org/wiki/Langton's_ant https://en.wikipedia.org/wiki/Langton's_ant
  - Kiro 12y ago
    Thanks. I am actually looking for one with conflicting resolutions though and can't seem to find that in the links. Basically I want to make a game where you put out ants that compete somehow. Either the one with most converted tiles wins or if they can kill each other. It doesn't have to be Langton's ant specifically, just an algorithm that is as easy to understand.
    - scrumper 12y ago
      I haven't thought this through, but I think a simple extension which would generate conflict would be to incorporate the ant's last movement in determining the end state of the cell it's currently on. That way, two ants arriving in the same cell from different directions would want different results.
Grue3 12y ago
One of the first programs I wrote was a simulator of Turmites in Visual Basic. There is an endless variety of configurations producing crazy abstract "art". I didn't know about Langton's ant back then, but I definitely noticed those "highways" that occured quite often from random experimentation.
Leszek 12y ago
> All finite initial configurations tested eventually converge to the same repetitive pattern, suggesting that the "highway" is an attractor of Langton's ant, but no one has been able to prove that this is true for all such initial configurations If Langton's ant is capable of universal computation, wouldn't non-halting programs be a counterexample to this convergence?
- sp332 12y ago
  Langton's ant has no halting state. It can't halt. But you're right, that description doesn't leave any room for programs that run in a specific loop forever instead of making a highway. So that doesn't seem to be Turing-complete.
- Igglyboo 12y ago
  I'd have to agree. From my understanding of that sentence, all programs would "halt" eventually because they all end up doing the highway. So unless your computation somehow ended with the highway then you couldn't run infinitely long computations.
nixy 12y ago
Made a jsfiddle where you can see the ant move and die (crash) after building the highway for a while. http://jsfiddle.net/zuu7bd2e/ http://jsfiddle.net/zuu7bd2e/
- netnichols 12y ago
  Thanks! It was hard to get the point of how cool this is from the animation/description in the Wikipedia article.
Gonzih 12y ago
Order in chaos. Love it. I have few different patterns for ants on my homepage (implemented in ugly ClojueScript).
V-2 12y ago
How about 3D Langton's (or Langtonish) ants? Or more dimensions? :)
- JoeAltmaier 12y ago
  Need at least one new rule and a new color.
  - pavel_lishin 12y ago
    You could still do it with two colors if it remembered the previous color as well, and if you didn't allow "keep going straight" or "move back in the direction you came from" as options. (Imagine the ant as a space-ship, and every time it turns, it also changes its pitch/yaw, so the directions are based on its direction of travel.) Current | Previous | Action white | white | go starboard white | black | go port black | white | go down black | black | go up

118 points by _piyush 12y ago

sp332 12y ago

How can it be Turing-complete with only two colors and one state? I thought you needed at least two colors and three states to be Turing-complete. https://en.wikipedia.org/wiki/Wolfram%27s_2-state_3-symbol_Turing_machine https://en.wikipedia.org/wiki/Wolfram%27s_2-state_3-symbol_T...

JadeNB 12y ago
I believe that it is the distinction between playing on a 1-dimensional or 2-dimensional grid. EDIT: Also, as the article that you link points out, while all definitions of Turing machines agree on their power as a class, minimality results like this are quite sensitive to the details of the definition. (In particular, the article seems to hedge its bets by saying that that machine may be the smallest universal machine.)
- Crito 12y ago
  Hmm, I'm not convinced that there should be a difference between 1d grids and 2d grids, since 2d grids are countable and can be represented as 1d grids (just spiral out from any tile on the 2d grid and you'll get a 1d grid. The rules for the ant would have to take this into account, but I don't see any reason why they shouldn't be able to). That's mostly just my intuition though; it is very possible that I am wrong.
  - throwaway_yy2Di 12y ago
    Sure, but you'd need more internal states to deal with the overhead of that simulation. On a 2D grid "up" is a primitive op; in your 1D spiral, "up" is some complicated function that probably needs unbounded memory of its own to compute (i.e., an explicit pair of grid coordinates, stored as an integer). (There's a textbook example where you can add auxiliary memory to a (1D) Turing machine, called a "multi-tape" Turing machine. And you can reduce that to a single-tape Turing machine, but at the cost of blowing up the number of states in the finite automaton).
da-bacon 12y ago
2d versus 1d Turing machine apparently. Here is the paper claiming universality: http://www.dim.uchile.cl/~anmoreir/oficial/langton_dam.pdf http://www.dim.uchile.cl/~anmoreir/oficial/langton_dam.pdf
throwaway_yy2Di 12y ago
In a sense it really has four "states", since the ant remembers which direction it had previously moved. That's implicit in the clockwise/counterclockwise rule.
- burtonlang 12y ago
  I would say there are 10 states. Any square can be empty or have an ant, and if the ant is there its direction is known. That gives 5 states of ant presence and direction, and since a square has 2 color states, that's 10 total states.
  - throwaway_yy2Di 12y ago
    I'm counting "states" as the term's used in (tape) Turing machines, where you distinguish the internal states of the finite automaton (tape head) from the memory states of the unbounded tape (symbols or colors). So this ant would be analogous to a 4-state, 2-color Turing machine. The ant has four possible states; each cell of the grid has two.
    - laumars 12y ago
      What about when the ant reaches the edge of his grid? (this part I couldn't find an explanation for on the wiki)
      - throwaway_yy2Di 12y ago
        The grid has no edges, it's infinite in all directions!
        laumars 12y ago
        I see. It would be interesting to see this on a finite universe - a curved universe where opposite edges join
- sp332 12y ago
deleted 12y ago
[deleted]

jreimers 12y ago

Interesting "art" can be generated by running the algorithm against a random initial map. Edit: adjusting the density of the initial map seems to result in different patterns appearing in the output http://jsfiddle.net/2yxyno52/4/ http://jsfiddle.net/2yxyno52/4/

MattHeard 12y ago

Langton's ant colony eBook cover generator: each word in the eBook title seeds the initial parameters (location, direction) of an ant and the simulation is run for a large, constant number of steps, producing an interesting and reproducible generated cover.

sneak 12y ago
Top Ten Signs You've Been Reading Too Much Hacker News

daeken 12y ago

I've been obsessed with Langton's ant for a good solid decade now. My latest creation is a few years old now, but occasionally I go back and add new commands. It's inspired by Langton's ant, but it operates in 45 degree increments, has the ability to fork, conditionally execute instructions, has colors, and a bunch of other interesting things. You can see it in action at http://demoseen.com/langton/#.FP$!!!!!!!!!!!!!!!!!!!!~ http://demoseen.com/langton/#.FP$!!!!!!!!!!!!!!!!!!!!~ and there's a simple instruction listing at the bottom of the page. It's quite a departure from the original, but you can make absolutely gorgeous images with some simple instructions.

hrjet 12y ago
Wow! A suggestion: Adding some sort of inertia calculation. It might lead to very complex and yet smooth looking images.
mercurial 12y ago
Beautiful. Thanks!
jtms 12y ago
Wow! Very cool... I could play with this for days! Thank you for posting this.
briandw 12y ago
This is amazing work. Langton's ant was one of the first programs I wrote in Java around 1996 so it's super fun to see what you've done with it.
cezarywojcik 12y ago
This is awesome - lot of fun to play with. This is the best pattern I've been able to come up with so far: http://demoseen.com/langton/#..rr@<>@!!@@ http://demoseen.com/langton/#..rr@<>@!!@@
- daeken 12y ago
  That's really cool -- I love 'lattice' type patterns. This is my current favorite, because it seems to terminate (stabilize) and then does one last little bit. Runs for a good while before it 'terminates', as well. http://demoseen.com/langton/#.$!~PF!!!! http://demoseen.com/langton/#.$!~PF!!!!.

patkai 12y ago

But what happened to Langton himself? After leaving SFI and the Swarm corp he seems to have disappeared. I met him once - about 12 years ago - and he was the most charming, kind guy who spent three hours and a lunch with me just because I said I don't understand something he said. Then he warned me not to become too much of a generalist and specialise more. He was right, but I didn't listen to him, I was in my 20s and thought I can be a polymath :)

tim_hutton 12y ago
I spoke to Glen Ropella of Swarm about him in 2009 when I was writing a paper and Glen said this: "Most of the people I know related to Swarm refer people to me when they're looking for Chris. It's no mystery, though. He decided awhile back to leave the Swarm/SFI community for personal reasons. So, he's out there. He just doesn't want to work on that stuff anymore, at least as of the last time I talked to him. ... He may well want to interact. I don't know. All I know is I haven't heard from him in awhile." Chris, if you're out there: Hi!
- api 12y ago
  I looked for Langton myself years ago when I was very into artificial life and evolutionary computing. IMHO he's one of the greatest unsung geniuses of the past 25 years. Here's what I consider his greatest work: http://wiki-app2.tudelft.nl/pub/Education/SPM955xABMofCAS/LectureIntroductionToComplexity/Computation_at_the_edge_of_chaos__Langton.pdf http://wiki-app2.tudelft.nl/pub/Education/SPM955xABMofCAS/Le... To give you one example: that paper is why I think Titan is the most likely world in the solar system where we might find present-day complex life. (Other than Earth of course.) Why? There's no liquid water on the surface, and it's too cold! Answer: phase boundaries everywhere. See Fig. 3 from paper. Titan has a hydrocarbon-based "water cycle" with solid, liquid, and gas all existing at the same time, along with what appear to be seasons. Universal computation occurs in the vicinity of phase boundaries, so I would not be terribly surprised if we found "cryolife" there. It would be radically different from our own, but not really... I agree with people like Langton that life should be considered primarily an informatics phenomenon rather than a conventional chemical reaction or physical state. If Titan life were intelligent, they'd regard us as hell-beasts with blood of molten water. :) We could never physically touch, as we would vaporize them and they would freeze us solid. There's a contemporary scientist named Dr. Christoph Adami at Michigan State's new BEACON center who's probably the closest to following in Langton's footsteps. http://www.mmg.msu.edu/adami.html http://www.mmg.msu.edu/adami.html Adami expounded upon these ideas by defining life as "a phase of matter in which the dynamics of information processing overcome those of ordinary matter and energy." I am paraphrasing, and possibly butchering it a little... can't find the original quote, but that's the basic idea. Life is a phase of matter -- one whose behavior is dominated by universal Turing-complete computation. You might call living matter "Turium" or something. The fact that this whole line of reasoning hasn't been taken up more broadly is IMHO some kind of failure of the academic and scientific system.

Kiro 12y ago

I'm looking for an algorithm that is as simple as Langton's ant but with X amount of ants that all compete in some way. Any pointers?

TuringTest 12y ago
The Wikipedia article contains several variations, including that one. Check the external links for videos and programs. Interestingly, multiple ants don't need conflict resolution, as two ants sharing the same cell will want to leave it at the same state. https://en.wikipedia.org/wiki/Langton's_ant https://en.wikipedia.org/wiki/Langton's_ant
- Kiro 12y ago
  Thanks. I am actually looking for one with conflicting resolutions though and can't seem to find that in the links. Basically I want to make a game where you put out ants that compete somehow. Either the one with most converted tiles wins or if they can kill each other. It doesn't have to be Langton's ant specifically, just an algorithm that is as easy to understand.
  - scrumper 12y ago
    I haven't thought this through, but I think a simple extension which would generate conflict would be to incorporate the ant's last movement in determining the end state of the cell it's currently on. That way, two ants arriving in the same cell from different directions would want different results.

Grue3 12y ago

One of the first programs I wrote was a simulator of Turmites in Visual Basic. There is an endless variety of configurations producing crazy abstract "art". I didn't know about Langton's ant back then, but I definitely noticed those "highways" that occured quite often from random experimentation.

Leszek 12y ago

> All finite initial configurations tested eventually converge to the same repetitive pattern, suggesting that the "highway" is an attractor of Langton's ant, but no one has been able to prove that this is true for all such initial configurations If Langton's ant is capable of universal computation, wouldn't non-halting programs be a counterexample to this convergence?

sp332 12y ago
Langton's ant has no halting state. It can't halt. But you're right, that description doesn't leave any room for programs that run in a specific loop forever instead of making a highway. So that doesn't seem to be Turing-complete.
Igglyboo 12y ago
I'd have to agree. From my understanding of that sentence, all programs would "halt" eventually because they all end up doing the highway. So unless your computation somehow ended with the highway then you couldn't run infinitely long computations.

nixy 12y ago

Made a jsfiddle where you can see the ant move and die (crash) after building the highway for a while. http://jsfiddle.net/zuu7bd2e/ http://jsfiddle.net/zuu7bd2e/

netnichols 12y ago
Thanks! It was hard to get the point of how cool this is from the animation/description in the Wikipedia article.

Gonzih 12y ago

Order in chaos. Love it. I have few different patterns for ants on my homepage (implemented in ugly ClojueScript).

V-2 12y ago

How about 3D Langton's (or Langtonish) ants? Or more dimensions? :)

JoeAltmaier 12y ago
Need at least one new rule and a new color.
- pavel_lishin 12y ago
  You could still do it with two colors if it remembered the previous color as well, and if you didn't allow "keep going straight" or "move back in the direction you came from" as options. (Imagine the ant as a space-ship, and every time it turns, it also changes its pitch/yaw, so the directions are based on its direction of travel.) Current | Previous | Action white | white | go starboard white | black | go port black | white | go down black | black | go up