Плитка Ван - Wang tile - Wikipedia

Этот набор из 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 tile.svg.

Обобщения

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

Приложения

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

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

В популярной культуре

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

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

Рекомендации

  1. ^ Ван, Хао (1961), «Доказательство теорем с помощью распознавания образов - II», Технический журнал Bell System, 40 (1): 1–41, Дои:10.1002 / j.1538-7305.1961.tb03975.x. Ван предлагает свои плитки и предполагает, что апериодических множеств не существует.
  2. ^ Ван, Хао (Ноябрь 1965 г.), «Игры, логика и компьютеры», Scientific American: 98–106. Представляет задачу домино для широкой аудитории.
  3. ^ Ренц, Питер (1981), «Математическое доказательство: что это такое и каким оно должно быть», Двухлетний математический журнал колледжа, 12 (2): 83–103, Дои:10.2307/3027370.
  4. ^ а б c Бергер, Роберт (1966), «Неразрешимость проблемы домино», Мемуары Американского математического общества, 66: 72, МИСТЕР  0216954. Бергер вводит термин «плитки Ванга» и демонстрирует их первый апериодический набор.
  5. ^ Робинсон, Рафаэль М. (1971), «Неразрешимость и непериодичность мозаик на плоскости», Inventiones Mathematicae, 12: 177–209, Bibcode:1971InMat..12..177R, Дои:10.1007 / bf01418780, МИСТЕР  0297572.
  6. ^ а б Кулик, Карел, II (1996), "Апериодический набор из 13 плиток Ванга", Дискретная математика, 160 (1–3): 245–251, Дои:10.1016 / S0012-365X (96) 00118-5, МИСТЕР  1417576. (Показан апериодический набор из 13 плиток 5 цветов).
  7. ^ Кари, Яркко (1996), "Небольшой апериодический набор плиток Ванга", Дискретная математика, 160 (1–3): 259–264, Дои:10.1016 / 0012-365X (95) 00120-L, МИСТЕР  1417578.
  8. ^ а б Джендель, Эммануэль; Рао, Майкл (2015), «Апериодический набор из 11 плиток Ванга», CoRR, arXiv:1506.06492, Bibcode:2015arXiv150606492J. (Показан апериодический набор из 11 плиток 4 цветов)}
  9. ^ Кулик, Карел, II; Кари, Яркко (1995), «Апериодический набор кубиков Ванга», Журнал универсальных компьютерных наук, 1 (10): 675–686, Дои:10.1007/978-3-642-80350-5_57, МИСТЕР  1392428.
  10. ^ Winfree, E .; Лю, Ф .; Wenzler, L.A .; Seeman, N.C. (1998), "Дизайн и самосборка двумерных кристаллов ДНК", Природа, 394: 539–544, Bibcode:1998Натура.394..539Вт, Дои:10.1038/28998, PMID  9707114.
  11. ^ Lukeman, P .; Seeman, N .; Миттал, А. (2002), «Гибридные наносистемы ПНК / ДНК», 1-я Международная конференция по наномасштабной / молекулярной механике (N-M2-I), Outrigger Wailea Resort, Мауи, Гавайи.
  12. ^ Стам, Джос (1997), Апериодическое отображение текстуры (PDF). Предлагает идею использования плиток Ванга для изменения текстуры с детерминированной системой замены.
  13. ^ Нейрет, Фабрис; Кани, Мари-Поль (1999), «Повторение текстурирования на основе шаблонов», ACM SIGGRAPH 1999 г. (PDF), Лос-Анджелес, США: ACM, стр. 235--242, Дои:10.1145/311535.311561. Вводит стохастический тайлинг.
  14. ^ Коэн, Майкл Ф.; Тень, Джонатан; Хиллер, Стефан; Деуссен, Оливер (2003), «Плитки Ванга для создания изображений и текстур», ACM SIGGRAPH 2003 (PDF), Нью-Йорк, Нью-Йорк, США: ACM, стр. 287–294, Дои:10.1145/1201775.882265, ISBN  1-58113-709-5, заархивировано из оригинал (PDF) на 2006-03-18.
  15. ^ Вэй, Ли-Йи (2004 г.), «Плитка наложения текстур на графическом оборудовании», Материалы конференции ACM SIGGRAPH / EUROGRAPHICS по графическому оборудованию (HWWS '04), Нью-Йорк, Нью-Йорк, США: ACM, стр. 55–63, Дои:10.1145/1058129.1058138, ISBN  3-905673-15-0. Применяет плитки Ванга для текстурирования в реальном времени на графическом процессоре.
  16. ^ . Копф, Йоханнес; Коэн-Ор, Даниэль; Деуссен, Оливер; Лищинский, Дэни (2006), "Рекурсивные плитки Ванга для синего шума в реальном времени", ACM SIGGRAPH 2006, Нью-Йорк, Нью-Йорк, США: ACM, стр. 509–518, Дои:10.1145/1179352.1141916, ISBN  1-59593-364-6. Показывает расширенные приложения.
  17. ^ Кари, Яркко (1990), «Обратимость двумерных клеточных автоматов неразрешима», Клеточные автоматы: теория и эксперимент (Лос-Аламос, Нью-Мексико, 1989), Physica D: нелинейные явления, 45, стр. 379–385, Bibcode:1990 ФИД ... 45..379K, Дои:10.1016 / 0167-2789 (90) 90195-У, МИСТЕР  1094882.
  18. ^ Бернхэм, Карен (2014), Грег Иган, Modern Masters of Science Fiction, University of Illinois Press, стр. 72–73, ISBN  9780252096297.

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

внешняя ссылка