Gödel numbers, MIU and Turing machines
Gödel numbers — strings as numbers, the MIU puzzle and the invariant that settles it in a second, and Turing machines step by step.
How to solve it
A formal system is a set of symbols and rules by which some strings are obtained from others. Gödel encoded strings as numbers so that statements about the system became statements about numbers. And to prove that a string cannot be derived, one looks for an invariant — a property no rule changes.
Step by step
- The Gödel number of a string: $2^{c_1} \cdot 3^{c_2} \cdot 5^{c_3} \cdots$, where $c_i$ are the symbol codes. Back: factor the number into primes; the exponents are the codes in order.
- MIU: a rule is applied to the string literally. Rule 2, for example, doubles everything after M: $\mathrm{M}x \to \mathrm{M}xx$.
- Derivability in MIU: the axiom MI has one I, and the rules never make the number of I's a multiple of $3$. If a string's I count is divisible by $3$, it cannot be derived.
- A Turing machine: at each step take from the table, by the state and the symbol under the head, what to write, where to move and which state to enter. Count the steps until state H.
Common mistakes
- Reading the codes in reverse: the exponent of $2$ is the first symbol.
- Trying to derive an MIU string by search when the invariant says “no” at once.
- Applying an MIU rule to part of the string instead of the whole.
- Moving a Turing machine's head before writing — write first, then move.