Robustness of Turing Machines - 3 dimensional case

How can one show that a machine with a three dimensional memory arranged in an infinite grid can be simulated by a single-tape Turing machine? I'd imagine there's some sort of mapping possible from three dimensional coordinates to single coordinates (eg. (0,0,0) -> 0, (1,0,0) -> 1, (-1,0,0) -> 2, ...) but I can't figure it out. Or maybe there's some clever way to separate the points using special symbols. Either way, I'm at a loss.

If you are not concerned with efficiency this trivial and time-wasting approach can also work (it only shows how it can be done without taking too much care of coordinate-mappings ... in other words the bad way to do it :-)).

Use the single tape to store a list of quadruples $...\#x,y,z,v\#...$.

Each quadruple holds the value $v$ stored on the 3D tape at point $(x,y,z)$. Initially the single tape is filled with a finite list of the non-blank values of the 3D tape along with their coordinates, and the head is on the left of the quadruple that represents the head position in the 3D tape.

Every step of the original 3D machine can be simulated in the following way:

• apply the original transition, and update the value $v$ to $v'$ in $(x,y,z,v)$

• now, suppose that the head must move to the adjacent 3D point $(x',y',z')$, then search in the tape from left to right for a quadruple that matches its coordinates;
• if you find it, then move the head on it and go to (1);
• if you don't find it, just append a new quadruple $(x',y',z',blank)$ to the end of the tape, move the head on it and goto (1)

For every state of the original 3D machine you must have many states on the single tape machine in order to perform the operations at step 2 and at the same time keep track of the current state of the original machine.

StackExchange Computer Science Q#6454, answer score: 4