MIU Workshop
About this app
The MIU system from Gödel, Escher, Bach to touch: the word is made of tiles, four rule cards show where MxI → MxIU, Mx → Mxx, xIIIy → xUy and xUUy → xy fit, and a tap applies the rule. Above it the derivation tree grows level by level as on the slide, optionally as a breadth-first search without repetitions (1, 2, 3, 5, 14, 44, 213 new words). The I counter with the remainder on division by 3 and the five proof cases show why MU never appears.
With explain mode: an AI tutor walks you through the app, points out what matters in the scene and answers your questions.
A formal system without meaning
A formal system consists of an alphabet, well-formed words, axioms and rules. In Douglas Hofstadter's MIU system the alphabet is {M, I, U}, the only axiom is MI, and four rules change words purely mechanically: MxI becomes MxIU, Mx becomes Mxx, a III turns into U, and a UU disappears. The MU puzzle asks whether the word MU can be produced this way. The answer comes from an invariant: the number of I is never divisible by 3.
What the app shows
The current word is a row of tiles, M, I and U in three shapes, with the position numbers below. Four rule cards list every position where a rule fits, together with the result; a tap applies it, and tiles glide, vanish or are copied. A counter shows the number of I and the remainder on division by 3. Above it the derivation tree grows level by level as on the slide, with the rule number on every edge.
Try it yourself
Try to derive MU from MI and watch the remainder at the I counter. Two tasks ask for MIUUI and MUIIU in five steps each, and a button shows the next step of the shortest derivation. In the tree you can skip words already found; it then becomes a breadth-first search with 1, 2, 3, 5, 14, 44 and 213 new words. The Proof panel goes through the five cases of the slide with examples from your history.
Frequently asked questions
- Why can MU not be derived in the MIU system?
- The axiom MI has one I. Rules 1 and 4 do not change the number of I, rule 2 doubles it, rule 3 subtracts 3. If the number is not divisible by 3, it stays that way after every rule. MU has 0 I, and 0 is divisible by 3.
- Does rule 3 replace all III at once?
- No. Every application replaces exactly one position. Depending on the position, MUIIII becomes MUUI or MUIU, because III occurs there at two overlapping positions.
- Will you find MU if you search long enough?
- No. The levels of the derivation tree grow quickly, without repetitions 1, 2, 3, 5, 14, 44 and 213 new words on levels 0 to 6, and MU is never among them. If MU were derivable the search would find it in finite time; that it is not is only shown by the invariant.
- What can you set in the MIU Workshop?
- Your own start word made of M, I and U, levels 0 to 6 of the derivation tree, skipping words already found, and three tasks. There is also the Python version with breadth-first search to copy, and the five cases of the proof.
Subject: Computer science
More from Computer science
- Ackermann function
- Elevator simulator
- Binary workshop
- Binary versus linear search
- The Collatz problem
- Inside a CPU
- Swap the inside
- One frame in 16 milliseconds — how a game engine renders an image (3D)
A VisuApp by heyprof: interactive, free in your browser, no sign-up. What is a VisuApp? · All apps