News for hackers. Stuff that matters.
Re:Langton's ant by throwaway_yy2Di on Wednesday September 03, 2014 @11:22PM (#8266613)
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).

There are no comments on this comment yet.