МУ головоломка

Загадка MU — это головоломка, сформулированная Дугласом Хофштадтером и найденная у Гёделя, Эшера и Баха, включающая простую формальную систему под названием «MIU». Мотивация Хофштадтера состоит в том, чтобы противопоставить рассуждения внутри формальной системы (т. е. вывод теорем) рассуждениям о самой формальной системе. MIU является примером канонической системы Поста и может быть переформулирован как система переписывания строк .

Загадка

Предположим, существуют символы M, I, и U которые можно комбинировать для создания строк символов. Загадка MU требует начать с «аксиоматической» строки. MI и преобразуем его в строку MU используя на каждом шаге одно из следующих правил преобразования:

Нет.	Формальное правило			Неофициальное объяснение	Пример
1.	х I	→	х IU	Добавить U до конца любой строки, заканчивающейся на I	MI	к	MIU
2.	Mх	→	Mхх	Удвойте строку после M	MIU	к	MIUIU
3.	х IIIи	→	х Uи	Замените любой III с U	MUIIIU	к	MUUU
4.	х UUи	→	ху	Удалите все UU	MUUU	к	MU

Решение

Головоломка неразрешима: нельзя поменять струну MI в MU путем многократного применения данных правил. Другими словами, MU не является теоремой формальной системы MIU. Чтобы доказать это, необходимо выйти «за пределы» самой формальной системы.

Чтобы доказать подобные утверждения, часто бывает полезно найти инвариант ; то есть некоторая величина или свойство, которое не меняется при применении правил.

В этом случае можно посмотреть общее количество I в строке. Только второе и третье правила меняют это число. В частности, второе правило удвоит его, а третье — уменьшит на 3. Инвариантным свойством является то, что число I не делится на 3:

• Вначале количество Is равно 1, которая не делится на 3.
• Удвоение числа, которое не делится на 3, не делает его делящимся на 3.
• Вычитание 3 из числа, которое не делится на 3, также не делает его делящимся на 3.

Таким образом, цель MU с нулем I невозможно, поскольку 0 делится на 3.

На языке арифметики число n модульной I подчиняется соответствию

$n\equiv 2^{a}\not \equiv 0{\pmod {3}}.\,$

где a подсчитывает, как часто применяется второе правило.

Разрешимый критерий выводимости

В более общем смысле, произвольно заданную строку x можно получить из MI по четырем вышеприведенным правилам тогда и только тогда , когда x соответствует трем следующим свойствам:

1. x состоит только из одного M и любое количество I и U,
2. х начинается с M, и
3. количество I число x не делится на 3.

Доказательство

Только если: Ни одно правило не перемещает M, изменяет количество M, или представляет любого персонажа из M, I, U. Следовательно, каждый x, полученный из MI учитывает свойства 1 и 2. Как было показано ранее , он также учитывает свойство 3.

Если: Если x соответствует свойствам с 1 по 3, пусть $N_{I}$ и $N_{U}$ быть числом I и U по x соответственно, и пусть $N=N_{I}+3N_{U}$.По свойству 3 число $N_{I}$ не может делиться на 3, следовательно, $N$ тоже не может быть. То есть, $N\equiv 1{\text{ or }}N\equiv 2{\pmod {3}}$. Позволять $n\in \mathbb {N}$ такой, что $2^{n}>N$ и $2^{n}\equiv N{\pmod {3}}$. Начиная с аксиомы MI, применяя второе правило $n$ раз получает MIII... I с $2^{n}$ I. С $2^{n}-N$ делится на 3, по построению $n$, применяя третье правило ${\frac {2^{n}-N}{3}}$ раз получит MIII... IU... U, с ровно $N$ I, за которым следует некоторое количество U. U счет всегда можно сравнять, если при необходимости применить первое правило один раз. Применяя четвертое правило достаточно часто, все U затем можно удалить, получив таким образом MIII... I с $N_{I}+3N_{U}$ I. Применяя третье правило для сокращения троек I в U в нужных местах получим x . В целом, x было получено из MI.

Пример

Чтобы проиллюстрировать конструкцию в If , строка части доказательства MIIUII, который учитывает свойства от 1 до 3, приводит к $N_{I}=4$, $N_{U}=1$, $N=7$, $n=4$; следовательно, его можно вывести следующим образом:

MI 2 → MII 2 → MIIII 2 → MIIIIIIII 2 → MIIIIIIIIIIIIIIII 3 → MIIIIIIIUIIIIII 3 → MIIIIIIIUUIII 1 → MIIIIIIIUUIIIU 3 → MIIIIIIIUUUU 4 → MIIIIIIIUU 4 → MIIIIIII 3 → MIIUII.

Арифметизация

Глава XIX книги Гёделя, Эшера и Баха дает следующее отображение системы MIU в арифметике. Во-первых, каждую строку MIU можно преобразовать в целое число, сопоставив буквы M, I, и U на числа 3, 1 и 0 соответственно. (Например, строка MIUIU будет сопоставлен с 31010.)

Во-вторых, единственная аксиома системы MIU, а именно строка MI, становится числом 31.

В-третьих, четыре формальных правила, приведенные выше, становятся следующими:

Нет.	Формальное правило			Пример
1.	к × 10 + 1	→	10 × ( к × 10 + 1)	31	→	310	( к = 3)
2.	3 × 10 м + н	→	10 м × (3 × 10 м + н ) + н	310	→	31010	( м = 2, п = 10)
3.	к × 10 м +3 + 111 × 10 м + н	→	к × 10 м + 1 + н	3111011	→	30011	( к = 3, м = 3, п = 11)
4.	к × 10 м +2 + н	→	к × 10 м + н	30011	→	311	( к = 3, м = 2, п = 11)

( Обратите внимание: интерпретация первого правила выше внешне отличается от перевода в книге, где оно написано как «[i] если мы сделали 10 m + 1, то мы можем сделать 10 × (10 m + 1)». Здесь, однако, переменная m была зарезервирована для использования только в показателях 10, и поэтому в первом правиле она была заменена на k . Кроме того, в этом представлении расположение факторов в этом правиле было согласовано с расположением факторов в другом правиле. три правила.)

Отношение к логике

Система MIU иллюстрирует несколько важных концепций логики посредством аналогии.

Его можно интерпретировать как аналогию формальной системы — инкапсуляции математических и логических понятий с помощью символов. Строка MI подобна одной аксиоме , а четыре правила преобразования подобны правилам вывода .

Строка MU и невозможность ее вывода в таком случае аналогичны утверждению математической логики, которое не может быть ни подтверждено , ни опровергнуто формальной системой.

Это также демонстрирует контраст между интерпретацией на «синтаксическом» уровне символов и на «семантическом» уровне значений. На синтаксическом уровне нет знания о неразрешимости головоломки MU. Система ни на что не ссылается : это просто игра с бессмысленными строками. Работая внутри системы, алгоритм мог последовательно генерировать каждую допустимую строку символов в попытке сгенерировать MU, и хотя это никогда не удавалось, он будет искать вечно, так и не придя к выводу, что поиск бесполезен. Однако игрок-человек после ряда попыток вскоре начинает подозревать, что головоломка может быть неразрешимой. Тогда человек «выпрыгивает из системы» и начинает рассуждать о системе, а не работать внутри нее. В конце концов, человек понимает, что система в некотором роде основана на делении на три. Это «семантический» уровень системы — уровень смысла, которого система естественным образом достигает. На этом уровне загадка MU кажется неразрешимой.

Неспособность системы MIU выражать или выводить факты о себе, например, неспособность выводить MU, является следствием ее простоты. Однако такой способностью могут обладать более сложные формальные системы, например системы математической логики. Это ключевая идея теоремы Гёделя о неполноте .

использование

В своем учебнике «Дискретная математика с приложениями » Сюзанна С. Эпп чтобы представить концепцию рекурсивных определений , и начинает соответствующую главу с цитаты из GEB. использует головоломку MU ,

См. также

• Инвариант (математика)
• Неограниченная грамматика

Внешние ссылки

• «Система MIU Хофштадтера» . Архивировано из оригинала 4 марта 2016 года . Проверено 29 ноября 2016 г. Онлайн-интерфейс для создания дериваций в системе MIU.
• «МЮ Пазл» . Архивировано из оригинала 14 мая 2018 года . Проверено 13 мая 2018 г. Онлайн-реализация производственной системы MIU на JavaScript.