brainwagon

An as-yet unfinished draft of Bob Hearn’s MIT PhD thesis Games, Puzzles and Computation is online.   I first became aware of some of these results at a conference a couple of years ago, which showed that sliding block puzzles like Rush Hour belong to the class of PSPACE-complete problems.   What does that mean?  From the previous paper:

Technically, a problem is called PSPACE-complete if it is equal in computational power to a particular mathematical model of computation (called “polynomial space-bounded Turing machines”).  Practically, this means that one can build computers out of the elements of the problem, just as one can with wires and transistors.

If this didn’t mean anything to you, here’s another try at explaining what it means.  Imagine that you can program a computer that can answer some yes or no question by executing an arbitrary program.   Hearn can build a sliding block puzzle that only has a solution if the computer would print “yes”.   This is perhaps a bit surprising: that no matter how lengthy, long, involved a calculation might be on a computer, you can represent it as a bunch of sliding blocks.

Well, I think it’s cool.

[tags]Turing Machine,Computer Science,Recreational Mathematics,Games[/tags]