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.
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:[1][2] 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.
In order to prove assertions like this, it is often beneficial to look for an invariant; that is, some quantity or property that doesn't change while applying the rules.
In the language of modular arithmetic, the number n of I obeys the congruence where a counts how often the second rule is applied.
More generally, an arbitrarily given string x can be derived from MI by the above four rules if, and only if, x respects the three following properties: Only if: No rule moves the M, changes the number of M, or introduces any character out of M, I, U.
[note 2] Beginning from the axiom MI, applying the second rule
Applying the fourth rule sufficiently often, all U can then be deleted, thus obtaining MIII...I with
Applying the third rule to reduce triplets of I into a U in the right spots will obtain x.
To illustrate the construction in the If part of the proof, the string MIIUII, which respects properties 1 to 3, leads to
; it can be hence derived as follows: Chapter XIX of Gödel, Escher, Bach gives a mapping of the MIU system to arithmetic, as follows.
First, every MIU-string can be translated to an integer by mapping the letters M, I, and U to the numbers 3, 1, and 0, respectively.
Second, the single axiom of the MIU system, namely the string MI, becomes the number 31.
Here, however, the variable m was reserved for use in exponents of 10 only, and therefore it was replaced by k in the first rule.
The MIU system illustrates several important concepts in logic by means of analogy.
It can be interpreted as an analogy for a formal system — an encapsulation of mathematical and logical concepts using symbols.
The MU string and the impossibility of its derivation is then analogous to a statement of mathematical logic which cannot be proven or disproven by the formal system.
On the syntactic level, there is no knowledge of the MU puzzle's insolubility.
The system does not refer to anything: it is simply a game involving meaningless strings.
Working within the system, an algorithm could successively generate every valid string of symbols in an attempt to generate MU, and though it would never succeed, it would search forever, never deducing that the quest was futile.
For a human player, however, after a number of attempts, one soon begins to suspect that the puzzle may be impossible.
This is the key idea behind Gödel's Incompleteness Theorem.
In her textbook, Discrete Mathematics with Applications, Susanna S. Epp uses the MU puzzle to introduce the concept of recursive definitions, and begins the relevant chapter with a quote from GEB.