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.

The puzzle

Suppose there are the symbols <syntaxhighlight lang="text" class="" style="" inline="1">M</syntaxhighlight>, <syntaxhighlight lang="text" class="" style="" inline="1">I</syntaxhighlight>, and <syntaxhighlight lang="text" class="" style="" inline="1">U</syntaxhighlight> which can be combined to produce strings of symbols. The MU puzzle asks one to start with the "axiomatic" string <syntaxhighlight lang="text" class="" style="" inline="1">MI</syntaxhighlight> and transform it into the string <syntaxhighlight lang="text" class="" style="" inline="1">MU</syntaxhighlight> using in each step one of the following transformation rules:^[1]^[2]

Nr.	Formal rule^{[note 1]}			Informal explanation	Example
1.	x<syntaxhighlight lang="text" class="" style="" inline="1">I</syntaxhighlight>	→	x<syntaxhighlight lang="text" class="" style="" inline="1">IU</syntaxhighlight>	Add a <syntaxhighlight lang="text" class="" style="" inline="1">U</syntaxhighlight> to the end of any string ending in <syntaxhighlight lang="text" class="" style="" inline="1">I</syntaxhighlight>	<syntaxhighlight lang="text" class="" style="" inline="1">MI</syntaxhighlight>	to	<syntaxhighlight lang="text" class="" style="" inline="1">MIU</syntaxhighlight>
2.	<syntaxhighlight lang="text" class="" style="" inline="1">M</syntaxhighlight>x	→	<syntaxhighlight lang="text" class="" style="" inline="1">M</syntaxhighlight>xx	Double the string after the <syntaxhighlight lang="text" class="" style="" inline="1">M</syntaxhighlight>	<syntaxhighlight lang="text" class="" style="" inline="1">MIU</syntaxhighlight>	to	<syntaxhighlight lang="text" class="" style="" inline="1">MIUIU</syntaxhighlight>
3.	x<syntaxhighlight lang="text" class="" style="" inline="1">III</syntaxhighlight>y	→	x<syntaxhighlight lang="text" class="" style="" inline="1">U</syntaxhighlight>y	Replace any <syntaxhighlight lang="text" class="" style="" inline="1">III</syntaxhighlight> with a <syntaxhighlight lang="text" class="" style="" inline="1">U</syntaxhighlight>	<syntaxhighlight lang="text" class="" style="" inline="1">MUIIIU</syntaxhighlight>	to	<syntaxhighlight lang="text" class="" style="" inline="1">MUUU</syntaxhighlight>
4.	x<syntaxhighlight lang="text" class="" style="" inline="1">UU</syntaxhighlight>y	→	xy	Remove any <syntaxhighlight lang="text" class="" style="" inline="1">UU</syntaxhighlight>	<syntaxhighlight lang="text" class="" style="" inline="1">MUUU</syntaxhighlight>	to	<syntaxhighlight lang="text" class="" style="" inline="1">MU</syntaxhighlight>

Solution

The puzzle cannot be solved: it is impossible to change the string <syntaxhighlight lang="text" class="" style="" inline="1">MI</syntaxhighlight> into <syntaxhighlight lang="text" class="" style="" inline="1">MU</syntaxhighlight> 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 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 <syntaxhighlight lang="text" class="" style="" inline="1">I</syntaxhighlight> 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, the invariant property is that the number of <syntaxhighlight lang="text" class="" style="" inline="1">I</syntaxhighlight> is not divisible by 3:

In the beginning, the number of <syntaxhighlight lang="text" class="" style="" inline="1">I</syntaxhighlight>s 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 of <syntaxhighlight lang="text" class="" style="" inline="1">MU</syntaxhighlight> with zero <syntaxhighlight lang="text" class="" style="" inline="1">I</syntaxhighlight> cannot be achieved because 0 is divisible by 3.

In the language of modular arithmetic, the number n of <syntaxhighlight lang="text" class="" style="" inline="1">I</syntaxhighlight> obeys the congruence

n\equiv 2^{a}\not \equiv 0{\pmod {3}}.\,

where a counts how often the second rule is applied.

A decidable criterion for derivability

More generally, an arbitrarily given string x can be derived from <syntaxhighlight lang="text" class="" style="" inline="1">MI</syntaxhighlight> by the above four rules if, and only if, x respects the three following properties:

x is only composed with one <syntaxhighlight lang="text" class="" style="" inline="1">M</syntaxhighlight> and any number of <syntaxhighlight lang="text" class="" style="" inline="1">I</syntaxhighlight> and <syntaxhighlight lang="text" class="" style="" inline="1">U</syntaxhighlight>,
x begins with <syntaxhighlight lang="text" class="" style="" inline="1">M</syntaxhighlight>, and
the number of <syntaxhighlight lang="text" class="" style="" inline="1">I</syntaxhighlight> in x is not divisible by 3.

Proof

Only if: No rule moves the <syntaxhighlight lang="text" class="" style="" inline="1">M</syntaxhighlight>, changes the number of <syntaxhighlight lang="text" class="" style="" inline="1">M</syntaxhighlight>, or introduces any character out of <syntaxhighlight lang="text" class="" style="" inline="1">M</syntaxhighlight>, <syntaxhighlight lang="text" class="" style="" inline="1">I</syntaxhighlight>, <syntaxhighlight lang="text" class="" style="" inline="1">U</syntaxhighlight>. Therefore, every x derived from <syntaxhighlight lang="text" class="" style="" inline="1">MI</syntaxhighlight> respects properties 1 and 2. As shown before, it also respects property 3.

If: If x respects properties 1 to 3, let $N_{I}$ and $N_{U}$ be the number of <syntaxhighlight lang="text" class="" style="" inline="1">I</syntaxhighlight> and <syntaxhighlight lang="text" class="" style="" inline="1">U</syntaxhighlight> in x, respectively, and let $N=N_{I}+3N_{U}$ . By property 3, the number $N_{I}$ cannot be divisible by 3, hence, $N$ cannot be, either. That is, $N\equiv 1{\text{ or }}N\equiv 2{\pmod {3}}$ . Let $n\in \mathbb {N}$ such that $2^{n}>N$ and $2^{n}\equiv N{\pmod {3}}$ .^{[note 2]} Beginning from the axiom <syntaxhighlight lang="text" class="" style="" inline="1">MI</syntaxhighlight>, applying the second rule $n$ times obtains <syntaxhighlight lang="text" class="" style="" inline="1">MIII</syntaxhighlight>...<syntaxhighlight lang="text" class="" style="" inline="1">I</syntaxhighlight> with $2^{n}$ <syntaxhighlight lang="text" class="" style="" inline="1">I</syntaxhighlight>. Since $2^{n}-N$ is divisible by 3, by construction of $n$ , applying the third rule ${\frac {2^{n}-N}{3}}$ times will obtain <syntaxhighlight lang="text" class="" style="" inline="1">MIII</syntaxhighlight>...<syntaxhighlight lang="text" class="" style="" inline="1">IU</syntaxhighlight>...<syntaxhighlight lang="text" class="" style="" inline="1">U</syntaxhighlight>, with exactly $N$ <syntaxhighlight lang="text" class="" style="" inline="1">I</syntaxhighlight>, followed by some number of <syntaxhighlight lang="text" class="" style="" inline="1">U</syntaxhighlight>. The <syntaxhighlight lang="text" class="" style="" inline="1">U</syntaxhighlight> count can always be made even, by applying the first rule once, if necessary. Applying the fourth rule sufficiently often, all <syntaxhighlight lang="text" class="" style="" inline="1">U</syntaxhighlight> can then be deleted, thus obtaining <syntaxhighlight lang="text" class="" style="" inline="1">MIII</syntaxhighlight>...<syntaxhighlight lang="text" class="" style="" inline="1">I</syntaxhighlight> with $N_{I}+3N_{U}$ <syntaxhighlight lang="text" class="" style="" inline="1">I</syntaxhighlight>. Applying the third rule to reduce triplets of <syntaxhighlight lang="text" class="" style="" inline="1">I</syntaxhighlight> into a <syntaxhighlight lang="text" class="" style="" inline="1">U</syntaxhighlight> in the right spots will obtain x. Altogether, x has been derived from <syntaxhighlight lang="text" class="" style="" inline="1">MI</syntaxhighlight>.

Example

To illustrate the construction in the If part of the proof, the string <syntaxhighlight lang="text" class="" style="" inline="1">MIIUII</syntaxhighlight>, which respects properties 1 to 3, leads to $N_{I}=4$ , $N_{U}=1$ , $N=7$ , $n=4$ ; it can be hence derived as follows:

<syntaxhighlight lang="text" class="" style="" inline="1">MI</syntaxhighlight> <syntaxhighlight lang="text" class="" style="" inline="1">MII</syntaxhighlight> <syntaxhighlight lang="text" class="" style="" inline="1">MIIII</syntaxhighlight> <syntaxhighlight lang="text" class="" style="" inline="1">MIIIIIIII</syntaxhighlight> <syntaxhighlight lang="text" class="" style="" inline="1">MIIIIIIIIIIIIIIII</syntaxhighlight> <syntaxhighlight lang="text" class="" style="" inline="1">MIIIIIIIUIIIIII</syntaxhighlight> <syntaxhighlight lang="text" class="" style="" inline="1">MIIIIIIIUUIII</syntaxhighlight> <syntaxhighlight lang="text" class="" style="" inline="1">MIIIIIIIUUIIIU</syntaxhighlight> <syntaxhighlight lang="text" class="" style="" inline="1">MIIIIIIIUUUU</syntaxhighlight> <syntaxhighlight lang="text" class="" style="" inline="1">MIIIIIIIUU</syntaxhighlight> <syntaxhighlight lang="text" class="" style="" inline="1">MIIIIIII</syntaxhighlight> <syntaxhighlight lang="text" class="" style="" inline="1">MIIUII</syntaxhighlight>.

Arithmetization

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 <syntaxhighlight lang="text" class="" style="" inline="1">M</syntaxhighlight>, <syntaxhighlight lang="text" class="" style="" inline="1">I</syntaxhighlight>, and <syntaxhighlight lang="text" class="" style="" inline="1">U</syntaxhighlight> to the numbers 3, 1, and 0, respectively. (For example, the string <syntaxhighlight lang="text" class="" style="" inline="1">MIUIU</syntaxhighlight> would be mapped to 31010.)

Second, the single axiom of the MIU system, namely the string <syntaxhighlight lang="text" class="" style="" inline="1">MI</syntaxhighlight>, 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 × 10^m + n	→	10^m × (3 × 10^m + n) + n	310	→	31010	(m = 2, n = 10)
3.	k × 10^m+3 + 111 × 10^m + n	→	k × 10^{m + 1} + n	3111011	→	30011	(k = 3, m = 3, n = 11)
4.	k × 10^m+2 + n	→	k × 10^m + 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 variable m was reserved for use in exponents of 10 only, and therefore it was replaced by k 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.)

Relationship to logic

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 MI string is akin to a single axiom, and the four transformation rules are akin to rules of inference.

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.

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 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. One then "jumps out of the system" and starts to reason about the system, rather than working within it. Eventually, one realises that the system is in some way about 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 behind Gödel's Incompleteness Theorem.

Pedagogical uses

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.^[3]

Notes

^ Here, x and y are variables, standing for strings of symbols. A rule may be applied only to the whole string, not to an arbitrary substring.
^ Such an $n$ always exists, since the powers of 2 alternatingly evaluate to 1 and 2, modulo 3.
^ Here, k and m stand for arbitrary natural numbers, and n is any natural number smaller than 10^m. Each rule of the form "x → y" should be read as "if we have made x we can make y." As the Example column illustrates, a rule may be applied only to an entire MIU-number, not to an arbitrary part of its decimal representation.

References

^ Justin Curry / Curran Kelleher (2007). Gödel, Escher, Bach: A Mental Space Odyssey. MIT OpenCourseWare.
^ Hofstadter, Douglas R. (1999) [1979], Gödel, Escher, Bach: An Eternal Golden Braid, Basic Books, ISBN 0-465-02656-7 Here: Chapter I.
^ Discrete Mathematics with Applications, Third Edition, Brooks/Cole, 2004. Chapter 8.4, "General Recursive Definitions," p. 501.

External links

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

[3] Here, x and y are variables, standing for strings of symbols. A rule may be applied only to the whole string, not to an arbitrary substring.

[4] Such an $n$ always exists, since the powers of 2 alternatingly evaluate to 1 and 2, modulo 3.

[5] Here, k and m stand for arbitrary natural numbers, and n is any natural number smaller than 10^m. Each rule of the form "x → y" should be read as "if we have made x we can make y." As the Example column illustrates, a rule may be applied only to an entire MIU-number, not to an arbitrary part of its decimal representation.

[1] Justin Curry / Curran Kelleher (2007). Gödel, Escher, Bach: A Mental Space Odyssey. MIT OpenCourseWare.

[2] Hofstadter, Douglas R. (1999) [1979], Gödel, Escher, Bach: An Eternal Golden Braid, Basic Books, ISBN 0-465-02656-7 Here: Chapter I.

[6] Discrete Mathematics with Applications, Third Edition, Brooks/Cole, 2004. Chapter 8.4, "General Recursive Definitions," p. 501.

[1]

[2]

[note 1]

[note 2]

[note 3]

[3]

v t e Douglas Hofstadter
Books	Gödel, Escher, Bach (1979) The Mind's I (1981)¹ Metamagical Themas (1985) Fluid Concepts and Creative Analogies (1995)² Le Ton beau de Marot (1997) I Am a Strange Loop (2007) Surfaces and Essences (2013)
Concepts and projects	Ambigram BlooP and FlooP Copycat Hofstadter's butterfly Hofstadter's law Hofstadter points MU puzzle Platonia dilemma Six nines in pi Strange loop Superrationality
Related	Robert Hofstadter (father) Egbert B. Gebstadter Indiana University Bloomington Victim of the Brain
¹ Edited by Hofstadter and Daniel C. Dennett ² By Hofstadter and the Fluid Analogies Research Group