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

Рис. 4.8.Периодическое замощение и его параллелограмм периодов

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

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

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

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

Рис. 4.10.Набор Рафаэля Робинсона из шести плиток, который покрывает плоскость только непериодически

Небесполезно было бы сделать историческое отступление и посмотреть, как появился это непериодический набор (см. Грюнбаум, Шепард [1987]). В 1961 году американский логик китайского происхождения Хао Ванг поставил вопрос о существовании процедуры для решения задачи замощения, или, иными словами, о нахождении алгоритма, который позволил бы выяснить возможность замощения всей плоскости с помощью конечного набора многоугольников различной формы! [89]Ему удалось показать, что такая процедура могла бы существовать, если бы получилось доказать следующую гипотезу: любой конечный набор разных «плиток», с помощью которого можно каким-нибудь способом выполнить замощение плоскости, пригоден также и для ее периодического замощения. Мне думается, в то время интуитивно казалось, что не может существовать набор «плиток», нарушающий это условие (т. е. не может существовать «непериодический» набор плиток). Однако в 1966 году, следуя в указанном Хао Вангом направлении, Роберт Бергер смог показать, что, на самом деле, процедуры решения задачи покрытия не существует: эта задача также принадлежит области нерекурсивной математики! [90]

С учетом доказанного Хао Вангом это означало, что хотя бы один непериодический набор «плиток» должен существовать; и Бергер смог построить первый такой набор. Однако, из-за сложности выбранного им способа рассуждений, его набор состоял из ненормально большого числа «плиток» разной формы — изначально их насчитывалось 20 426. Использовав некоторый дополнительный искусный прием, Бергеру удалось сократить это число до 104. А в 1971 году Рафаэль Робинсон довел его до шести, которые изображены на рис. 4.10 выше.

Другой непериодический набор из шести «плиток» представлен на рис. 4.11. Это множество я придумал сам в 1973 году, следуя в своих рассуждениях несколько отличным путем. (Я вернусь к этой теме в главе 10 «Плиточные структуры и квазикристаллы», где на рис. 10.3, изображен массив, покрытый такими «плитками».)

Рис. 4.11.Другой набор из шести плиток, который покрывает плоскость только непериодически

После того, как, я познакомился с «шестиплиточным» набором Робинсона, я начал думать о том, как сократить их число; и путем различных манипуляций с разрезаниями и склеиванием я, в конечном счете, смог довести количество «плиток» до двух. Две альтернативные схемы представлены на рис. 4.12.

Рис. 4.12.Две пары плиток, которые покрывают плоскость только непериодически («плитки Пенроуза»). Также показано замощение плоскости каждой из этих пар

Узоры, которые получаются в результате полного замощения и имеющие с необходимостью непериодическую структуру, обладают рядом замечательных свойств, в том числе — кажущейся невозможной с точки зрения кристаллографии квазипериодической симметрией с осью пятого порядка. К этому вопросу я вернусь позднее.

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

Задача замощения, в том виде, как она исследовалась Вангом, Бергером и Робинсоном, формулируется для «плиток», построенных на квадратах. Я же здесь допускаю рассмотрение многоугольников произвольной формы, и поэтому необходимо наличие какого-нибудь способа изображения каждой из «плиток», поддающегося адекватному вычислению. Одним из таких путей могло бы быть представление вершин «плиток» точками плоскости Аргана, которые превосходно задаются алгебраическими числами.

Давайте теперь вернемся к нашей предшествующей дискуссии о множестве Мандельброта. Я буду для наглядности предполагать, что это множество является в некотором смысле нерекурсивным. Поскольку его дополнение рекурсивно нумеруемо, то, как следствие, само оно таковым быть не может. Я думаю, что форма множества Мандельброта может кое-чему научить нас о том, что касается природы нерекурсивных множеств и нерекурсивной математики.

Посмотрим еще раз на рис. 3.2, с которым мы встретились в третьей главе («страна Тор'Блед-Нам»). Заметьте, что большая часть множества вписывается в сердцевидную фигуру, которую я обозначил на рис. 4.13 через А(ниже). Эта фигура называется кардиоида и ее внутренняя область может быть определена математически как множество точек с плоскости Аргана, которые удовлетворяют равенству