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.
These can be applied in any way and any order, so long as the starting string is MI or derivable from MI
The challenge is to construct MU. This is provably impossible. Here's my proof:
1) MU contains no I's
2) Lemma: You can only eliminate all I's from a string if the number of I's is a multiple of three
a) The only way to remove I's is to convert them to U's3) Lemma: There is no string of multiplications by 2 and subtractions of 3 that will generate a multiple of 3
b) I's can only be converted to U's in groups of 3
c) ∴ You can only eliminate all I's if the number of I's ≡ 0 (mod 3)
a) ∀ x. x - 3 ≡ x (mod 3)4) ∴ There is no combination of rule applications that will eliminate all I's from a string
b) 0 * 2 ≡ 0 (mod 3)
c) 1 * 2 ≡ 2 (mod 3)
d) 2 * 2 ≡ 1 (mod 3)
e) ∴ by exhaustion, there is no string of multiplications by 2 and subtractions of 3 that will generate a multiple of 3
5) ∴ MU is underivable in the MIU system
Anyway, here's my code for manipulating MIU strings. Have fun!