MU puzzle

The MU puzzle is a puzzle stated by Douglas Hofstadter and found in Gödel, Escher, Bach involving a simple formal system called "MIU". Hofstadter's motivation is to contrast reasoning within a formal system (i.e., deriving theorems) against reasoning about the formal system itself. MIU is an example of a Post canonical system and can be reformulated as a string rewriting system. Suppose there are the symbols M, I, and U which can be combined to produce strings of symbols. The MU puzzle asks one to start with the "axiomatic" string MI and transform it into the string MU using in each step one of the following transformation rules: The puzzle cannot be solved: it is impossible to change the string MI into MU by repeatedly applying the given rules. In other words, MU is not a theorem of the MIU formal system. To prove this, one must step "outside" the formal system itself. To prove assertions like this, it is often helpful to look for an invariant; that is, some quantity or property that doesn't change while applying the rules. In this case, one can look at the total number of I in a string. Only the second and third rules change this number.