MIU Haskellized

Posted on March 6, 2014
Note: crosspost from here, I originally planned to keep that blog separate but on thinking more about it I realized that’s stupid.

One of the first formal systems that Hofstadter introduces in the book is the so-called MIU system. It consists of four rules that can be used to transform a string of M’s, I’s, and U’s:
Add a U to the end of any string ending in I. For example: MI to MIU.
Double the string after the M (that is, change Mx, to Mxx). For example: MIU to MIUIU.
Replace any III with a U. For example: MUIIIU to MUUU.
Remove any UU. For example: MUUU to MU.
  1. MU contains no I’s
  2. MU contains no I’s
  3. Lemma: You can only eliminate all I’s from a string if the number of I’s is a multiple of three
    • the only way to remove I’s is to convert them to U’s
    • I’s can only be converted to U’s in groups of 3
    • ∴ You can only eliminate all I’s if the number of I’s ≡ 0 (mod 3)
  4. Lemma: There is no string of multiplications by 2 and subtractions of 3
    • ∀ x. x - 3 ≡ x (mod 3)
    • 0 * 2 ≡ 0 (mod 3)
    • 1 * 2 ≡ 2 (mod 3)
    • 2 * 2 ≡ 1 (mod 3)
    • ∴ by exhaustion, there is no string of multiplications by 2 and subtractions of 3 that will generate a multiple of 3
  5. ∴ There is no combination of rule applications that will eliminate all I’s from a string
  6. ∴ MU is underivable in the MIU system
Anyway, here’s my code for manipulating MIU strings. Have fun!