Tuesday, April 29, 2014

Moved to main blog!

This blog isn't going to be seeing use anymore - I'd delete it but there are already some links to it out there that I wouldn't want people to break.
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's
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)
3) Lemma: There is no string of multiplications by 2 and subtractions of 3 that will generate a multiple of 3
a) ∀ x. x - 3 ≡ x (mod 3)
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
4) ∴ There is no combination of rule applications that will eliminate all I's from a string
5) ∴ MU is underivable in the MIU system

Anyway, here's my code for manipulating MIU strings. Have fun!