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!

3 comments:

  1. Errrmmm... where is the code? 1am here so may be missing something obvious - Cheers! :-)

    ReplyDelete
    Replies
    1. It should be there now - something went funny with Github's embedding url when I changed usernames, it should be working now
      Also, I need to post on here, I've stopped using this blog in favor of just using the schoolwork tag on my main blog, you can find the cross-post of this one at http://blog.gallabytes.com/2014/03/miu-haskellized.html

      Delete