MU головоломка - MU puzzle

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

Головоломка

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

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

Решение

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

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

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

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

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

На языке модульная арифметика, число п из я подчиняется конгруэнтности

${displaystyle nequiv 2^{a}ot equiv 0{pmod {3}}.,}$

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

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

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

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

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

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

Если: Если Икс уважает свойства с 1 по 3, пусть ${displaystyle N_{I}}$ и ${displaystyle N_{U}}$ быть числом я и U в Икссоответственно, и пусть ${displaystyle N=N_{I}+3N_{U}}$.По свойству 3 число ${displaystyle N_{I}}$ не может делиться на 3, поэтому ${displaystyle N}$ тоже не может быть. Это, ${displaystyle Nequiv 1{ ext{ or }}Nequiv 2{pmod {3}}}$. Позволять ${displaystyle nin mathbb {N} }$ такой, что ${displaystyle 2^{n}>N}$ и ${displaystyle 2^{n}equiv N{pmod {3}}}$.^{[заметка 2]} Начиная с аксиомы MI, применяя второе правило ${displaystyle n}$ раз получает MIII...я с ${displaystyle 2^{n}}$ я. С ${displaystyle 2^{n}-N}$ делится на 3, по построению ${displaystyle n}$, применяя третье правило ${displaystyle {frac {2^{n}-N}{3}}}$ раз получит MIII...IU...U, с точно с ${displaystyle N}$ я, за которым следует некоторое количество U. В U счет всегда можно уравнять, применив первое правило один раз, если это необходимо. Применяя четвертое правило достаточно часто, все U затем можно удалить, получив таким образом MIII...я с ${displaystyle N_{I}+3N_{U}}$ я. Применяя третье правило для уменьшения троек я в U в нужных местах получим Икс. В целом, Икс был получен из MI.

пример

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

MI ${displaystyle {stackrel {2}{ o }}}$ MII ${displaystyle {stackrel {2}{ o }}}$ MIIII ${displaystyle {stackrel {2}{ o }}}$ MIIIIIIII ${displaystyle {stackrel {2}{ o }}}$ MIIIIIIIIIIIIIIII ${displaystyle {stackrel {3}{ o }}}$ MIIIIIIIUIIIIII ${displaystyle {stackrel {3}{ o }}}$ MIIIIIIIUUIII ${displaystyle {stackrel {1}{ o }}}$ MIIIIIIIUUIIIU ${displaystyle {stackrel {3}{ o }}}$ MIIIIIIIUUUU ${displaystyle {stackrel {4}{ o }}}$ MIIIIIIIUU ${displaystyle {stackrel {4}{ o }}}$ MIIIIIII ${displaystyle {stackrel {3}{ o }}}$ MIIUII.

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

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

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

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

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

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

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

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

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

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

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

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

Педагогическое использование

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

Смотрите также

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

Примечания

1. Здесь, Икс и у - переменные, обозначающие строки символов. Правило может применяться только ко всей строке, но не к произвольной подстроке.
2. Такой ${displaystyle n}$ всегда существует, так как степени двойки поочередно оцениваются в 1 и 2 по модулю 3.
3. Здесь, k и м обозначают произвольные натуральные числа, а п любое натуральное число меньше 10^м. Каждое правило формы "Икс → у"следует читать как", если мы сделали Икс мы можем сделать у. »Как показано в столбце« Пример », правило может применяться только ко всему номеру MIU, а не к произвольной части его десятичного представления.

Рекомендации

1. Джастин Карри / Curran Kelleher (2007). Гедель, Эшер, Бах: ментальная космическая одиссея. MIT OpenCourseWare.
2. Хофштадтер, Дуглас Р. (1999) [1979], Гедель, Эшер, Бах: вечная золотая коса, Базовые книги, ISBN  0-465-02656-7Здесь: Глава I.
3. Дискретная математика с приложениями, Третье издание, Brooks / Cole, 2004. Глава 8.4, «Общие рекурсивные определения», с. 501.

внешняя ссылка

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