I'm giving you a word for free, MI, which you can transform into others according to the following rules:
- Add a U to the end of any string ending in I. For example:
MI -> MIU
- Double any string after the M (that is, change Mx, to Mxx). For example:
MIU -> MIUIU
- Replace any III with a U. For example:
MUIIIU -> MUUU
- Remove any UU. For example:
MUUU -> MU
Using these four rules is it possible to change MI into MU in a finite number of steps?
The MU puzzle is a puzzle stated by Douglas Hofstadter and found in Gödel, Escher, Bach.