Плитки Вана

Плитки Вана (або доміно Вана), вперше запропоновані математиком, логіком і філософом Хао Ваном^[ru] в 1961, — це клас формальних систем. Вони моделюються візуально за допомогою квадратних плиток з розфарбуванням кожного боку. Визначається набір таких плиток (наприклад, як на ілюстрації), потім копії цих плиток прикладаються одна до одної з умовою узгодження кольорів сторін, але без обертання або симетричного відображення плиток.

Основне питання про набір плиток Вана — чи можуть вони замостити площину чи ні, тобто чи можна площину заповнити таким способом. Наступне питання, чи можна її заповнити у вигляді періодичного візерунка.

Задача доміно

В 1961 році Ван висловив гіпотезу, що якщо скінченне число плиток Вана може замостити площину, то існує періодичне замощення, тобто мозаїка, інваріантна відносно паралельного перенесення на вектор у двовивимірній решітці на зразок шпалер. Він також зауважив, що ця гіпотеза має наслідком існування алгоритму, що визначає, чи може даний скінченний набір плиток Вана замостити площину^[1]^[2]. Ідея обмеження з'єднання суміжних плиток виникла в грі доміно, так що плитки Вана відомі також під назвою доміно Вана^[3], а алгоритмічна задача визначення, чи можуть плитки замостити площину, здобула популярність як задача доміно^[4].

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

Задача доміно має справу з класом усіх наборів доміно. Задача полягає у визначенні для кожного набору доміно, можливе чи ні замощення. Ми говоримо, що задачу доміно розв'язна або нерозв'язна, залежно від того, існує чи ні алгоритм, який за заданим набором довільного набору доміно визначає, можна розв'язати чи ні задачу замощення для цього набору.

Іншими словами, в задачі доміно запитується, чи існує ефективний метод, який правильно розв'язує задачу для заданих наборів доміно.

1966 року Бергер розв'язав задачу доміно, спростувавши гіпотезу Вана. Він довів, що не може існувати алгоритму, показавши, як перетворити будь-яку машину Тюрінга на набір плиток Вана, так що плитки замощують площину тоді й лише тоді, коли машина Тюрінга не зупиняється. З неможливості розв'язати проблему зупинки (завдання перевірки, чи зупиниться, зрештою, машина Тюрінга) тоді випливає неможливість розв'язати задачу замощення Вана^[4]^[4].

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

Комбінація результату Бергера зі спостереженням Вана показує, що повинен існувати скінченний набір плиток Вана, які замощують площину, але лише неперіодично. Цю властивість має мозаїка Пенроуза і розташування атомів у квазікристалі. Хоча оригінальний набір Бергера містив 20 426 плиток, він припустив, що менші набори можуть також існувати, зокрема підмножини його оригінального набору, та в опублікованих тезах його дисертації він скоротив число плиток до 104. Пізніше знайдено ще менші набори^[5]^[6]^[7]. Наприклад, набір з 11 плиток і 4 кольорів, наведений вище, є неперіодичним набором, і його відкрили Еммануель Жандель і Майкл Рао в 2015 році, використовуючи повний перебір для доведення того, що 10 плиток або 3 кольорів недостатньо для аперіодичності^[8].

Узагальнення

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

Застосування

Плитки Вана нещодавно стали популярним засобом створення алгоритмічних текстур, полів висот та інших великих неповторюваних двовимірних наборів даних. Невелике число заздалегідь обчислених або створених вручну плиток можна зібрати швидко і дешево без очевидних повторень та періодичності. В цьому випадку звичайні неперіодичні мозаїки показали б свою структуру. Набори зі значно меншими обмеженнями, які забезпечують вибір щонайменше двох варіантів для будь-яких двох кольорів сторін, більш прийнятні, оскільки замощуваність легко забезпечується і кожну плитку можна обрати псевдовипадково^[12]^[13]^[14]^[15]. Плитки Вана використовуються також під час перевірки розв'язності теорії клітинних автоматів^[16].

В культурі

Коротке оповідання Грега Ігена «Килим Вана», згодом розширене до роману «Діаспора»^[en], розповідає про всесвіт, заповнений організмами і мислячими істотами у вигляді плиток Вана, утвореними візерунками складних молекул^[17].

Див. також

Примітки

↑ Wang, 1961, с. 1–41.
↑ Wang, 1965, с. 98–106.
↑ Renz, 1981, с. 83–103.
↑ ^а ^б ^в ^г Berger, 1966, с. 72.
↑ Robinson, 1971, с. 177–209.
↑ Culik, 1996, с. 245–251.
↑ Kari, 1996, с. 259–264.
↑ Jeandel, Emmanuel; Rao, Michael (2015), An aperiodic set of 11 Wang tiles, CoRR, arXiv:1506.06492. (Показано неперіодичний набір з 11 плиток з 4 кольорами)}
↑ Culik, Kari, 1995, с. 675–686.
↑ Winfree, Liu, Wenzler, Seeman, 1998, с. 539–544.
↑ Lukeman, Seeman, Mittal, 2002.
↑ Stam, 1997.
↑ Cohen, Shade, Hiller, Deussen, 2003, с. 287–294.
↑ Wei, 2004, с. 55–63.
↑ Kopf, Cohen-Or, Deussen, Lischinski, 2006, с. 509–518.
↑ Kari, 1990, с. 379–385.
↑ Burnham, 2014, с. 72–73.

Література

Hao Wang. Proving theorems by pattern recognition—II // Bell System Technical Journal. — 1961. — Т. 40, вип. 1 (28 грудня). — DOI:10.1002/j.1538-7305.1961.tb03975.x.. Ван вводить свої плитки і висловлює гіпотезу, що немає неперіодичних множин.
Hao Wang. Games, logic and computers // Scientific American. — 1965. — Вип. November (28 грудня). Представляє задачу доміно популярній аудиторії.
Peter Renz. Mathematical proof: What it is and what it ought to be // The Two-Year College Mathematics Journal. — 1981. — Т. 12, вип. 2 (28 грудня). — DOI:10.2307/3027370.
Robert Berger. The undecidability of the domino problem // Memoirs of the American Mathematical Society. — 1966. — Т. 66 (28 грудня). Бергер уводить поняття «плитки Вана» і демонструє першу неперіодичну множину на них.
Raphael M. Robinson. Undecidability and nonperiodicity for tilings of the plane // Inventiones Mathematicae. — 1971. — Т. 12 (28 грудня). — DOI:10.1007/bf01418780.
Karel Culik. An aperiodic set of 13 Wang tiles // Discrete Mathematics. — 1996. — Т. 160, вип. 1—3 (28 грудня). — DOI:10.1016/S0012-365X(96)00118-5.
Jarkko Kari. A small aperiodic set of Wang tiles // Discrete Mathematics. — 1996. — Т. 160, вип. 1—3 (28 грудня). — 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 (28 грудня). — 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 (28 грудня). — 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. — 28 грудня.
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.. Застосування плиток Вана для створення текстури в ГП.
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..

Посилання

Сторінка Стівена Датча з багатьма зображеннями неперіодичних замощень
Animated demonstration of a naïve Wang tiling method — вимагає Javascript і HTML5

[FOOTNOTEWang19611–41-1] Wang, 1961, с. 1–41.

[FOOTNOTEWang196598–106-2] Wang, 1965, с. 98–106.

[FOOTNOTERenz198183–103-3] Renz, 1981, с. 83–103.

[FOOTNOTEBerger196672-4] а ^б ^в ^г Berger, 1966, с. 72.

[FOOTNOTERobinson1971177–209-5] Robinson, 1971, с. 177–209.

[FOOTNOTECulik1996245–251-6] Culik, 1996, с. 245–251.

[FOOTNOTEKari1996259–264-7] Kari, 1996, с. 259–264.

[jeandel-8] Jeandel, Emmanuel; Rao, Michael (2015), An aperiodic set of 11 Wang tiles, CoRR, arXiv:1506.06492. (Показано неперіодичний набір з 11 плиток з 4 кольорами)}

[FOOTNOTECulik,_Kari1995675–686-9] Culik, Kari, 1995, с. 675–686.

[FOOTNOTEWinfree,_Liu,_Wenzler,_Seeman1998539–544-10] Winfree, Liu, Wenzler, Seeman, 1998, с. 539–544.

[FOOTNOTELukeman,_Seeman,_Mittal2002-11] Lukeman, Seeman, Mittal, 2002.

[FOOTNOTEStam1997-12] Stam, 1997.

[FOOTNOTECohen,_Shade,_Hiller,_Deussen2003287–294-13] Cohen, Shade, Hiller, Deussen, 2003, с. 287–294.

[FOOTNOTEWei200455–63-14] Wei, 2004, с. 55–63.

[FOOTNOTEKopf,_Cohen-Or,_Deussen,_Lischinski2006509–518-15] Kopf, Cohen-Or, Deussen, Lischinski, 2006, с. 509–518.

[FOOTNOTEKari1990379–385-16] Kari, 1990, с. 379–385.

[FOOTNOTEBurnham201472–73-17] Burnham, 2014, с. 72–73.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]