MU problem

Take an initial string (theorem) of two characters "MI" in an alphabet of 3 characters "M", "I", and "U". The MU problem asks if "MU" can be derived from "MI" given 4 rules.

• Add U to any string ending in I (MxI $\Rightarrow$ MxIU)
• Double everything after M (Mx $\Rightarrow$ Mxx)
• Replace III with U (MxIIIx $\Rightarrow$ MxUx)
• Remove UU (MxUUx $\Rightarrow$ Mxx)

This is an example of a formal system.

You should try to reach MU from MI.

...

Perhaps you made attempts like: MI $\Rightarrow$ MII $\Rightarrow$ MIIII $\Rightarrow$ MUI $\Rightarrow$ MUII $\Rightarrow$ MUIIII...

You can't actually make MU. The rules preserve a specific property that MU would violate; being that the number of "I"s in the string will always be of $2^{n}$ meaning that the "III" $\Rightarrow$ "U" rule could never reduce the string to 0 "I"s. The same principle, syntactic rules create semantic boundaries, explains why you can't prove certain statements in arithmetic, or why some programs can't be optimized by compilers.