MU puzzle facts for kids

The MU puzzle is a fun brain-teaser from the famous book Gödel, Escher, Bach by Douglas Hofstadter. It's about a simple set of rules for changing strings of letters. The puzzle challenges you to start with "MI" and turn it into "MU" using only these rules. It helps us understand how we think inside a system of rules versus thinking about the system itself.

The MU Puzzle: Can You Solve It?

Imagine you have three special letters: M, I, and U. You can combine these letters to make different strings, like MI or MIU.

The MU puzzle asks you to start with the string MI. Your goal is to change it into the string MU. You can only do this by following four special rules. You must use one rule at a time, step by step.

Here are the rules you can use:

• Rule 1: If a string ends with I, you can add a U to the end.

* Example: MI can become MIU.

• Rule 2: If a string starts with M, you can double whatever comes after the M.

* Example: MIU can become MIUIU.

• Rule 3: If you see three I's together (III), you can change them into a single U.

* Example: MUIIIU can become MUUU.

• Rule 4: If you see two U's together (UU), you can remove them completely.

* Example: MUUU can become MU.

Solving the MU Puzzle: Is It Possible?

It turns out that you cannot solve the MU puzzle. It's impossible to change MI into MU using only the rules given. This means MU is not something you can create within the MIU system.

To understand why, we need to think outside the puzzle's rules. We look for something that stays the same, no matter which rule we use. This unchanging thing is called an invariant.

In this puzzle, let's look at the total number of I's in a string.

• When you start with MI, you have one I.
• Rule 1 (add U to end) doesn't change the number of I's.
• Rule 2 (double the string after M) doubles the number of I's.
• Rule 3 (change III to U) reduces the number of I's by three.
• Rule 4 (remove UU) doesn't change the number of I's.

Notice that only Rule 2 and Rule 3 change the count of I's.

• Starting with 1 I, which is not divisible by 3.
• If you double a number that isn't divisible by 3, the new number still won't be divisible by 3. (For example, 1x2=2, 2x2=4, 4x2=8. None of these are divisible by 3).
• If you subtract 3 from a number that isn't divisible by 3, the new number still won't be divisible by 3. (For example, 4-3=1, 8-3=5).

So, the number of I's in any string you create will never be divisible by 3.

The goal string, MU, has zero I's. But zero is divisible by 3! Since you can only create strings where the number of I's is not divisible by 3, you can never reach MU.

What Does This Puzzle Teach Us?

The MIU system is like a simple formal system. This is a way to represent math or logic using symbols and rules.

• The starting string MI is like an axiom (a basic truth).
• The four rules are like rules of inference (ways to make new truths from old ones).

The fact that you can't make MU shows that some statements might not be provable within a formal system.

This puzzle also helps us see the difference between working inside a system (just following the rules) and thinking about the system (understanding its deeper meaning).

• When you're just following the rules, you don't know if MU is impossible. You might keep trying forever. This is like the "syntactic" level, where you only care about the symbols and rules.
• But when you step back and think about the puzzle, you realize the hidden rule about the number of I's and divisibility by 3. This is the "semantic" level, where you find meaning in the system.

This idea is similar to Gödel's incompleteness theorems, which show that even complex math systems might have true statements that cannot be proven within that system.

How This Puzzle Is Used

The MU puzzle is often used in textbooks to teach about important ideas in computer science and math. For example, Susanna S. Epp uses it in her book Discrete Mathematics with Applications to explain recursive definitions.

See also

In Spanish: Rompecabezas MU para niños