MU puzzle

From Wikipedia, the free encyclopedia

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.

[edit] 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:

1. At the end of any string ending in I, you can add a U, such as changing MI to MIU.
2. You can double any string after the M (that is, change Mx, to Mxx, such as changing MIU to MIUIU.
3. You can replace any III with a U, such as changing MUIIIU to MUUU.
4. You can remove any UU, such as changing MUUU to MU.

Using these 4 rules, how can we change MI, to MU?

[edit] 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.