# Can you Turn MI to MU?

Using the letters M, I, and U, which can be used to create words. Can you turn MI into MU using in each step one of the following rules:

• Insert a U to the end of a word ending in I. e.g: MI becomes MIU.

• Re-insert the letters after the M e.g: MIU to MIUIU.

• Replace the letters III with a U. e.g: MUIIIU to MUUU.

• Get rid of letters UU. For example: MUUU to MU.

Can you use the 4 rules to change the word MI into MU? If so how many does it take?

This is the MU-Puzzle from one of my favourite books Gödel, Escher, Bach.

The solution is here:

No. It is impossible. The number of Is in the string will never be evenly divisible by 3. You need it to be so that rule 3 can reduce it to 0 and thus acheive the goal. We start with 1 I. We may only double it in the hopes of making it a multiple of 3 - no power of 2 is a multiple of 3 - nor is any number not already a multiple of 3 by any power of 2 divisible by 3. Since we start at 1, it cannot be done.

• You just plagiarized the Wikipedia :O put that into your own words! – warspyking Oct 26 '14 at 18:07
• @warspyking I reworded it :p good job finding puzzles not already on here btw – d'alar'cop Oct 26 '14 at 18:14
• I searched "Impossible Puzzles" and graves the only 2 good-looking ones on the Wikipedia list. Infact my question came from the same page as your answer. – warspyking Oct 26 '14 at 18:44
• Usually the puzzles that are declared as "impossible" on the Internet are ones everyone has heard of before. – Joe Z. Oct 26 '14 at 20:18
• Though remember the point of this puzzle is not to solve it but to recognize two properties of formal systems: They don't need an interpretation as a mathematical theory (thus nobody is tempted to suggest that the string MU is "false", and nor should you do so for the strings of TNT) and secondly, that facts about formal systems may be proved informally, as is done here to show that MU is not a producible string (as later the book will consider a string of TNT that is not producible, but which has a True interpetation) – James K Oct 26 '14 at 22:16

Start by ignoring the Us. Let NI be the number of Is. The only rule that will get rid of Is is rule 3 and it only works on triplets. So we need to have NI become 3*n somehow as we need all Is gone. Rule 1 will not change NI. Rule 2 will double NI, but doubling a number will never make it divisible by 3 unless it was so in the first place, so that is not going to help us either (this is easy to prove if you compute modulo 3). Rule 3 will only make NI divisible by 3 if it was so in the first place. Rule 4 only deals with Us. So given that NI can never become divisible by 3 you can never get rid of all the Is => Impossible.

MI - Axiom
MII - Rule 2
MIIII - Rule 2
MUI - Rule 3
MUIU - Rule 1
MUIUUIU - Rule 2
MUIUUIUUIUUIU - Rule 2
MUIIIU - Rule 4
MUUU Rule 3
MU - Rule 4

• Your 4th-last step is missing an I – boboquack Mar 13 '18 at 4:39