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!

MUnads anyone?

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

ReplyDeleteIt should be there now - something went funny with Github's embedding url when I changed usernames, it should be working now

DeleteAlso, 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