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 socalled 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.
 MU contains no I’s
 MU contains no I’s

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)

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
 ∴ There is no combination of rule applications that will eliminate all I’s from a string
 ∴ MU is underivable in the MIU system