Monday, July 04, 2005

Back with a bang :)

Manupulative codewords - Hofstadter's MIU system

This system of codewords have only stings of letters formed from the alphabets, M, I, U with MI as one of the codewords. You can form other codewords in the system by the following four rules :

x in the below lines can be any string of letters from M, I, U that makes a codeword in each of the rules.

1. If xI is a codeword, then xIU is also a codeword.
2. If Mx is a codeword, Mxx is also a codeword.
3. In any codeword, III can be replaced by U.
4. In any codeword, UU can be omitted.

Questions : Show that MUII is a codeword. Is MU a codeword?