Strings in the MIU System
Logic
Level
1
In the \(MIU\) system, you always start with the string \(MI\) and then form new strings by applying any of following rules any number of times:
| Rules | Examples |
| 1. If your string ends with \(I\), you can add a \(U\) at the end. | \(MI\longrightarrow MIU\) |
| 2. You can double the entire string following \(M.\) | \(MIU\longrightarrow MIUIU\) |
| 3. Three consecutive \(I\)'s can be replaced with a single \(U.\) | \(MIIIU\longrightarrow MUU\) |
| 4. Two consecutive \(U\)'s can be removed from the string. | \(MUU\longrightarrow M\) |
Which of the following strings can be derived from \(MI\) using these rules?
Note: None of the rules can be used in the opposite way; for example, you aren't allowed to derive \(MUUI\) from \(MI\) by using a reversed version of rule 4.
Source: The \(MIU\) puzzle was introduced by Douglas Hofstadter in his magisterial work Gödel, Escher, Bach.
by
Steve Gualtieri