Плитки Вана: различия между версиями

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Следующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
Перевод статьи "Wang tile" с английского
(нет различий)

Версия от 16:10, 4 января 2016

Этот набор из 13 плиток Вана может заполнить плоскость только апериодично[англ.]*.
Пример замощения Вана 13-ю плитками.

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

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

Задача домино

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

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

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

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

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

Апериодические наборы плиток

Комбинация результата Бергера с наблюдением Вана показывает, что должен существовать конечный набор плиток Вана, замощающих плоскость, но лишь непериодично[англ.]. Этим свойством обладает мозаика Пенроуза и расположение атомов в квазикристалле. Хотя оригинальный набор Бергера содержал 20.426 плиток, он предположил, что меньшие наборы могут также существовать, включая подмножества его оригинального набора, и в неопубликованных тезисах его диссертации он сократил число плиток до 104. Позднее были найдены ещё меньшие наборы [5][6][7]. Например, набор из 13 плиток, приведённый выше, является непериодическим набором (по публикации Карела Кулика в 1996) [6].

Обобщения

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

Приложения

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

В культуре

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

См. также

Примечания

  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. ↑ 1 2 Culik, 1996, с. 245–251.
  7. ↑ Kari, 1996, с. 259–264.
  8. ↑ Culik, Kari, 1995, с. 675–686.
  9. ↑ Winfree, Liu, Wenzler, 1998, с. 539–544.
  10. ↑ Lukeman, Seeman, Mittal, 2002.
  11. ↑ Stam, 1997.
  12. ↑ Cohen, Shade, Hiller, Deussen, 2003, с. 287–294.
  13. ↑ Wei, 2004, с. 55–63.
  14. ↑ Kopf, Cohen-Or, Deussen, Lischinski, 2006, с. 509–518.
  15. ↑ Kari, 1990, с. 379–385.
  16. ↑ 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.

Литература для дальнейшего чтения

Ссылки

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