Having started reading Gödel, Escher, Bach: An Eternal Golden Braid, I decided to create an “explorer” for the MU puzzle described in chapter one. This is constructed using arbor.js – just click a node to perform all four transformation rules on it, and you will start to see the pattern of the graph.
From Wikipedia:
Suppose there are the symbols M, I, and U which can be combined to produce strings of symbols called “words”. The MU puzzle asks one to start with the “axiomatic” word MI and transform it into the word MU using in each step one of the following transformation rules:
1. Add a U to the end of any string ending in I. For example: MI to MIU.
2. Double any string after the M (that is, change Mx, to Mxx). For example: MIU to MIUIU.
3. Replace any III with a U. For example: MUIIIU to MUUU.
4. Remove any UU. For example: MUUU to MU.Using these four rules is it possible to change MI into MU in a finite number of steps?
One important flaw in my implementation is that for 3rd and 4th rules we parse the string left to right only. This limits the number of permutations created via these rules, but it doesn’t dramatically affect the result. This flaw was larger than I’d thought, but is corrected now.
Only tested in Chrome – probably will not work in IE.
See comments on reddit, find the source code on github.
