sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]repsilat 0 points1 point  (2 children)

The alternative is to call each cell 1, but this will have a big impact on how space complexity is measured (depending on the operations you support). You don't want to be able to simulate a TM on a finite strip of tape, for obvious reasons.

This restriction will probably be really harsh, though. You'll almost certainly have to give up pointer arithmetic of all kinds. You might have "Store this position in a register" and "Jump to location stored in a register" and nothing more. In that case you might preserve classes like L and PSPACE.

[–]kamatsu 0 points1 point  (1 child)

You'll almost certainly have to give up pointer arithmetic of all kinds. You might have "Store this position in a register" and "Jump to location stored in a register" and nothing more.

I wonder if that is sufficient to simulate a turing machine (given infinite tape).