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