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?

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.