Головоломка MU (англ. Mu Puzzle) — головоломка, которую создал Дуглас Хофштадтер. Упомянута в книге Гедель, Эшер, Бах. Ход головоломки - переписывание одной строки в другую по заданным правилам. Головоломка построена так, что она не имеет решения.
Предположим, что есть символы M, I, и U, которые могут быть объединены, и при объединении из них получаются определенные строки. Головоломка звучит так:
«Пусть в начале есть строка MI. Преобразуйте её в строку MU, каждый выбирая один из возможных вариантов хода:[1][2]
Головоломка не имеет решения: невозможно изменить строку MI так, чтобы вместо неё появилась строка МU по данным правилам.
Для того, чтобы доказать утверждение о том, что головоломка MU нерешаема, нужно искать инвариант, то есть некоторое количество или свойство, которое не меняется при применении правила.
В этой головоломке можно посмотреть на общее количество букв I в строке.
Первый и четвертый варианты хода не меняют это число.
Второй вариант хода удваивает число букв I, третий способ уменьшает это число на 3. Докажем, что число букв I не делится на 3, если ходы начались со строки MI:
Таким образом, целевая строка MU не может быть достигнута, потому что в строке MU 0 букв I (т. е. нет ни одной буквы), а 0 - это число, которое делится на 3 (а по доказанному ранее число не должно делиться на 3).
На языке сравнений по модулю, число 2 в степени a не может быть сравнимо с нулём по модулю 3. (здесь число а показывает количество применений второй операции, так как операции 1, 3 и 4 не меняют остаток числа по модулю n).
Глава XIX в книге Гедель, Эшер, Бах предлагает заменить буквы M, I и U цифрами. Каждая строка из букв M, I, U заменяется на число. M - это цифра 3, I - это 1 и U - это 0. (Например, строке MIUIU будет соответствовать число 31010.)
Начальная строка в головоломке (MI) сопоставлена числу 31.
Четыре правила преобразований, приведенные выше, можно записать так:
Таким образом, головоломку MU можно представить в виде числовой головоломки.
(Примечание: описание первого правила здесь несколько отличается от того, которое применялось в книге. В книге использовалась буква m. Но буква m уже используется в показателях степеней, поэтому здесь она заменена на букву k. Кроме того, здесь запись первого правила была несколько[уточнить] изменена, чтобы она была более схожей с тремя другими правилами)
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .