MU Puzzle

Hello everyone, I’ve been reading Gödel Escher Bach: An Eternal Golden Braid by Douglas Hofstadter for a while. The book contains many instances of recursion and self-reference, where objects and ideas speak about or refer back to themselves. Douglas Hofstadter’s book is concerned directly with the nature of “maps” or links between formal systems. However, according to Hofstadter, the formal system that underlies all mental activity transcends the system that supports it. If life can grow out of the formal chemical substrate of the cell, if consciousness can emerge out of a formal system of firing neurons, then so too will computers attain human intelligence. Gödel, Escher, Bach is a wonderful exploration of fascinating ideas at the heart of cognitive science: meaning, reduction, recursion, and much more.

The book is filled with puzzles, including Hofstadter’s famous MU puzzle. The MU puzzle is a puzzel started by Dougles Hofstadter and found in Gödel, Escher, Bach GEB involving a simple formal system called “MIU”. A starting string is given in the puzzle. With this starting string, it aims to reach the target string MU string.

The starting string will be MI. After that, some rules for changing the series will be told. If one of those rules is applicable at some point, and you want to use it, you may, but there is nothing that will dictate which rule you should use, in case there are several applicable rules. It’s up to you!

RULE -I If you possess a string whose last letter is I, you can add on a U at the end.

For example, MI and IM are two different strings. A string of symbols is not just a “bag” of symbols, in which the order doesn’t make any difference.

RULE -II Suppose you have Mx. Then you may add Mxx to your collection. What I mean by this is shown below, in a few examples.

From MIU, you may get MIUIU. ⟶ MIU, x = IU therefore; Mxx = MIUIU From MUM, you may get MUMUM. ⟶ MUM, x = UM therefore; Mxx = MUMUM From MU, you may get MUU. ⟶ MU, x = U therefore; Mxx = MUU

RULE -III If III occurs in one of the strings in your collection, you may make a new string with U in place of III. Examples:

From UMIIIMU, you could make UMUMU.

From MIIII, you could make MIU (also MUI. From IIMII, you can’t get anywhere using this rule. The three I’s have to be consecutive.)

From MIII, make MU. Don’t, under any circumstances, think you can run this rule backwards, as in the following example:

From MU, make MIII < — This is wrong. Rules are one-way!

RULE -IV If UU occurs inside one of your strings, you can drop it.

From UUU, get U.

From MUUUIII, get MUIII.

There you have it. Now you may begin trying to make MU!