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

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



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




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

Search: