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 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:
Solution 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. 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 I 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, in any string produced when starting with MI, the number of I is not divisible by 3:
In the beginning, the number of Is 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 MU with zero I cannot be achieved because 0 is divisible by 3. In the language of modular arithmetic, the number n of I obeys the congruence
n ≡ 2 a ≢ 0 ( mod 3 ) . {\displaystyle 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 MI by the above four rules if, and only if, x respects the three following properties:
x is only composed with one M and any number of I and U, x begins with M, and the number of I in x is not divisible by 3.
Proof Only if: No rule moves the M, changes the number of M, or introduces any character out of M, I, U. Therefore, every x derived from MI respects properties 1 and 2. As shown before, it also respects property 3. If: If x respects properties 1 to 3, let N I {\displaystyle N_{I}} and N U {\displaystyle N_{U}} be the number of I and U in x, respectively, and let N = N I + 3 N U {\displaystyle N=N_{I}+3N_{U}} . By property 3, the number N I {\displaystyle N_{I}} cannot be divisible by 3, hence, N {\displaystyle N} cannot be, either. That is, N ≡ 1 or N ≡ 2 ( mod 3 ) {\displaystyle N\equiv 1{\text{ or }}N\equiv 2{\pmod {3}}} . Let n ∈ N {\displaystyle n\in \mathbb {N} } such that 2 n > N {\displaystyle 2^{n}>N} and 2 n ≡ N ( mod 3 ) {\displaystyle 2^{n}\equiv N{\pmod {3}}} . Beginning from the axiom MI, applying the second rule n {\displaystyle n} times obtains MIII...I with 2 n {\displaystyle 2^{n}} I. Since 2 n − N {\displaystyle 2^{n}-N} is divisible by 3, by construction of n {\displaystyle n} , applying the third rule 2 n − N 3 {\displaystyle {\frac {2^{n}-N}{3}}} times will obtain MIII...IU...U, with exactly N {\displaystyle N} I, followed by some number of U. The U count can always be made even, by applying the first rule once, if necessary. Applying the fourth rule sufficiently often, all U can then be deleted, thus obtaining MIII...I with N I + 3 N U {\displaystyle N_{I}+3N_{U}} I. Applying the third rule to reduce triplets of I into a U in the right spots will obtain x. Altogether, x has been derived from MI.
Example To illustrate the construction in the If part of the proof, the string MIIUII, which respects properties 1 to 3, leads to N I = 4 {\displaystyle N_{I}=4} , N U = 1 {\displaystyle N_{U}=1} , N = 7 {\displaystyle N=7} , n = 4 {\displaystyle n=4} ; it can be hence derived as follows:
… excerpt ends here. Continue reading the full article.
