I was looking at this: http://www.cs.odu.edu/~toida/nerzic/390teched/tm/othertms.html

At the very beginning, they show a 2d tape and (I assume) it's 1d equivalent. However, I cannot figure out they got from the 2d case to the 1d case. I was hoping someone could elaborate.


The idea is very similar to the way we show that the rational numbers are countable. Essentially, what you need to do is to find a (bijective) mapping of the 2D tape onto the 1D tape. Of course, you want this mapping to be computable, and it would be helpful if it is computable efficiently.

The illustrative way to think about this is in diagonals: the cell $(1,1)$ is mapped to cell $1$ in the 1D tape. Then the second diagonal, namely cells $(1,2)$ and $(2,1)$ are mapped to cells $2,3$ respectively. Continuing in the same manner, you can map the entire 2D tape to the 1D tape. Of course, any movement of the head needs to be translated to the correct position in the 1D tape, so a single movement in the 2D tape may actually take several operations to simulate in the 1D tape.

There are many explicit functions that compute such a mapping. See for example the Cantor pairing function.

| cite | improve this answer | |
  • $\begingroup$ So what function were they using? That is what I was really asking? $\endgroup$ – user678392 Sep 26 '13 at 17:49
  • $\begingroup$ The problem with their function is that it goes "back and forth" in the diagonals. It is easy to draw, but to formulate it mathematically you will probably need a patched function, where the cases are even and odd columns. It's not pretty... $\endgroup$ – Shaull Sep 26 '13 at 18:56
  • 1
    $\begingroup$ Just to make sure I'm following you: they could have used (but didn't) the cantor pairing function, which would have been easy to write down. Is this correct? $\endgroup$ – user678392 Sep 26 '13 at 21:49
  • $\begingroup$ That is correct. $\endgroup$ – Shaull Sep 27 '13 at 5:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.