Here’s a funny problem that you may probably know if you read Douglas Hofstadter’s wonderful book, Gödel, Escher, Bach. You are given a small alphabet, which consists in the letters M, U and I, and a set of four rules, where x and y denote any string:
- xI to xIU: append U at the end of a string that ends with I;
- Mx to Mxx: append the string after M a second time;
- xIIIy to xUy: replace III with U;
- xUUy to xy: remove UU.
Let’s start with the string MI. The goal is to convert this string to MU using those rules, that you can reuse at will. I can’t remember where I saw this problem mentioned on the internet. There is no solution to this problem, but I keep thinking of this gorgeous book each time I see some mention of Hofstadter’s puzzles.