MU puzzle

The MU puzzle is a puzzle stated by Douglas Hofstadter and is found in "Gödel, Escher, Bach". As stated, it is an example of a Post canonical system and can be reformulated as a term rewriting system.

The puzzle

Let's suppose to have the symbols M, I, and U which can be combined to produce strings of symbols or "words". The "MU puzzle" asks to start with a the "axiomatic" word MI and transform it into the word MU using in each step one of the following transformation rules:
# At the end of any string ending in I, you can add a U, such as changing MI to MIU.
# You can double any string after the M (that is, change Mx, to Mxx), such as changing MIU to MIUIU.
# You can replace any III with a U, such as changing MUIIIU to MUUU.
# You can remove any UU, such as changing MUUU to MU.Using these 4 rules is it possible to change MI into MU in a finite number of steps?

We can write the production rules in a more schematic way. Suppose x and y behave as variables (standing for a string of symbols) then the production rules can be written as:
# xI → xIU
# Mx → Mxx
# xIIIy → xUy
# xUUy → xycan we obtain the word MU, using these rules?

Solution

The puzzle's solution is no. None of the rules allows us to create a string whose total number of "I"s is a multiple of three, except by starting with another such string. Since we can only start with "MI" which contains one "I", we can never produce such a string. In particular, we can never produce a string containing no "I"s, such as "MU".

To see this, notice that the only rule which allows us to add "I"s to our string is rule 2, which will double the number of "I"s in the string, while the only rule which allows us to remove "I"s from our string is rule 3, which will remove 3 "I"s from the string.

Thus, the total number of "I"s in a string must be of the form

:$i\; cdot\; 2^\{a\}\; -3b$

where $a$ and $b$ are constants, and $i$ is the number of "I"s in our axiom. For example, for the axiom MI, $i\; =\; 1$. Now, consider the above equation modulo 3. Since "3" unicode|≡ "0" (mod "3"), and "2" unicode|≡ "-1" (mod "3"), we can express the number of "I"s in our string (modulo 3) as

:$i\; cdot\; (-1)^\{a\}\; pmod\; 3$.

Clearly, this equation is congruent to zero (mod 3) if and only if $i$ is also congruent to 0 (mod 3), but because $i$ is congruent to 1 given the axiom MI, a string without "I"s, (in particular, MU), cannot be formed.

ee also

*Invariant (computer science)