MU Puzzle (D. Hofstadter, U of Indiana)


Given the string MI, can you produce the string MU using the following set of rules ?

Rule 1:If you possess a string whose last letter is I, you can add on a U at the end

Example: MIII yields MIIIU

Rule 2:Suppose you have Mx, where x represents the entire string of letters following the M. Then you may add an x to the end of your string.

MIU yields MIUIU

Rule 3:If III occurs in the string, you may replace it with U.

MIII yields MU
MIIIU yields MUU

Rule 4:If UU occurs inside the string, you may drop it.

MUUI yields MI
MIUU yields MI

A Longer Example:

MII  by rule 2
MIIII by rule 2
MUI by rule 3
MUIU by rule 1
MUIUUIU by rule 2
MUIIU by rule 4