This week's puzzle comes to us from Godel, Escher, Bach by Douglas Hofstadter, because I'm too zonked to find anything proper.
Suppose there are the symbols M, I, and U which can be combined to produce strings of symbols called "words". We also have the following rules for transformations of words:
- Add a U to the end of any string ending in I. For example: MI to MIU.
- Double any string after the M (that is, change Mx, to Mxx). For example: MIU to MIUIU.
- Replace any III with a U. For example: MUIIIU to MUUU.
- Remove any UU. For example: MUUU to MU.
Using these four rules is it possible to change MI into MU in a finite number of steps?