Плитка Ван
Квадратные плитки с цветом на каждой стороне
Этот набор из 11 плиток Вана будет замощать плоскость, но только апериодически .
На Викискладе есть медиафайлы по теме «Плитки Вана» .

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

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

Проблема домино

Пример мозаики Вана с 13 плитками.

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

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

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

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

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

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

Плитки Вана сделаны монохромными путем замены краев каждого квадранта фигурой, соответствующей его цвету – этот набор изоморфен минимальному набору Жанделя и Рао, приведенному выше.

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

Наименьший набор апериодических плиток был обнаружен Эммануэлем Жанделем и Майклом Рао в 2015 году, с 11 плитками и 4 цветами. Они использовали исчерпывающий компьютерный поиск, чтобы доказать, что 10 плиток или 3 цвета недостаточно для обеспечения апериодичности. [8] Этот набор, показанный выше на заглавном изображении, можно рассмотреть более подробно в Файл: Wang 11 tiles.svg .

Обобщения

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

Приложения

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

Плитки Вана также использовались в доказательствах разрешимости теории клеточных автоматов . [17]

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

Одна из плиток Вана напоминает флаг народа майя .

Смотрите также

Ссылки

  1. ^ Ван, Хао (1961), «Доказательство теорем с помощью распознавания образов — II», Bell System Technical Journal , 40 (1): 1– 41, doi :10.1002/j.1538-7305.1961.tb03975.x. Ван предлагает свои плитки и предполагает, что не существует апериодических множеств.
  2. ↑ Ван, Хао (ноябрь 1965 г.), «Игры, логика и компьютеры», Scientific American , 213 (5): 98–106 , doi :10.1038/scientificamerican1165-98. Представляет задачу домино для широкой аудитории.
  3. ^ Ренц, Питер (1981), «Математическое доказательство: что это такое и каким оно должно быть», The Two-Year College Mathematics Journal , 12 (2): 83–103 , doi :10.2307/3027370, JSTOR  3027370.
  4. ^ abc Бергер, Роберт (1966), «Неразрешимость проблемы домино», Мемуары Американского математического общества , 66 : 72, MR  0216954. Бергер вводит термин «плитки Вана» и демонстрирует первый апериодический их набор.
  5. ^ Робинсон, Рафаэль М. (1971), «Неразрешимость и непериодичность для разбиений плоскости», Inventiones Mathematicae , 12 (3): 177– 209, Bibcode : 1971InMat..12..177R, doi : 10.1007/bf01418780, MR  0297572, S2CID  14259496.
  6. ^ ab Culik, Karel II (1996), "Апериодический набор из 13 плиток Вана", Discrete Mathematics , 160 ( 1– 3): 245– 251, doi : 10.1016/S0012-365X(96)00118-5 , MR  1417576. (Показан апериодический набор из 13 плиток 5 цветов.)
  7. ^ Кари, Яркко (1996), «Небольшой апериодический набор плиток Вана», Дискретная математика , 160 ( 1–3 ): 259–264 , doi : 10.1016/0012-365X(95)00120-L , MR  1417578.
  8. ^ ab Jeandel, Emmanuel; Rao, Michaël (2021), «Апериодический набор из 11 плиток Вана», Advances in Combinatorics : 1:1–1:37, arXiv : 1506.06492 , doi :10.19086/aic.18614, MR  4210631, S2CID  13261182. (Показан апериодический набор из 11 плиток с 4 цветами и доказано, что меньшее количество плиток или меньшее количество цветов не могут быть апериодическими.)
  9. ^ Кулик, Карел II; Кари, Яркко (1995), «Апериодический набор кубов Вана», Журнал универсальной компьютерной науки , 1 (10): 675– 686, doi :10.1007/978-3-642-80350-5_57, MR  1392428.
  10. ^ Уинфри, Э.; Лю, Ф.; Венцлер, Л.А.; Симан, Н.К. (1998), «Проектирование и самосборка двумерных кристаллов ДНК», Nature , 394 (6693): 539– 544, Bibcode : 1998Natur.394..539W, doi : 10.1038/28998, PMID  9707114, S2CID  4385579.
  11. ^ Люкман, П.; Симан, Н.; Миттал, А. (2002), «Гибридные наносистемы ПНК/ДНК», 1-я Международная конференция по наномасштабной/молекулярной механике (N-M2-I), Outrigger Wailea Resort, Мауи, Гавайи.
  12. ^ Стэм, Джос (1997), Апериодическое текстурное отображение (PDF). Представляет идею использования плиток Вана для изменения текстуры с детерминированной системой замены.
  13. ^ Нейре, Фабрис; Кани, Мари-Поль (1999), «Повторный взгляд на текстурирование на основе шаблонов», Труды 26-й ежегодной конференции по компьютерной графике и интерактивным технологиям — SIGGRAPH '99 (PDF) , Лос-Анджелес, США: ACM, стр.  235–242 , doi :10.1145/311535.311561, ISBN 0-201-48560-5, S2CID  11247905. Вводит стохастическую мозаику.
  14. ^ Коэн, Майкл Ф.; Шейд, Джонатан; Хиллер, Стефан; Дойссен, Оливер (2003), «Плитки Вана для генерации изображений и текстур», ACM SIGGRAPH 2003 Статьи по - SIGGRAPH '03 (PDF) , Нью-Йорк, США: ACM, стр.  287–294 , doi :10.1145/1201775.882265, ISBN 1-58113-709-5, S2CID  207162102, архивировано из оригинала (PDF) 2006-03-18.
  15. ^ Вэй, Ли-И (2004), «Наложение текстур на основе тайлов на графическое оборудование», Труды конференции ACM SIGGRAPH/EUROGRAPHICS по графическому оборудованию (HWWS '04), Нью-Йорк, США: ACM, стр.  55–63 , doi :10.1145/1058129.1058138, ISBN 3-905673-15-0, S2CID  53224612. Применяет Wang Tiles для текстурирования в реальном времени на GPU.
  16. ^ . Копф, Йоханнес; Коэн-Ор, Дэниел; Дойссен, Оливер; Лишински, Дани (2006), «Рекурсивные плитки Вана для синего шума в реальном времени», ACM SIGGRAPH 2006 Статьи по - SIGGRAPH '06, Нью-Йорк, США: ACM, стр.  509–518 , doi :10.1145/1179352.1141916, ISBN 1-59593-364-6, S2CID  11007853. Показывает расширенные приложения.
  17. ^ Кари, Яркко (1990), «Обратимость двумерных клеточных автоматов неразрешима», Клеточные автоматы: теория и эксперимент (Лос-Аламос, Нью-Мексико, 1989) , Physica D: Nonlinear Phenomena , т. 45, стр.  379–385 , Bibcode : 1990PhyD...45..379K, doi : 10.1016/0167-2789(90)90195-U, MR  1094882.
  18. ^ Бернхэм, Карен (2014), Грег Эган, Современные мастера научной фантастики, Издательство Иллинойсского университета, стр.  72–73 , ISBN 978-0-252-09629-7.

Дальнейшее чтение

  • Страница Стивена Датча, содержащая множество изображений апериодичных мозаик
  • Анимированная демонстрация простого метода мозаики Вана — требуются Javascript и HTML5
Взято с "https://en.wikipedia.org/w/index.php?title=Wang_tile&oldid=1266063405#Domino_problem"