Введение

Загадка в книге Дугласа Хофстадтера "Гёдель, Эсчер, Бах"

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

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

Только если: Ни одно правило не перемещает , не изменяет количество , и не вводит какой-либо символ, отличный от , , Следовательно, каждое x, выведенное из , удовлетворяет свойствам 1 и 2. Как было показано ранее, оно также удовлетворяет свойству 3. Если: Если x удовлетворяет свойствам 1–3, пусть и будут количеством и в x соответственно, и пусть . По свойству 3, число не делится на 3, следовательно, и не может делиться на 3. То есть, пусть такое, что и . Начиная с аксиомы , применяя второе правило раз, получим , где . Поскольку делится на 3, по построению , применяя третье правило раз, получим , с ровно , за которым следует некоторое количество . Количество всегда можно сделать четным, применив первое правило один раз, если это необходимо. Применяя четвертое правило достаточное количество раз, все можно удалить, таким образом, получив , где . Применяя третье правило для уменьшения троек в правильных позициях, получим x. В итоге, x было выведено из .

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

Система МИУ иллюстрирует несколько важных концепций логики посредством аналогии. Её можно интерпретировать как аналогию формальной системы – инкапсуляцию математических и логических концепций с использованием символов. Строка МИ подобна одной аксиоме, а четыре правила преобразования подобны правилам вывода. Строка МУ и невозможность её вывода аналогичны утверждению математической логики, которое нельзя доказать или опровергнуть в рамках формальной системы. Она также демонстрирует контраст между интерпретацией на "синтаксическом" уровне символов и на "семантическом" уровне значений. На синтаксическом уровне нет знания о неразрешимости головоломки МУ. Система не отсылает ни к чему: это просто игра с бессмысленными строками. Работая в системе, алгоритм мог бы последовательно генерировать каждую допустимую строку символов в попытке получить МУ, и хотя он никогда бы не преуспел, он искал бы бесконечно, так и не придя к выводу о тщетности поисков. Однако, после нескольких попыток, человек начинает подозревать, что головоломка может быть неразрешимой. Тогда человек "выходит за пределы системы" и начинает рассуждать о самой системе, а не работать внутри неё. В конечном итоге, человек понимает, что система в некотором роде связана с делимостью на три. Это "семантический" уровень системы – уровень смысла, которого система естественным образом достигает. На этом уровне головоломка МУ оказывается неразрешимой. Неспособность системы МИУ выражать или выводить факты о себе, такие как невозможность вывести МУ, является следствием её простоты. Однако более сложные формальные системы, такие как системы математической логики, могут обладать этой способностью. Это ключевая идея, лежащая в основе теоремы о неполноте Гёделя.

Педагогическое применение

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