Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Langton's ant

en.wikipedia.org

Post reply on HN
Print view View original

1–10 of 44 posts

Re: Langton's ant

#3

Post by JadeNB »

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

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

Re: Langton's ant

#4

Post by da-bacon »

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

2d versus 1d Turing machine apparently. Here is the paper claiming universality: http://www.dim.uchile.cl/~anmoreir/oficial/langton_dam.pdf

Re: Langton's ant

#5

Post by throwaway_yy2Di »

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.

Re: Langton's ant

#6

Post by Crito »

JadeNB wrote: post #3
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...

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

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.

Re: Langton's ant

#7

Post by throwaway_yy2Di »

Crito wrote: post #6
JadeNB wrote: post #3

Earlier quoted context omitted.

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

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.

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

Re: Langton's ant

#8

Post by burtonlang »

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.

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.

Re: Langton's ant

#9

Post by throwaway_yy2Di »

burtonlang wrote: post #8
throwaway_yy2Di wrote: post #5

Earlier quoted context omitted.

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.

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.

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.
Post reply on HN