Апериодический набор прототипов
Набор прототипов является апериодическим, если копии прототипов могут быть собраны для создания мозаики , так что все возможные шаблоны тесселяции являются непериодическими . Упомянутая апериодичность ; является свойством конкретного набора прототилей различные результирующие мозаики сами по себе просто непериодичны.
Данный набор плиток на евклидовой плоскости или в какой-либо другой геометрической конфигурации допускает замощение , если неперекрывающиеся копии плиток в наборе могут быть совмещены, чтобы покрыть все пространство. Данный набор плиток может допускать периодические мозаики, то есть мозаики, которые остаются инвариантными после сдвига в результате перевода (например, решетка из квадратных плиток является периодической). Нетрудно спроектировать набор плиток, допускающий как непериодические, так и периодические замощения. (Например, случайно расположенные мозаики с использованием квадрата 2×2 и прямоугольника 2×1 обычно непериодичны.)
Однако апериодический набор плиток может создавать только непериодические мозаики. [1] [2] Бесконечно много различных мозаик можно получить из одного апериодического набора плиток. [3]
Самыми известными примерами апериодического набора плиток являются различные плитки Пенроуза . [4] [5] Известные апериодические наборы прототайлов можно увидеть в списке апериодических наборов тайлов . Основная неразрешимость проблемы домино подразумевает, что не существует систематической процедуры решения, может ли данный набор плиток замостить плоскость.
История
[ редактировать ]Многоугольники – это плоские фигуры , ограниченные отрезками прямых . Правильные многоугольники имеют все стороны одинаковой длины , а также все углы одинаковой меры . Еще в 325 году нашей эры Папп Александрийский знал, что только три типа правильных многоугольников (квадрат, равносторонний треугольник и шестиугольник) могут идеально сочетаться друг с другом в повторяющихся мозаиках на евклидовой плоскости . Внутри этой плоскости каждый треугольник, независимо от правильности, будет мозаичным. Напротив, правильные пятиугольники не образуют мозаику. Однако неправильные пятиугольники с разными сторонами и углами могут образовывать мозаику. Плоскость покрыта 15 неправильными выпуклыми пятиугольниками. [6]
Многогранники — это трехмерные корреляты многоугольников. Они построены из плоских граней и прямых краев и имеют острые углы в вершинах . Хотя куб — единственный правильный многогранник, допускающий мозаику, многие неправильные трехмерные формы могут быть мозаичными, например усеченный октаэдр .
Вторая часть восемнадцатой проблемы Гильберта требовала замощения одного многогранника в евклидовом трехмерном пространстве , такого, что никакое замощение им не было бы изоэдральным ( анизоэдральная плитка). Заявленная проблема была решена Карлом Рейнхардтом в 1928 году, но наборы апериодических плиток считались естественным продолжением. [7] Конкретный вопрос об апериодических наборах плиток впервые возник в 1961 году, когда логик Хао Ван попытался определить, разрешима ли проблема домино , то есть существует ли алгоритм для определения того, допускает ли данный конечный набор прототайлов мозаику плоскости. . Ван нашел алгоритмы для подсчета наборов тайлов, которые не могут замостить плоскость, и наборов тайлов, которые периодически замостили ее; этим он показал, что такой алгоритм принятия решений существует, если каждый конечный набор прототайлов, допускающий замощение плоскости, также допускает периодическое замощение.
Следовательно, когда в 1966 году Роберт Бергер обнаружил апериодический набор прототайлов, это продемонстрировало, что проблема замощения на самом деле неразрешима. [8] (Таким образом, процедуры Ванга не работают со всеми наборами плиток, хотя это не делает их бесполезными для практических целей.) Для этого первого такого набора, использованного Бергером в его доказательстве неразрешимости, потребовалось 20 426 плиток Ванга. Позже Бергер сократил свой набор до 104, а Ганс Лойхли впоследствии нашел апериодический набор, требующий всего 40 плиток Ванга. [9] Набор из 13 плиток, представленный на иллюстрации справа, представляет собой апериодический набор, опубликованный Карелом Куликом II в 1996 году.
Однако меньший апериодический набор из шести плиток, не принадлежащих Вангу, был обнаружен Рафаэлем М. Робинсоном в 1971 году. [10] Роджер Пенроуз открыл еще три набора в 1973 и 1974 годах, сократив количество необходимых плиток до двух, а Роберт Амманн открыл несколько новых наборов в 1977 году. Вопрос о том, существует ли апериодический набор только с одним прототипом, известен как проблема Эйнштейна .
Конструкции
[ редактировать ]Известно несколько конструкций апериодических мозаик, даже спустя сорок лет после новаторской конструкции Бергера. Некоторые конструкции представляют собой бесконечные семейства апериодических множеств плиток. [11] [12] Те конструкции, которые были обнаружены, в основном построены одним из нескольких способов — в первую очередь путем создания некой непериодической иерархической структуры. Несмотря на это, неразрешимость гарантирует проблемы домино , что должно существовать бесконечно много различных принципов построения и что фактически существуют апериодические наборы плиток, для которых не может быть доказательства их апериодичности.
Стоит отметить, что не может быть апериодического набора плиток в одном измерении: это простое упражнение, чтобы показать, что любой набор плиток в линии либо не может быть использован для формирования полной мозаики, либо может быть использован для формирования периодической мозаики. укладка плитки. Апериодичность прототилей требует двух или более измерений.
Ссылки
[ редактировать ]- ^ Сенешаль, Марджори (1996) [1995]. Квазикристаллы и геометрия (исправленное издание в мягкой обложке). Издательство Кембриджского университета . ISBN 978-0-521-57541-6 .
- ^ Грюнбаум, Бранко ; Джеффри С. Шепард (1986). Плитки и узоры . WH Фриман и компания. ISBN 978-0-7167-1194-0 .
- ^ Набор апериодических прототайлов всегда может образовывать бесчисленное множество различных мозаик, даже с точностью до изометрии, как доказал Николай Долбилин в его статье 1995 года « Счетность семейства плиток и периодичность мозаики».
- ^ Гарднер, Мартин (январь 1977 г.). «Математические игры». Научный американец . 236 (5): 111–119. Бибкод : 1977SciAm.236e.128G . doi : 10.1038/scientificamerican0577-128 .
- ^ Гарднер, Мартин (1988). Плитки Пенроуза к шифрам с люками . WH Freeman & Co. ISBN 978-0-7167-1987-8 .
- ^ «Доказательство мозаики Пентагона решает вековую математическую задачу» . 11 июля 2017 г.
- ^ Сенешаль, стр. 22–24.
- ^ Бергер, Роберт (1966). «Неразрешимость проблемы домино». Мемуары Американского математического общества (66): 1–72.
- ^ Грюнбаум и Шепард, раздел 11.1.
- ^ Робинсон, Рафаэль М. (1971). «Неразрешимость и непериодичность разбиений плоскости». Математические изобретения . 12 (3): 177–209. Бибкод : 1971InMat..12..177R . дои : 10.1007/BF01418780 . S2CID 14259496 .
- ^ Гудман-Штраус, Хаим (1998). «Правила сопоставления и мозаики замены» . Анналы математики . 147 (1): 181–223. CiteSeerX 10.1.1.173.8436 . дои : 10.2307/120988 . JSTOR 120988 .
- ^ Мозес, Шахар (1989). «Разбиения, системы подстановки и порожденные ими динамические системы». Журнал Математического Анализа . 53 (1): 139–186. дои : 10.1007/BF02793412 . S2CID 121775031 .
