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

Предлагалось объединить эту статью с Геделем, Эшером, Бахом . ( Обсудить ) Предлагается с января 2021 года.

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

Загадка [ править ]

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

№	Формальное правило [примечание 1]			Неформальное объяснение	Пример
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. Теперь неизменным свойством является то, что количество Is не делится на 3:

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

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

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

${\ Displaystyle п \ экв 2 ^ {а} \ not \ эквив 0 {\ pmod {3}}. \,}$

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

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

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

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

Доказательство [ править ]

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

Если: если x соответствует свойствам с 1 по 3, пусть и будет числом и в x , соответственно, и пусть . По свойству 3 число не может делиться на 3, а значит, и быть не может. То есть . Пусть такое то и . ^{[примечание 2]} Исходя из аксиомы , применяя второе правило, раз получаем ... с . Так как делится на 3, по построению , применяя третье правило, раз получим ... ... , с ровно с , за которым следует некоторое количество${\ displaystyle N_ {I}}$${\ displaystyle N_ {U}}$IU${\ Displaystyle N = N_ {I} + 3N_ {U}}$${\ displaystyle N_ {I}}$${\ displaystyle N}$${\ Displaystyle N \ Equiv 1 {\ text {или}} N \ Equ 2 {\ pmod {3}}}$${\ Displaystyle п \ в \ mathbb {N}}$${\ displaystyle 2 ^ {n}> N}$${\ Displaystyle 2 ^ {п} \ эквив N {\ pmod {3}}}$MI${\ displaystyle n}$MIIII${\ Displaystyle 2 ^ {п}}$ I${\ displaystyle 2 ^ {n} -N}$${\ displaystyle n}$${\ displaystyle {\ frac {2 ^ {n} -N} {3}}}$MIIIIUU${\ displaystyle N}$ IU. UСчетчик всегда можно сделать еще, применяя первое правило один раз, если это необходимо. Достаточно часто применяя четвертое правило, все Uможно удалить, получив таким образом MIII... Iwith . Применяя третье правило для уменьшения триплетов в в правильных местах получат х . В целом x был получен из .${\ displaystyle N_ {I} + 3N_ {U}}$ IIUMI

Пример [ править ]

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

MI ${\ Displaystyle {\ stackrel {2} {\ to}}}$ MII ${\ Displaystyle {\ stackrel {2} {\ to}}}$ MIIII ${\ Displaystyle {\ stackrel {2} {\ to}}}$ MIIIIIIII ${\ Displaystyle {\ stackrel {2} {\ to}}}$ MIIIIIIIIIIIIIIII ${\ Displaystyle {\ stackrel {3} {\ to}}}$ MIIIIIIIUIIIIII ${\ Displaystyle {\ stackrel {3} {\ to}}}$ MIIIIIIIUUIII ${\ Displaystyle {\ stackrel {1} ​​{\ to}}}$ MIIIIIIIUUIIIU ${\ Displaystyle {\ stackrel {3} {\ to}}}$ MIIIIIIIUUUU ${\ Displaystyle {\ stackrel {4} {\ to}}}$ MIIIIIIIUU ${\ Displaystyle {\ stackrel {4} {\ to}}}$ MIIIIIII ${\ Displaystyle {\ stackrel {3} {\ to}}}$ MIIUII.

Арифметизация [ править ]

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

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

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

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

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

Отношение к логике [ править ]

Этот раздел требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален. ( Июль 2013 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

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

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

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

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

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

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

См. Также [ править ]

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

Примечания [ править ]

Ссылки [ править ]

Внешние ссылки [ править ]

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