Новый ум короля: О компьютерах, мышлении и законах физики
Шрифт:
В действительности, для нашего конкретногосписка из пяти «равенств», которые составляют исходный список в рассмотренном выше примере, привести алгоритм, устанавливающий «неравенство» в случае, когда два слова и вправду «неравны» — не так уж сложно. Однако, чтобы отыскатьалгоритм в этом случае, потребовалась изрядная работа интеллекта! И, конечно, оказывается, что не существует единого универсального алгоритма для всех возможных вариантов исходного списка. Общая задача со словами принадлежит области нерекурсивной математики!
Существуют даже определенные варианты выбора исходного списка, для которых нет алгоритма решения задачи сравнения двух слов. Один из них дается таким набором:
АН = НА
ОН = НО
АТ = ТА
ОТ = ТО
TAI = IT
HOI = IH
THAT = ITHT.
(Этот
Общая задача со словами возникает как следствие рассмотрения формализованной математической логики («формальных систем» и т. п., в соответствии с обсуждаемым ранее). Исходный список выполняет роль системы аксиом, а правила замены слов — правил вывода. Доказательство нерекурсивности задачи со словами вытекает из подобных рассуждений.
В качестве последнего примера задачи из области нерекурсивной математики давайте рассмотрим вопрос о покрытии Евклидовой плоскости многоугольниками, разнообразие форм которых ограничено, а сам вопрос при этом ставится так: можем ли мы выложить всю плоскость полностью, без разрывов и нахлестов, используя фигуры только данных нам форм? Такая укладка фигур называется замощениемплоскости. Мы знаем, что такое замощение возможно при помощи только квадратов, только равнобедренных треугольников или только правильными шестиугольниками (как изображено на рис. 10.2 гл. 10 «Плиточные» структуры и квазикристалы»), но невозможно, если использовать только правильные пятиугольники. Многими иными фигурами, такими, как два неправильныхпятиугольника на рис. 4.6, также можно выложить плоскость.
Рис. 4.6.Два примера периодического замощения плоскости фигурой одной формы (предложены Марджори Райе (Marjorie Rice) в 1976 году)
Замощение фигурами двух форм может стать более хитроумной задачей. Два простых примера даны на рис. 4.7.
Рис. 4.7.Два примера периодического замощения плоскости фигурами двух форм
Все эти замощения являются периодическими; это означает, что они в точности повторяются по всей плоскости в двух независимых направлениях. На языке математики мы бы сказали, что существует параллелограмм периодов— параллелограмм, который, будучи неким образом выделен и затем повторен снова и снова в двух направлениях, параллельных его сторонам, даст в результате заданный узор покрытия. На рис. 4.8. представлен пример, где периодическое покрытие слева состоит из «плиток» в форме шипов, а справа указан соответствующий параллелограмм периодов.
Рис. 4.8.Периодическое замощение и его параллелограмм периодов
С другой стороны, существует множество типов замощений плоскости, которые не являются периодическими.
Рис. 4.9 изображает три непериодических «спиральных» замощения из таких же шиповидных «плиток», как и на рис. 4.8.
Рис. 4.9.Три непериодических «спиральных» замощения из таких же «универсальных» плиток, как и на рис. 4.8
Эта форма «плиток», известная как «универсальная» (по вполне понятным причинам!),
Рис. 4.10.Набор Рафаэля Робинсона из шести плиток, который покрывает плоскость только непериодически
Небесполезно было бы сделать историческое отступление и посмотреть, как появился это непериодический набор (см. Грюнбаум, Шепард [1987]). В 1961 году американский логик китайского происхождения Хао Ванг поставил вопрос о существовании процедуры для решения задачи замощения, или, иными словами, о нахождении алгоритма, который позволил бы выяснить возможность замощения всей плоскости с помощью конечного набора многоугольников различной формы! [89] Ему удалось показать, что такая процедура могла бы существовать, если бы получилось доказать следующую гипотезу: любой конечный набор разных «плиток», с помощью которого можно каким-нибудь способом выполнить замощение плоскости, пригоден также и для ее периодического замощения. Мне думается, в то время интуитивно казалось, что не может существовать набор «плиток», нарушающий это условие (т. е. не может существовать «непериодический» набор плиток). Однако в 1966 году, следуя в указанном Хао Вангом направлении, Роберт Бергер смог показать, что, на самом деле, процедуры решения задачи покрытия не существует: эта задача также принадлежит области нерекурсивной математики! [90]
89
В действительности Хао Ванг занимался несколько иной проблемой — с квадратными «плитками», не вращаемыми и с совпадающими по цвету сторонами, — но эти особенности для нас здесь не важны.
90
Более того, Ханф [1974] и Майерс [1974] показали, что существует отдельное множество (из большого числа «плиток»), которое покрывает плоскость только невычислимым образом.
С учетом доказанного Хао Вангом это означало, что хотя бы один непериодический набор «плиток» должен существовать; и Бергер смог построить первый такой набор. Однако, из-за сложности выбранного им способа рассуждений, его набор состоял из ненормально большого числа «плиток» разной формы — изначально их насчитывалось 20 426. Использовав некоторый дополнительный искусный прием, Бергеру удалось сократить это число до 104. А в 1971 году Рафаэль Робинсон довел его до шести, которые изображены на рис. 4.10 выше.
Другой непериодический набор из шести «плиток» представлен на рис. 4.11. Это множество я придумал сам в 1973 году, следуя в своих рассуждениях несколько отличным путем. (Я вернусь к этой теме в главе 10 «Плиточные структуры и квазикристаллы», где на рис. 10.3, изображен массив, покрытый такими «плитками».)
Рис. 4.11.Другой набор из шести плиток, который покрывает плоскость только непериодически
После того, как, я познакомился с «шестиплиточным» набором Робинсона, я начал думать о том, как сократить их число; и путем различных манипуляций с разрезаниями и склеиванием я, в конечном счете, смог довести количество «плиток» до двух. Две альтернативные схемы представлены на рис. 4.12.