# In this proof that sokoban+ is pspace complete, how does the gadgets register the fact that a cell of the turing machine has changed?

I´ve been reading the paper "SOKOBAN and other motion planning problems" by Dorit Dor and Uri Zwick.

This is a link to the paper: Sokoban+ is pspace complete

In the paper, they proved that a problem called sokoban+ is pspace complete, they did it by reducing simulation of a turing machine with bounded tape to that problem.

sokoban+ is like sokoban, but the player can pull and push obstacles and all pieces are 2 x 1 rectangles (instead of 1 x 1 like in normal sokoban).

In figure 7, they show a drawing of the cell gadget, this represents a cell of a turing machine.

In the cell, the player enters, chosses a simbol (0 or 1) and if the player chooses correctly, he can go to a simbol gadgdet which will be open only if he has chosen the correct symbol. He goes through the symbol gadget, closing it, and then he goes to a gadget that forces the player to go to the next cell.

My question is, if in this cell and state the symbol of the tape has to change, how does the cell gadget registers that the symbol has changed?

• Near the bottom of page 5: ​ "If the Turing machine is supposed to write j', ..., then the porter may now open gate B$_{\hspace{-0.02 in}j\hspace{.02 in}'}$ and ..." ​ ​ ​ ​ – user12859 Mar 9 '16 at 22:59
• @Ricky Demer Thanks Ricky, i didn´t see that. I´m very dense. But doesn´t this mean that there are more than 2 $B$ gates for cell? . I mean the gates are not connected to each other and once the player goes out through one of the $A_i,j$ gates he cannot return to the previous $B$ gates to change them. The picture seems to show that the player has to open a $B_j$ gate that it´s after the one he just passed. I´m sure i´m getting something wrong – rotia Mar 9 '16 at 23:27
• The player is given access to the "open" path (section 2.2) of the relevant sliding door (figure 3). ​ ​ – user12859 Mar 9 '16 at 23:35
• @Ricky Demer I think that i´m starting to see what was my problem. By looking at the image, i thought that the player goes from some $A_i,j$ to $B_j$ and then to some different $A_i,j$ gates. But, what the player does is open some door $A_i,j$, then, he goes to the $B_j$ door that is open, closing it. Then, he returns to the $A_i,j$ door he opened before. He goes through that door, closing it, and from there he can open the corresponding $B_j$ door and exit the cell. Am I right? – rotia Mar 10 '16 at 0:16
• I think so. ​ ​ – user12859 Mar 10 '16 at 0:21

In the cell gadget, there are $2k + 2$ gates where $k$ is the number of states the turing machine has and the other two gates correspond to the symbols ($0$ or $1$) that the tape of the turing machine can have.