Новый ум короля: О компьютерах, мышлении и законах физики - Пенроуз Роджер. Страница 48

В качестве примера мы можем взять для нашего исходного списка, скажем, такие равенства:

EAT = АТ

АТЕ = А

LATER = LOW

PAN = PILLOW

CARP = ME.

Отсюда мы можем, например, вывести

LAP = LEAP,

используя последовательные замены из второго, первого и снова второго соотношения из нашего исходного листа:

LAP = LATEP = LEATEP = LEAP.

Проблема теперь заключается в том, чтобы выяснить, сможем ли мы для любой наперед заданной пары слов осуществить вышеописанным образом переход от одного из них к другому? Можем мы перейти от CATERPILLAR к MAN, или, скажем, от CARPET — к MEAT? Ответ в первом случае оказывается утвердительным, тогда как во втором — отрицательным. Когда ответ утвердителен, стандартный путь показать его справедливость заключается в построении цепочки равенств, где каждое из слов получается из предыдущего с учетом допустимых соотношений. Итак, имеем (обозначая буквы, назначенные к замене, жирным шрифтом, а только что измененные — курсивом):

Как мы можем утверждать, что посредством разрешенных подстановок невозможно получить MEAT из CARPET? Для демонстрации этого факта придется подумать чуть больше, однако показать это не так уж сложно, причем множеством разных способов. Простейшим представляется следующий: в каждом «равенстве» из нашего списка число букв А плюс число букв W плюс число букв М с каждой стороны одинаково. Значит, общая сумма указанных букв не может меняться в процессе преобразования по допустимым нашим списком правилам. Однако, для CARPET эта сумма равна 1, а для MEAT — 2. Следовательно, не существует способа получить из первого слова второе при помощи вышеприведенного списка равенств.

Заметьте, что когда два слова «равны», мы можем показать это, просто приведя допустимую формальную строчку символов, построенную с помощью заданных нами правил; тогда как в случае их «неравенства» мы должны прибегать к рассуждениям об этих самых правилах. Существует четкий алгоритм, который мы можем использовать для установления «равенства» между двумя словами в том случае, когда они действительно «равны». Все, что нам требуется, это составить лексикографический перечень всех возможных последовательностей слов, и потом вычеркнуть из этого списка любую строчку, где имеется пара слов, в которой последующее нельзя получить из предыдущего при помощи какого бы то ни было правила из исходного списка. Оставшиеся последовательности дадут нам набор всех искомых «равенств» между словами. Однако, в общем случае нет такого явного алгоритма для случая, когда два слова «неравны», и нам, возможно, пришлось бы применить «интеллект» для установления этого факта. (Конечно же, мне потребовалось некоторое время, прежде чем я заметил описанный выше «трюк», при помощи которого доказал, что CARPET и MEAT «неравны». А для другого примера «трюк» мог бы понадобиться совершенно иной. Кстати, интеллект помогает — хотя и не обязательно — и в случае, когда необходимо установить существование некоторого «равенства».)

В действительности, для нашего конкретного списка из пяти «равенств», которые составляют исходный список в рассмотренном выше примере, привести алгоритм, устанавливающий «неравенство» в случае, когда два слова и вправду «неравны» — не так уж сложно. Однако, чтобы отыскать алгоритм в этом случае, потребовалась изрядная работа интеллекта! И, конечно, оказывается, что не существует единого универсального алгоритма для всех возможных вариантов исходного списка. Общая задача со словами принадлежит области нерекурсивной математики!

Существуют даже определенные варианты выбора исходного списка, для которых нет алгоритма решения задачи сравнения двух слов. Один из них дается таким набором:

АН = НА

ОН = НО

АТ = ТА

ОТ = ТО

TAI = IT

HOI = IH

THAT = ITHT.

(Этот список взят из списка, предложенного Григорием Цейтиным и Даной Скотт в 1955 году (см. Гарднер [1958]).) Таким образом, эта частная задача со словами служит примером нерекурсивной математики в том смысле, что, используя такой исходный список, мы не можем алгоритмическим путем решить, «равны» два наперед заданных слова или нет.

Общая задача со словами возникает как следствие рассмотрения формализованной математической логики («формальных систем» и т. п., в соответствии с обсуждаемым ранее). Исходный список выполняет роль системы аксиом, а правила замены слов — правил вывода. Доказательство нерекурсивности задачи со словами вытекает из подобных рассуждений.

В качестве последнего примера задачи из области нерекурсивной математики давайте рассмотрим вопрос о покрытии Евклидовой плоскости многоугольниками, разнообразие форм которых ограничено, а сам вопрос при этом ставится так: можем ли мы выложить всю плоскость полностью, без разрывов и нахлестов, используя фигуры только данных нам форм? Такая укладка фигур называется замощением плоскости. Мы знаем, что такое замощение возможно при помощи только квадратов, только равнобедренных треугольников или только правильными шестиугольниками (как изображено на рис. 10.2 гл. 10 «Плиточные» структуры и квазикристалы»), но невозможно, если использовать только правильные пятиугольники. Многими иными фигурами, такими, как два неправильных пятиугольника на рис. 4.6, также можно выложить плоскость.

Замощение фигурами двух форм может стать более хитроумной задачей. Два простых примера даны на рис. 4.7.

Все эти замощения являются периодическими; это означает, что они в точности повторяются по всей плоскости в двух независимых направлениях. На языке математики мы бы сказали, что существует параллелограмм периодов — параллелограмм, который, будучи неким образом выделен и затем повторен снова и снова в двух направлениях, параллельных его сторонам, даст в результате заданный узор покрытия. На рис. 4.8. представлен пример, где периодическое покрытие слева состоит из «плиток» в форме шипов, а справа указан соответствующий параллелограмм периодов.

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

Рис. 4.9 изображает три непериодических «спиральных» замощения из таких же шиповидных «плиток», как и на рис. 4.8.

Эта форма «плиток», известная как «универсальная» (по вполне понятным причинам!), была предложена Б. Грюнбаумом и Дж. К. Шепардом [1981, 1987] на основании форм, изученных X. Фодербергом. Обратите внимание, что универсальная форма позволяет замостить плоскость как периодически, так и непериодически. Это свойство характерно и для многих других форм единичных «плиток» и наборов «плиток». А могут ли существовать «плитки» (или конечные наборы «плиток»), которые бы покрывали плоскость только непериодически? Ответ на этот вопрос будет «да». На рис. 4.10 я изобразил сконструированный американским математиком Рафаэлем Робинсоном набор из фигур шести различных форм, которым можно замостить всю плоскость, но только непериодическим образом.