Апериодический набор прототипов - Aperiodic set of prototiles

Щелкните "показать" для описания.
А периодическая мозаика с выделенной основной единицей (треугольник) и примитивной ячейкой (шестиугольник). Мозаика всей плоскости может быть создана путем совмещения копий этих треугольных фрагментов. Для этого базовый треугольник нужно повернуть на 60 градусов, чтобы подогнать его от края до края к соседнему треугольнику. Таким образом треугольная черепица основных единиц будет сгенерировано, то есть взаимно локально производные от облицовки цветной плиткой. Другая фигура, нанесенная на мозаику, белый шестиугольник, представляет собой примитивную ячейку мозаики. Копии соответствующего участка цветной плитки могут быть переведено чтобы образовать бесконечную мозаику плоскости. Для этого нет необходимости вращать этот патч.
В Плитка Пенроуза являются апериодическим набором плиток, поскольку допускают только непериодический мозаики плоскости (см. следующее изображение).
Все бесконечно многие мозаики плиток Пенроуза апериодический. То есть плитки Пенроуза представляют собой апериодический набор прототипов.

Набор прототипы является апериодический можно ли собрать копии прототипов для создания мозаики, так что все возможные шаблоны тесселяции непериодический. В апериодичность упоминается свойство определенного набора прототипов; сами различные результирующие мозаики просто непериодичны.

Данный набор плиток в Евклидова плоскость или другое геометрическое окружение, допускает черепицу если неперекрывающиеся копии плитки в наборе могут быть соединены вместе, чтобы покрыть все пространство. Данный набор плиток может допускать периодические мозаики, то есть мозаики, которые остаются инвариантными после сдвига на перевод (например, решетка из квадратных плиток периодична). Нетрудно разработать набор плиток, который допускает непериодические мозаики, а также периодические мозаики (например, случайно расположенные мозаики с использованием квадрата 2 × 2 и прямоугольника 2 × 1 обычно будут непериодическими).

Однако апериодический набор плиток может Только производят непериодические мозаики.[1][2] Бесконечно много различных мозаик может быть получено из одного апериодического набора плиток.[3]

Самыми известными примерами апериодического набора плиток являются различные Плитка Пенроуза.[4][5] Известные апериодические наборы прототипов видны на список апериодических наборов тайлов. Лежащий в основе неразрешимость из проблема домино означает, что не существует систематического процедура для принятия решения о том, может ли данный набор плиток перекрывать плоскость.

История

Полигоны находятся самолет цифры которые ограничены прямыми отрезки линии. Правильные многоугольники имеют все стороны равной длины а также все углы равной меры. Уже в 325 году нашей эры Папп Александрийский знал, что только 3 типа правильных многоугольников (квадрат, равносторонний треугольник и шестиугольник) могут идеально сочетаться при повторении мозаика на Евклидова плоскость. Внутри этой плоскости каждый треугольник, независимо от его регулярности, будет мозаичным. Напротив, правильные пятиугольники не мозаичны. Однако неправильные пятиугольники с разными сторонами и углами могут быть мозаичными. Плоскость выложена 15 неправильными выпуклыми пятиугольниками.[6]

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

Вторая часть Восемнадцатая проблема Гильберта попросил мозаику из одного многогранника Евклидово 3-пространство, такой, что по нему не равногранный (ан анизоэдральный плитка). Проблема, как указано, была решена Карл Рейнхардт в 1928 г., но наборы апериодических листов рассматривались как естественное расширение.[7]Конкретный вопрос об апериодических наборах плиток впервые возник в 1961 г., когда логики Хао Ван пытался определить, Проблема домино разрешима - то есть существует ли алгоритм для определения того, допускает ли данный конечный набор прототипов замощение плоскости. Ван нашел алгоритмы для перечисления наборов тайлов, которые не могут покрывать плоскость мозаикой, и наборов тайлов, которые периодически покрывают ее; тем самым он показал, что такой алгоритм решения существует, если каждый конечный набор прототипов, допускающий разбиение плоскости, также допускает периодическое разбиение.

Эти Ванская плитка дадут только непериодические мозаики плоскости, а значит, являются апериодическими.

Следовательно, когда в 1966 г. Роберт Бергер нашел апериодический набор прототипов, который продемонстрировал, что проблема мозаики на самом деле не разрешима.[8] (Таким образом, процедуры Вана не работают со всеми наборами тайлов, хотя это не делает их бесполезными для практических целей.) Этот первый такой набор, использованный Бергером в его доказательстве неразрешимости, требовал 20 426 тайлов Ванга. Позже Бергер сократил свой сет до 104, и Ханс Лаухли впоследствии был обнаружен апериодический набор, требующий всего 40 плиток Ванга.[9] Набор из 13 плиток, показанный на иллюстрации справа, представляет собой апериодический набор, опубликованный Карел Кулик, II, в 1996 году.

Однако меньший апериодический набор из шести плиток не Ванга был обнаружен Рафаэль М. Робинсон в 1971 г.[10] Роджер Пенроуз обнаружил еще три набора в 1973 и 1974 годах, сократив количество необходимых плиток до двух, и Роберт Амманн открыл несколько новых наборов в 1977 году. Вопрос о том, существует ли апериодический набор только с одним прототипом, известен как проблема Эйнштейна.

Конструкции

Известно несколько конструкций апериодических плиток, даже через сорок лет после новаторской конструкции Бергера. Некоторые конструкции представляют собой бесконечные семейства апериодических наборов плиток.[11][12] Те конструкции, которые были обнаружены, в основном построены несколькими способами, в первую очередь, путем создания некой непериодической иерархической структуры. Несмотря на это, неразрешимость из Проблема домино гарантирует, что должно быть бесконечно много различных принципов построения, и что на самом деле существуют апериодические наборы плиток, для которых не может быть доказательств их апериодичности.

Стоит отметить, что не может быть апериодического набора плиток в одном измерении: это простое упражнение, чтобы показать, что любой набор плиток в строке либо не может быть использован для формирования полной мозаики, либо может использоваться для формирования периодической мозаики. черепица. Апериодичность прототипов требует двух или более измерений.

Рекомендации

  1. ^ Сенешаль, Марджори (1996) [1995]. Квазикристаллы и геометрия (исправленное издание в мягкой обложке). Издательство Кембриджского университета. ISBN  978-0-521-57541-6.
  2. ^ Грюнбаум, Бранко; Джеффри С. Шепард (1986). Плитки и узоры. W.H. Фриман и компания. ISBN  978-0-7167-1194-0.
  3. ^ Набор апериодических прототипов всегда может образовывать бесчисленное множество различных мозаик, вплоть до изометрии, как доказал Николай Долбилин в своей статье 1995 года. Счетность семейства замощений и периодичность замощения
  4. ^ Гарднер, Мартин (Январь 1977 г.). «Математические игры». Scientific American. 236: 111–119.
  5. ^ Гарднер, Мартин (1988). Плитки Пенроуза для тайных шифров. W H Freeman & Co. ISBN  978-0-7167-1987-8.
  6. ^ https://www.quantamagazine.org/pentagon-tiling-proof-solves-century-old-math-problem-20170711/
  7. ^ Сенешаль, стр. 22–24.
  8. ^ Бергер, Роберт (1966). «Неразрешимость проблемы домино». Мемуары Американского математического общества (66): 1–72.
  9. ^ Грюнбаум и Шепард, раздел 11.1.
  10. ^ Робинсон, Рафаэль М. (1971). «Неразрешимость и непериодичность мозаик на плоскости». Inventiones Mathematicae. 12 (3): 177–209. Bibcode:1971InMat..12..177R. Дои:10.1007 / BF01418780.
  11. ^ Гудман-Штраус, Хаим (1998). «Правила совпадения и подстановочные тилинги». Анналы математики. 147 (1): 181–223. CiteSeerX  10.1.1.173.8436. Дои:10.2307/120988. JSTOR  120988.
  12. ^ Мозес, С. (1989). «Тайлинги, системы замещения и порождаемые ими динамические системы». Журнал д'анализа математика. 53 (1): 139–186. Дои:10.1007 / BF02793412.