Плитки Вана

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Этот набор из 11 плиток Вана может заполнить плоскость только апериодично.
Пример замощения Вана 13-ю плитками.

Плитки Вана (или домино Вана), впервые предложенные математиком, логиком и философом Хао Ваном в 1961, — это класс формальных систем. Они моделируются визуально с помощью квадратных плиток с раскрашиванием каждой стороны. Определяется набор таких плиток (например, как на иллюстрации), затем копии этих плиток прикладываются друг к другу с условием согласования цветов сторон, но без вращения или симметрического отражения плиток.

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

Задача домино[править | править код]

В 1961-м году Ван высказал гипотезу, что если конечное число плиток Вана может замостить плоскость, то существует периодическое замощение, то есть мозаика, инвариантная относительно параллельного переноса на вектора в двумерной решётке наподобие обоев. Он также заметил, что эта гипотеза имеет следствием существование алгоритма, определяющего, может ли данный конечный набор плиток Вана замостить плоскость[1][2]. Идея ограничения соединения смежных плиток возникла в игре домино, так что плитки Вана известны также под названием домино Вана [3], а алгоритмическая задача определения, могут ли плитки замостить плоскость, получила известность как задача домино [4].

По словам студента Вана Роберта Бергера[en] [4],

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

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

В 1966 Бергер решил задачу домино, опровергнув гипотезу Вана. Он доказал, что не может существовать алгоритма, показав, как преобразовать любую машину Тьюринга в набор плиток Вана, так что плитки замощают плоскость в том и только в том случае, если машина Тьюринга не останавливается. Из невозможности решить проблему остановки (задачу проверки, остановится ли, в конце концов, машина Тьюринга) тогда следует невозможность решить задачу замощения Вана [4][4].

Апериодические наборы плиток[править | править код]

Комбинация результата Бергера с наблюдением Вана показывает, что должен существовать конечный набор плиток Вана, замощающих плоскость, но лишь непериодично[en]. Этим свойством обладает мозаика Пенроуза и расположение атомов в квазикристалле. Хотя оригинальный набор Бергера содержал 20.426 плиток, он предположил, что меньшие наборы могут также существовать, включая подмножества его оригинального набора, и в неопубликованных тезисах его диссертации он сократил число плиток до 104. Позднее были найдены ещё меньшие наборы [5][6][7]. Например, набор из 11 плиток и 4 цветов, приведённый выше, является непериодическим набором, и был открыт Эммануэлем Жанделем и Майклом Рао в 2015 году, используя полный перебор для доказательства того, что 10 плиток или 3 цветов недостаточно для апериодичности[8].

Обобщения[править | править код]

Плитки Вана можно обобщить различными способами и все они также неразрешимы в вышеприведённом смысле. Например, кубы Вана — это кубы одинакового размера с раскрашенными гранями, которые должны совмещаться по цвету при создании многогранных замощений (сот). Кулик и Кари показали непериодичные наборы кубов Вана [9]. Винфри и др. показали возможность создания молекулярных «плиток» на основе ДНК (дезоксирибонуклеиновой кислоты), которые могут действовать наподобие плиток Вана [10]. Миттал и др. показали, что этими плитками можно составить пептидо-нуклеиновые кислоты (ПНК), устойчивые искусственные подобия ДНК[11].

Приложения[править | править код]

Плитки Вана недавно стали популярным средством создания алгоритмических[en] текстур, полей высот и других больших неповторяющихся двумерных наборов данных. Небольшое число заранее вычисленных или созданных вручную плиток могут быть собраны быстро и дёшево без очевидных повторений и периодичности. В этом случае обычные непериодичные мозаики показали бы свою структуру. Куда менее ограничивающие наборы, которые обеспечивают выбор по меньшей мере двух вариантов для любых двух цветов сторон, более приемлемы, поскольку замощаемость легко обеспечивается и каждая плитка может быть выбрана псевдослучайно [12][13][14][15]. Плитки Вана используются также при проверке разрешимости теории клеточных автоматов [16].

В культуре[править | править код]

Короткий рассказ Грега Игана «Ковёр Вана», впоследствии расширенный до новеллы «Диаспора»[en], рассказывает о вселенной, заполненной организмами и мыслящими существами в виде плиток Вана, образованными узорами сложных молекул[17].

См. также[править | править код]

Примечания[править | править код]

  1. ↑ Wang, 1961, с. 1–41.
  2. ↑ Wang, 1965, с. 98–106.
  3. ↑ Renz, 1981, с. 83–103.
  4. ↑ 1 2 3 4 Berger, 1966, с. 72.
  5. ↑ Robinson, 1971, с. 177–209.
  6. ↑ Culik, 1996, с. 245–251.
  7. ↑ Kari, 1996, с. 259–264.
  8. ↑ Jeandel, Emmanuel; Rao, Michael (2015), "An aperiodic set of 11 Wang tiles", CoRR, arXiv:1506.06492. (Showed an aperiodic set of 11 tiles with 4 colors)}
  9. ↑ Culik, Kari, 1995, с. 675–686.
  10. ↑ Winfree, Liu, Wenzler, Seeman, 1998, с. 539–544.
  11. ↑ Lukeman, Seeman, Mittal, 2002.
  12. ↑ Stam, 1997.
  13. ↑ Cohen, Shade, Hiller, Deussen, 2003, с. 287–294.
  14. ↑ Wei, 2004, с. 55–63.
  15. ↑ Kopf, Cohen-Or, Deussen, Lischinski, 2006, с. 509–518.
  16. ↑ Kari, 1990, с. 379–385.
  17. ↑ Burnham, 2014, с. 72–73.

Литература[править | править код]

  • Hao Wang. Proving theorems by pattern recognition—II // Bell System Technical Journal. — 1961. — Т. 40, вып. 1. — doi:10.1002/j.1538-7305.1961.tb03975.x.. Ван вводит свои плитки и высказывает гипотезу, что нет непериодических множеств.
  • Hao Wang. Games, logic and computers // Scientific American. — 1965. — Вып. November.. Представляет задачу домино для популярной аудитории.
  • Peter Renz. Mathematical proof: What it is and what it ought to be // The Two-Year College Mathematics Journal. — 1981. — Т. 12, вып. 2. — doi:10.2307/3027370.
  • Robert Berger. The undecidability of the domino problem // Memoirs of the American Mathematical Society. — 1966. — Т. 66.. Бергер вводит понятие «плитки Вана» и демонстрирует первое непериодическое множество на них.
  • Raphael M. Robinson. Undecidability and nonperiodicity for tilings of the plane // Inventiones Mathematicae. — 1971. — Т. 12. — doi:10.1007/bf01418780.
  • Karel Culik. An aperiodic set of 13 Wang tiles // Discrete Mathematics. — 1996. — Т. 160, вып. 1—3. — doi:10.1016/S0012-365X(96)00118-5.
  • Jarkko Kari. A small aperiodic set of Wang tiles // Discrete Mathematics. — 1996. — Т. 160, вып. 1—3. — doi:10.1016/0012-365X(95)00120-L.
  • Karel Culik, Jarkko Kari. An aperiodic set of Wang cubes // Journal of Universal Computer Science. — 1995. — Т. 1, вып. 10. — doi:10.1007/978-3-642-80350-5_57.
  • E. Winfree, F. Liu, L.A. Wenzler, N.C. Seeman. Design and self-assembly of two-dimensional DNA crystals // Nature. — 1998. — Т. 394. — doi:10.1038/28998. — PMID 9707114.
  • P. Lukeman, N. Seeman, A. Mittal. 1st International Conference on Nanoscale/Molecular Mechanics (N-M2-I), Outrigger Wailea Resort, Maui, Hawaii. — 2002.
  • Jos Stam. Aperiodic Texture Mapping. — 1997.
  • Michael F. Cohen, Jonathan Shade, Stefan Hiller, Oliver Deussen. ACM SIGGRAPH 2003. — New York, NY, USA: ACM, 2003. — ISBN 1-58113-709-5. — doi:10.1145/1201775.882265.. Случайные мозаики.
  • Li-Yi Wei. Proceedings of the ACM SIGGRAPH/EUROGRAPHICS Conference on Graphics Hardware (HWWS '04). — New York, NY, USA: ACM, 2004. — ISBN 3-905673-15-0. — doi:10.1145/1058129.1058138.. Применение плиток Вана для создания текстуры в GPU.
  • Johannes Kopf, Daniel Cohen-Or, Oliver Deussen, Dani Lischinski. ACM SIGGRAPH 2006. — New York, NY, USA, 2006. — ISBN 1-59593-364-6. — doi:10.1145/1179352.1141916.. Показывает приложения.
  • Jarkko Kari. Cellular automata: theory and experiment (Los Alamos, NM, 1989). — 1990. — Т. 45. — (Physica D: Nonlinear Phenomena). — doi:10.1016/0167-2789(90)90195-U.
  • Karen Burnham. Greg Egan. — University of Illinois Press, 2014. — (Modern Masters of Science Fiction). — ISBN 9780252096297.
  • Branko Grünbaum, G.C. Shephard. Tilings and Patterns. — New York: W. H. Freeman, 1987. — ISBN 0-7167-1193-1..

Ссылки[править | править код]

Источник — https://wiki4.ru/w/index.php?title=Плитки_Вана&oldid=118099103