I’ve just started reading Gödel, Escher, Bach: An Eternal Golden Braid by Douglas Hofstadter. Though I’m only a couple chapters in, it’s a really interesting read, and I highly recommend it.
In the second chapter, Hofstadter introduces the MU Puzzle. You are given a starting string, MI, and must obtain MU by using any combination of the following four rules:
- If you have a string ending in I, you can obtain that string with U appended. So if you have MI you can get MIU, and if you have MUII you can get MUIIU.
- If you have a string Mx, where x is any string, you can obtain Mxx. So if you have MI you can get MII, and if you have MUM you can get MUMUM.
- If you have a string containing three consecutive I’s, you can obtain the string that replaces them with a single U. So if you have MIIIU you can get MUU, and if you have MUIIIMU, you can get MUUMU.
- If you have a string containing two consecutive U’s, you can obtain the string that deletes them. So if you have MUUIU, you can get MIU, and if you have MUMUU you can get MUM.
Also note that you “obtain” strings because once you generate them, you have them in your possession for the duration of the puzzle. That is, if you have MI and generate MIU, then you can also generate MII, because you still have MI. You can’t lose strings.
If you’d like to play around with this and try your hand at solving the puzzle, you should stop reading now, because I’m going to start discussing the techniques I used to solve it.
If you start playing around with the strings, you should quickly realize that the M at the beginning of your starting string cannot be modified in any way. In fact, you can just get rid of it. In that case, the only rule that changes is Rule 2, which essentially becomes “you can concatenate a string with itself.” In the end, this ends up being a somewhat unimportant observation, but it is an interesting one.
But back to solving the puzzle. The only way to eliminate I’s is to do so by Rule 3. And in particular, we need to eliminate all of the I’s in a string to get even the possibility of a string that reduces to MU. This is a key observation to make. Why? Because in order to eliminate all of the I’s, we have to get the number of I’s in the string to some multiple of 3.
Notice also that Rule 2 is the only way to add I’s to the string. Furthermore, you can’t add I’s in any number you want; you can only double the number of I’s currently in the string. Since you start out with a single I and can only double the numbers, if you never eliminate I’s, the number of I’s in your string will always be 1 or 2 mod 3. This is because 2*1 mod 3 = 2 mod 3, and 2*2 mod 3 = 1 mod 3.
But notice that if you eliminate I’s, you can only do so three at a time, which means that the number of I’s in your string will always be 1 or 2 mod 3. Thus we can never get the number of I’s in the string to be some multiple of 3, and thus we can never eliminate all of the I’s. Therefore, this puzzle can’t be solved.
This is a really neat puzzle, because it requires careful thought about what the rules imply. In essence, you’re deriving strings based on a set of predefined rules, and Hofstadter’s point is that these rules do not allow you to generate even a string a simple as MU. But to see this, you have to think about what conditions need to be satisfied in order to solve the problem, and then observe that these conditions can never be satisfied.
I hope this inspires you to check out the book, and I hope that the rest of it is as thought-provoking and fun as this puzzle was.