MU Puzzle - The Puzzle

The Puzzle

Suppose there are the symbols M, I, and U which can be combined to produce strings of symbols called "words". The MU puzzle asks one to start with the "axiomatic" word MI and transform it into the word MU using in each step one of the following transformation rules:

  1. Add a U to the end of any string ending in I. For example: MI to MIU.
  2. Double any string after the M (that is, change Mx, to Mxx). For example: MIU to MIUIU.
  3. Replace any III with a U. For example: MUIIIU to MUUU.
  4. 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?

The production rules can be written in a more schematic way. Suppose x and y behave as variables (standing for strings of symbols). Then the production rules can be written as:

  1. xI → xIU
  2. Mx → Mxx
  3. xIIIy → xUy
  4. xUUy → xy

Is it possible to obtain the word MU using these rules?

Read more about this topic:  MU Puzzle

Famous quotes containing the word puzzle:

    “Scholars and artists thrown together are often annoyed at the puzzle of where they differ. Both work from knowledge; but I suspect they differ most importantly in the way their knowledge is come by. Scholars get theirs with conscientious thoroughness along projected lines of logic; poets theirs cavalierly and as it happens in and out of books. They stick to nothing deliberately, but let what will stick to them like burrs where they walk in the fields.”
    —Robert Frost (1874–1963)

    “What are you now? If we could touch one another,
    if these our separate entities could come to grips,
    clenched like a Chinese puzzle . . . yesterday
    I stood in a crowded street that was live with people,
    and no one spoke a word, and the morning shone.
    Everyone silent, moving. . . . Take my hand. Speak to me.”
    —Muriel Rukeyser (1913–1980)