Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

> do not use stacks (nor do Turing machines

A Turing machine has two stacks. They're the part of the tape to the left of the head and the part of the tape to the right of the head.

The other Turing complete systems described use arbitrarily large amounts of storage that are addressed more often, and for example Langton's Ant uses a two-dimensional tape, which is "not two stacks" in the sense that it is more complex than two stacks.



More complex how? Both are abstract and can simulate each other. The difference in complexity would wend into practicality arguments that don't apply in Turing world.

Turing machine uses a tape, which is equivalent to two stacks, and also equivalent to a 2-dimensional tape (Farey Sequence), and (I guess, per previous comment) equivalent to Rule 110.

The word "Equivalent" always carries some load, though. For example, the Langton Ant tape and Rule 110 use a more interesting version of "blank" initial state, similar to the "send a message by flipping a coin on a chess board with an arbitrarily flipped coin on each square" puzzle.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: