The example task of MIU-system (in the lecture notes) was more difficult than meant by mistake. So don't worry, if you couldnät solve the problem! It isn't solvable (which was in fact the original idea in the book).

So this task did not only demonstrate formal languages but also a more important subject: How to find a proof or show that it doesn't exist. This is in fact same as showing that the given word belongs or doesn't belong to the language. During the course we will learn different solutions for this so called parsing problem, depending on the difficultiness of the langauge. But now I just explain the idea, why MU cannot be derived from MI.

The system consisted of the rules
xI -> xIU
Mx -> Mxx
xIIIy -> xUy
xUUy -> xy

But Mu cannot be derived with these rules (i.e. MU is not a theorem of the system). The problem is that we cannot get rid of letter I, unless we had multiple of 3 I's in the original word.

Rule 4 eats always even number of U's. To get one U left we have to have odd number of U.s. Let's mark the number of U's by 2n+1. We have two possibilities to get that:

1) From multiple of 3 of I's by rule 3. So the number of I's must have been 3*(2n+1)=6n+3. I's can be produced only by rule 2, which always duplicates the ''tails''. Thus an odd number of I's cannot be produced.

2) One U is produced by rule 1. In addition there can be an even number of U's. These can be produced from I's only by rule 3. So we must have had 3*2n=6n I's. But this cannot be produced by rule 2, unless we originally had multiple of 3 I's.

In the book Gödel, Escher, Bach, chapter IX (p. 260->) is given a nice proof by Gödel(MIU-) numbers.