TheMU puzzle is a puzzle stated byDouglas Hofstadter and found inGö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 aPost canonical system and can be reformulated as astring rewriting system.

Suppose there are the symbolsM,I, andU which can be combined to produce strings of symbols. The MU puzzle asks one to start with the "axiomatic" stringMI and transform it into the stringMU using in each step one of the following transformation rules:^[1][2]

Nr.	Formal rule[note 1]			Informal explanation	Example
1.	xI	→	xIU	Add aU to the end of any string ending inI	MI	to	MIU
2.	Mx	→	Mxx	Double the string after theM	MIU	to	MIUIU
3.	xIIIy	→	xUy	Replace anyIII with aU	MUIIIU	to	MUUU
4.	xUUy	→	xy	Remove anyUU	MUUU	to	MU

The puzzle cannot be solved: it is impossible to change the stringMI intoMU 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.

In order to prove assertions like this, it is often beneficial to look for aninvariant; that is, some quantity or property that doesn't change while applying the rules.

In this case, one can look at the total number ofI in a string. Only the second and third rules change this number. In particular, rule two will double it while rule three will reduce it by 3. Now, theinvariant property is that, in any string produced when starting withMI, the number ofI is notdivisible by 3:

• In the beginning, the number ofIs is 1 which is not divisible by 3.
• Doubling a number that is not divisible by 3 does not make it divisible by 3.
• Subtracting 3 from a number that is not divisible by 3 does not make it divisible by 3 either.

Thus, the goal ofMU with zeroI cannot be achieved because 0is divisible by 3.

In the language ofmodular arithmetic, the numbern ofI obeys the congruence

${\displaystyle n\equiv 2^a\not\equiv 0(\mathrm{mod}3).}$

wherea counts how often the second rule is applied.

More generally, an arbitrarily given stringx can be derived fromMI by theabove four rulesif, and only if,x respects the three following properties:

1. x is only composed with oneM and any number ofI andU,
2. x begins withM, and
3. the number ofI inx is not divisible by 3.

Only if: No rule moves theM, changes the number ofM, or introduces any character out ofM,I,U. Therefore, everyx derived fromMI respects properties 1 and 2. As shownbefore, it also respects property 3.

If: Ifx respects properties 1 to 3, let${\displaystyle N_I}$ and${\displaystyle N_U}$ be the number ofI andU inx, respectively, and let${\displaystyle N=N_I+3N_U}$.By property 3, the number${\displaystyle N_I}$ cannot be divisible by 3, hence,${\displaystyle N}$ cannot be, either. That is,${\displaystyle N\equiv 1\text{ or }N\equiv 2(\mathrm{mod}3)}$. Let${\displaystyle n\in \mathbb{N}}$ such that${\displaystyle 2^n>N}$ and${\displaystyle 2^n\equiv N(\mathrm{mod}3)}$.^{[note 2]} Beginning from the axiomMI, applying the second rule${\displaystyle n}$ times obtainsMIII...I with${\displaystyle 2^n}$I. Since${\displaystyle 2^n-N}$ is divisible by 3, by construction of${\displaystyle n}$, applying the third rule${\displaystyle \frac{2^n-N}{3}}$ times will obtainMIII...IU...U, with exactly${\displaystyle N}$I, followed by some number ofU. TheU count can always be made even, by applying the first rule once, if necessary. Applying the fourth rule sufficiently often, allU can then be deleted, thus obtainingMIII...I with${\displaystyle N_I+3N_U}$I. Applying the third rule to reduce triplets ofI into aU in the right spots will obtainx. Altogether,x has been derived fromMI.

To illustrate the construction in theIf part of the proof, the stringMIIUII, which respects properties 1 to 3, leads to${\displaystyle N_I=4}$,${\displaystyle N_U=1}$,${\displaystyle N=7}$,${\displaystyle n=4}$; it can be hence derived as follows:

MI2→MII2→MIIII2→MIIIIIIII2→MIIIIIIIIIIIIIIII3→MIIIIIIIUIIIIII3→MIIIIIIIUUIII1→MIIIIIIIUUIIIU3→MIIIIIIIUUUU4→MIIIIIIIUU4→MIIIIIII3→MIIUII.

Chapter XIX ofGö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 lettersM,I, andU to the numbers 3, 1, and 0, respectively. (For example, the stringMIUIU would be mapped to 31010.)

Second, the single axiom of the MIU system, namely the stringMI, becomes the number 31.

Third, the four formal rules given above become the following:

Nr.	Formal rule[note 3]			Example
1.	k × 10 + 1	→	10 × (k × 10 + 1)	31	→	310	(k = 3)
2.	3 × 10m +n	→	10m × (3 × 10m +n) +n	310	→	31010	(m = 2,n = 10)
3.	k × 10m+3 + 111 × 10m +n	→	k × 10m + 1 +n	3111011	→	30011	(k = 3,m = 3,n = 11)
4.	k × 10m+2 +n	→	k × 10m +n	30011	→	311	(k = 3,m = 2,n = 11)

(NB: The rendering of the first rule above differs superficially from that in the book, where it is written as "[i]f we have made 10m + 1, then we can make 10 × (10m + 1)". Here, however, the variablem was reserved for use in exponents of 10 only, and therefore it was replaced byk in the first rule. Also, in this rendering, the arrangement of factors in this rule was made consistent with that of the other three rules.)

This sectionneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources in this section. Unsourced material may be challenged and removed.(July 2013) (Learn how and when to remove this message)

The MIU system illustrates several important concepts in logic by means of analogy.

It can be interpreted as an analogy for aformal system — an encapsulation of mathematical and logical concepts using symbols. The MI string is akin to a singleaxiom, and the four transformation rules are akin torules of inference.

The MU string and the impossibility of its derivation is then analogous to a statement of mathematical logic which cannot beproven or disproven by the formal system.

It also demonstrates the contrast between interpretation on the "syntactic" level of symbols and on the "semantic" level of meanings. On the syntactic level, there is no knowledge of the MU puzzle's insolubility. The system does notrefer 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. One then "jumps out of the system" and starts to reasonabout the system, rather than working within it. Eventually, one realises that the system is in some wayabout divisibility by three. This is the "semantic" level of the system — a level of meaning that the system naturally attains. On this level, the MU puzzle can be seen to be impossible.

The inability of the MIU system to express or deduce facts about itself, such as the inability to derive MU, is a consequence of its simplicity. However, more complex formal systems, such as systems of mathematical logic, may possess this ability. This is the key idea behindGödel's Incompleteness Theorem.

In her textbook,Discrete Mathematics with Applications,Susanna S. Epp uses the MU puzzle to introduce the concept ofrecursive definitions, and begins the relevant chapter with a quote fromGEB.^[3]

• Invariant (mathematics)
• Unrestricted grammar

• "Hofstadter's MIU System". Archived fromthe original on 4 March 2016. Retrieved29 November 2016. An online interface for producing derivations in the MIU System.
• "MU Puzzle". Archived fromthe original on 14 May 2018. Retrieved13 May 2018. An online JavaScript implementation of the MIU production system.

• Logic puzzles
• Unsolvable puzzles
• Independence results
• Formal languages
• 1979 introductions

• Articles with short description
• Short description matches Wikidata
• Articles needing additional references from July 2013
• All articles needing additional references