In the very first chapter of
Gödel, Escher, Bach, Douglas Hofstadter poses a very interesting puzzle that he calls the
MU Puzzle. Trying to solve this puzzle is a very interesting exercise. The puzzle, as well as the solution is available on
Wikipedia. I'm reproducing just the puzzle statement here so that you can attempt to solve it without accidentally glancing at the solution
.
The puzzleLet's suppose to have the symbols
M,
I, and
U which can be combined to produce strings of symbols or "words". The MU puzzle asks to start with a the "axiomatic" word
MI and transform it into the word
MU using in each step one of the following transformation rules:
1. At the end of any string ending in
I, you can add a
U, such as changing
MI to
MIU.
2. You can double any string after the
M (that is, change
Mx, to
Mxx), such as changing
MIU to
MIUIU.
3. You can replace any
III with a
U, such as changing
MUIIIU to
MUUU.
4. You can remove any
UU, such as changing
MUUU to
MU.
Using these 4 rules is it possible to change
MI into
MU in a finite number of steps?
We can write the production rules in a more schematic way. Suppose
x and
y behave as variables (standing for a string of symbols) then the production rules can be written as:
1. xI → xIU
2. Mx → Mxx
3. xIIIy → xUy
4. xUUy → xy
can we obtain the word
MU, using these rules?
Print