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
We have the symbols M, I, and U. Suppose x and y behave as variables (standing for a string of symbols). Then the MU puzzle asks, given the axiomatic word MI, and the production rules:
- xI → xIU
- Mx → Mxx
- xIIIy → xUy
- xUUy → xy,
can we obtain the word MU, using these rules? More simply put:
- 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?
Solution
The puzzle's solution is no. None of the rules allows us to create a string whose total number of Is 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 Is, 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
- <math> i \cdot 2^{a} -3b </math>
where <math> a </math> and <math> b </math> are constants, and <math> i </math> is the number of "I"s in our axiom. For example, for the axiom MI, <math> i = 1 </math>. Now, consider the above equation Modulo 3. Since 3 ≡ 0 (mod 3), and 2 ≡ -1 (mod 3), we can express the number of "I"s in our string (modulo 3) as
- <math> i \cdot (-1)^{a} \pmod 3 </math>.
Clearly, this equation is congruent to zero (mod 3) if and only if <math> i </math> is also congruent to 0 (mod 3), but because <math> i </math> is congruent to 1 given the axiom MI, a string without "I"s, (in particular, MU), cannot be formed.
