Гёделевы номера, MIU и машины Тьюринга
Гёделевы номера — строки как числа, головоломка MIU и инвариант, который решает её за секунду, и машины Тьюринга по шагам.
Как решать
Формальная система — набор символов и правил, по которым одни строки получаются из других. Гёдель закодировал строки числами, чтобы утверждения о системе стали утверждениями о числах. А чтобы доказать, что строка не выводится, ищут инвариант — свойство, которое ни одно правило не меняет.
По шагам
- Гёделев номер строки: $2^{c_1} \cdot 3^{c_2} \cdot 5^{c_3} \cdots$, где $c_i$ — коды символов. Обратно: разложите номер на простые, показатели — коды по порядку.
- MIU: правило применяется к строке буквально. Например, правило 2 удваивает всё после M: $\mathrm{M}x \to \mathrm{M}xx$.
- Выводимость в MIU: число букв I в аксиоме MI равно $1$, и правила никогда не делают его кратным $3$. Если в строке число I делится на $3$, она не выводится.
- Машина Тьюринга: на каждом шаге по состоянию и символу под головкой возьмите из таблицы, что написать, куда сдвинуться и куда перейти. Считайте шаги до состояния H.
Где ошибаются
- Читают коды в обратном порядке: показатель при $2$ — первый символ.
- Пытаются вывести строку MIU перебором, а инвариант сразу говорит «нет».
- В MIU применяют правило не к всей строке, а к её части.
- В машине Тьюринга сдвигают головку до записи символа — сначала пишут, потом сдвигаются.