Langton's ant • Hacker News Board

Re: Langton's ant

#21

Post by tim_hutton » Thu, Sep 04, 2014, 10:19 AM UTC

patkai wrote: post #16

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 an…

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!

Re: Langton's ant

#22

Post by Grue3 » Thu, Sep 04, 2014, 11:10 AM UTC

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.

Re: Langton's ant

#23

Post by jtms » Thu, Sep 04, 2014, 11:16 AM UTC

daeken wrote: post #14

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$!!!!!!!!!!!!!…

Wow! Very cool... I could play with this for days! Thank you for posting this.

Re: Langton's ant

#24

Post by Leszek » Thu, Sep 04, 2014, 11:19 AM UTC

> 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?

Re: Langton's ant

#25

Post by laumars » Thu, Sep 04, 2014, 11:50 AM UTC

throwaway_yy2Di wrote: post #20

laumars wrote: post #19

Earlier quoted context omitted.

What about when the ant reaches the edge of his grid? (this part I couldn't find an explanation for on the wiki)

The grid has no edges, it's infinite in all directions!

I see. It would be interesting to see this on a finite universe - a curved universe where opposite edges join

Re: Langton's ant

#26

Post by TuringTest » Thu, Sep 04, 2014, 12:33 PM UTC

Kiro wrote: post #17

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?

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

Re: Langton's ant

#27

Post by sp332 » Thu, Sep 04, 2014, 2:03 PM UTC

throwaway_yy2Di wrote: post #5

sp332 wrote: post #2

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_T...

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.

Oh yeah, that's a good point!

Re: Langton's ant

#28

Post by sp332 » Thu, Sep 04, 2014, 2:16 PM UTC

Leszek wrote: post #24

> 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?

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.

Re: Langton's ant

#29

Post by nixy » Thu, Sep 04, 2014, 2:37 PM UTC

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

http://jsfiddle.net/zuu7bd2e/

Re: Langton's ant

#30

Post by Kiro » Thu, Sep 04, 2014, 2:45 PM UTC

TuringTest wrote: post #26

Kiro wrote: post #17

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?

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

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.