The MU Puzzle is a
formal system puzzle that I first discovered when I read
Douglas R. Hofstadter's book
Gödel, Escher, Bach: an Eternal Golden Braid.
You start with a string of letters
MI. From this you try to derive the string
MU, but you have to follow a few rules of course. The order of the characters in a string
does matter. Each time you follow a rule to create a new string, you have "added" the new string to your "collection".
Rule 1: If you possess a string whose last letter is
I, you can add on a
U at the end.
Rule 2: Suppose you have
Mx. Then you may add
Mxx to your collection.
A lowercase x here represents a string of any size.
From
MIU, you may get
MIUIU.
From
MUM, you may get
MUMUM.
From
MUIUIM, you may get
MUIUIMUIUIM.
Rule 3: If
III occurs in one of the strings in your collection, you may make a new string with
U in place of
III.
From
UMIIIMU, you may get
UMUMU.
From
MIIII, you may get
MIU or
MUI.
From
IIMII, you may get nothing.
From
MIII, you may get
MU.
Rule 4: If
UU occurs inside one of the strings, you can drop it.
From
UUU, you may get
U.
From
MUUUIII, you may get
MUIII.
The opposites of these rules are not allowed, you can not replace
U with
III, etc. etc.
That's all the rules. Note that you do not have to follow a rule just because you can. If you have
UU in your string you do not have to drop it, likewise if you have
III in your string you do not have to replace it with
U.
MU puzzle solution