Weekly puzzle 20/5

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?

Tags: