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:

  1. apply the original transition, and update the value $v$ to $v'$ in $(x,y,z,v)$
  2. 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.


Let's begin with a 2D infinite memory. point (0,0) is 0. Then, we go in "circles" around the (0,0) so that we cover all the plane. Each "step" increases the image index by one.. $walk \equiv (x,y) : (0,0) \to (1,0) \to (1,1) \to (0,1) \to (-1,1) \to \cdots$

See the image in:

(it might be copyrighted, so I just give a link. If somebody finds a free picture, I'd be grateful if you could add it here).

Now, the specific order doesn't really matter, as long as you eventually cover all the points, and have a systematic way to describe your mapping.

Generalizing to 3D space is not a big deal. Begin with (0,0,0), and cover all the points around in some order.

For instance, for a fixed $z$ value, we reduce the problem to a 2D-plane which can be covered like following the series $walk$ above. To cover the entire space, we change $z$ at each step, so that every value will be chosen infinitely many time. For instance, let $z$ be (along the first few steps): 0,1,0,1,2,0,1,2,3,.... Actually, $z$ should be also negative, so it could look like $z: 0,1,-1,0,1,-1,2,-2,0,1,-1,2,-2,3,-3,...$. For every choiceof $z$ we have a fresh copy of $walk$, which we denote $walk_z$, that determines the next value of $x$ and $y$ for that plane (i.e., $walk_z = (0,0,z)\to (1,0,z) \to (1,1,z)\cdots$). At every step, we choose a specific plane (value of $z$) and pick the next value of the series $walk_z$ that hasn't been picked before.

(if somebody finds a 3D pic (or can draw one), please add it..)


Your Answer

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