Synchronizing sequences for rubik's cube?

Question

Are there any results on the existence of synchronizing sequences for a standard 3x3 rubik's cube? Like a proof that there are none? My google-skills failed me...

Answer 1

Synchronizing sequence over a finite state machine: a sequence of state transitions that leads the machine to a known unique final state independently of the (unknown) initial state.

In the Rubik's cube there are obviously no "self stopping" configurations: every move leads to a new configuration, so you are forced to look at the current configuration in order to decide the next move. This implies that a synchronizing sequence (as usually defined) cannot exist.

A trivial demonstration: suppose that $SSEQ = m_1 m_2 m_3 ... m_n$ is a synchronizing sequence of moves that leads to a solved Rubik's cube independently of the initial configuration. Now pick a wrong configuration and apply the reverse sequence $m^{-1}_n m_{n-1}^{-1} ... m_1^{-1}$ where $m_i^{-1}$ is the inverse of move $m_i$ (and is well defined because if you apply the same move to two different cube configurations you cannot obtain the same configuration). This reverse sequence leads to a unique configuration $c_0$. If you apply sequence $SSEQ$ to $c_0$ you obviously don't end to a solved Rubik's cube.

What you can do is to allow to stop every subsequence looking at the content of a particular cube's coordinate. For example run subsequence 1 until corner at (0,0,0) contains the red+yellow+blue block, then proceed to subsequence 2 (which will correctly position another block, and so on. In this case you can reach a known final configuration running a fixed sequence of moves made of subsequences that can stop looking at the content of a fixed sequence of blocks. This is very similar to what is usually called an homing sequence.

Perhaps another nice question is "What is the shortest sequence of moves and monitored coordinates that leads to a known final configuration in this modified homing version?".

For example to put a known block at monitored coordinate (0,0,0) (asterisk * in the figure), the length of the first trivial subsequence must be 28

F1.rotate, F1.rotate, F1.rotate 
R4.shiftL, R6.shiftL, F1.rotate, F1.rotate, F1.rotate
R4.shiftL, R6.shiftL, F1.rotate, F1.rotate, F1.rotate
R4.shiftL, R6.shiftL, F1.rotate, F1.rotate, F1.rotate
C4.shiftDown, C6.shiftDown, F1.rotate, F1.rotate, F1.rotate
C4.shiftDown, C6.shiftDown, F1.rotate, F1.rotate, F1.rotate

EDIT: Another interesting question (suggested by Tsuyoshi and Kaveh in the comments) arise if we consider the case in which the sequence of moves automatically stops when the cube is solved: if no information is gathered/stored during the moves then we must scan all cube's configurations (similar configurations obtained rotating the whole cube should be grouped in equivalence classes).

But what is the shortest sequence that scans all cube's configurations, or better does the configuration graph of the cube have a Hamiltonian path?.

This is a special case of a more general unsolved problem: for an arbitrary permutation group with a given generating set, is its Cayley graph Hamiltonian?

There are some good info available online, I cite the book: Adventures in Group Theory: Rubik's Cube, Merlin's Machine, and Other Mathematical Toys and the lecture notes by W.D.Joyner: Mathematics of the Rubik's cube (downloadable in pdf format).

Chapter 6 of the lecture notes is devoted to Cayley graphs and God's algorithm.