The Simple Mathematical Philosophy of Life, The Universe, and Everything
Tuesday, April 29, 2014
Moved to main blog!
Anyway, if you want to find more of the content that I was going to put on here, check out the schoolwork tag on my main blog.
Thursday, February 20, 2014
MIU Haskellized
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!