1
$\begingroup$

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?

Thanks for your help!

Improve this question
$\endgroup$
  • $\begingroup$ 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 ..." ​ ​ ​ ​ $\endgroup$ – user12859 Mar 9 '16 at 22:59
  • $\begingroup$ @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 $\endgroup$ – rotia Mar 9 '16 at 23:27
  • $\begingroup$ The player is given access to the "open" path (section 2.2) of the relevant sliding door (figure 3). ​ ​ $\endgroup$ – user12859 Mar 9 '16 at 23:35
  • $\begingroup$ @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? $\endgroup$ – rotia Mar 10 '16 at 0:16
  • $\begingroup$ I think so. ​ ​ $\endgroup$ – user12859 Mar 10 '16 at 0:21
2
$\begingroup$

In the paper they created gadget called a gate. This gadget has two entrances, from one entrance the player can open the gate, the other entrance can be traversed only if the gate its on the open state.

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.

When the player enters the cell gadget, he accesses a chamber corresponding to the state the turing machine is at that moment. In the chamber, there are two gates that correspond to the two possible symbols that the turing machine can have. There, the player can open one of the gates, the opened door has to coincide with the symbol that the turing machine has in that cell. He opens the gate by entering through one of the two entrances of the gate, he cannot access the other entrance from here. After opening the gate, he can traverse one of the two symbol gates, closing it.

After traversing the gate, the player reaches a different corridor, from that corridor he can access only the "state gates" that have the same symbol that the symbol gadget has (if they are opened), so he must have chosen to open the correct gate gadget in order to continue. Assuming that the player decided to open the correct state gadget, he can return to the same gate he opened before by entering through the second entrance of the gate (I thought that the player went to a different gate after that, the figure confused me).

After traversing the gate from this second entrance, the player closes the gate. From here he goes to a corridor that allows the player to open one of the symbols gadgets he visited previously (not a different one), and he will only be allowed to open the symbol gadget that the turing machine will write in that state and symbol configuration (if he decides not to open the symbol gate, he will be trapped if he decides to return to the gadget).

Improve this answer
$\endgroup$
  • 1
    $\begingroup$ Note that this paper, published 10 months later, claims to show the same hardness for actual Sokoban. ​ ​ $\endgroup$ – user12859 Mar 16 '16 at 23:44

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.