Из Википедии, бесплатной энциклопедии
  (Перенаправлено с тайлов Ванга )
Перейти к навигации Перейти к поиску
Этот набор из 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] Этот набор, показанный выше в заголовке, можно более подробно изучить в File: Wang 11 tile.svg .

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

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

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

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

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

В популярной культуре [ править ]

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

См. Также [ править ]

  • Головоломка с подбором краев
  • Загадка Вечности II
  • Перси Александр МакМахон

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

  1. ^ Ван, Хао (1961), «Доказательство теорем с помощью распознавания образов - II», Bell System Technical Journal , 40 (1): 1–41, DOI : 10.1002 / j.1538-7305.1961.tb03975.x. Ван предлагает свои плитки и предполагает, что апериодических множеств не существует.
  2. ↑ Ван, Хао (ноябрь 1965 г.), «Игры, логика и компьютеры», Scientific American : 98–106. Представляет задачу домино для широкой аудитории.
  3. ^ Renz, Питер (1981), "Математическое доказательство: Что это такое и что оно должно быть", The Two-Year College Mathematics Journal , 12 (2): 83-103, DOI : 10,2307 / 3027370.
  4. ^ a b c Бергер, Роберт (1966), "Неразрешимость проблемы домино", Мемуары Американского математического общества , 66 : 72, MR 0216954 . Бергер вводит термин «плитки Ванга» и демонстрирует их первый апериодический набор.
  5. ^ Робинсон, Рафаэль М. (1971), "Неразрешимость и непериодичности для разбиений плоскости", Inventiones Mathematicae , 12 : 177-209, Bibcode : 1971InMat..12..177R , DOI : 10.1007 / bf01418780 , МР 0297572 .
  6. ^ Б Culik, Карел, II (1996), "апериодического набор из 13 Ван плитки", дискретной математики , 160 (1-3): 245-251, DOI : 10.1016 / S0012-365X (96) 00118-5 , Руководство по ремонту 1417576 . (Показан апериодический набор из 13 плиток 5 цветов).
  7. ^ Кари, Яркко~d (1996), "Небольшой апериодический набор Ван плиток", дискретная математика , 160 (1-3): 259-264, DOI : 10.1016 / 0012-365X (95) 00120-L , МР 1417578 .
  8. ^ a b Джендель, Эммануэль; Рао, Майкл (2015), «Апериодический набор из 11 плиток Ванга», CoRR , arXiv : 1506.06492 , Bibcode : 2015arXiv150606492J. (Показан апериодический набор из 11 плиток 4 цветов)}
  9. ^ Кулик, Карел, II; Kari, Яркко (1995), "апериодический набор Ван кубов" , журнал Юниверсал Computer Science , 1 (10): 675-686, DOI : 10.1007 / 978-3-642-80350-5_57 , MR 1392428 .
  10. ^ Winfree, E .; Лю, Ф .; Венцлер, Луизиана; Симэн, NC (1998), "Проектирование и самосборка двумерных кристаллов ДНК", Nature , 394 : 539-544, Bibcode : 1998Natur.394..539W , DOI : 10.1038 / 28998 , PMID 9707114 .
  11. ^ Lukeman, P .; Seeman, N .; Миттал, А. (2002), «Гибридные наносистемы ПНК / ДНК», 1-я Международная конференция по наномасштабной / молекулярной механике (N-M2-I), Outrigger Wailea Resort, Мауи, Гавайи..
  12. ^ Stam, Jos (1997), Апериодическое отображение текстуры (PDF) . Предлагает идею использования плиток Ванга для изменения текстуры с детерминированной системой замены.
  13. ^ Нейрет, Фабрис; Кани, Marie-Paule (1999), "Pattern-Based Текстурирование Revisited", ACM SIGGRAPH 1999 (PDF) , Лос - Анджелес, Соединенные Штаты Америки:. ACM, стр 235--242, DOI : 10,1145 / 311535,311561 . Вводит стохастический тайлинг.
  14. ^ Коэн, Майкл Ф .; Тень, Джонатан; Хиллер, Стефан; Дейссен, Оливер (2003), "Ван плитки для изображения и текстуры поколения", ACM SIGGRAPH 2003 (PDF) , Нью - Йорк, Нью - Йорк, США:. ACM, стр 287-294, DOI : 10,1145 / +1201775,882265 , ISBN  1-58113-709-5, архивировано из оригинального (PDF) 18 марта 2006 г..
  15. ↑ Wei, Li-Yi (2004), « Построение мозаичного отображения текстуры на графическом оборудовании», Труды конференции ACM SIGGRAPH / EUROGRAPHICS по графическому оборудованию (HWWS '04) , Нью-Йорк, Нью-Йорк, США: ACM, стр. 55 -63, DOI : 10,1145 / 1058129,1058138 , ISBN 3-905673-15-0. Применяет плитки Ванга для текстурирования в реальном времени на графическом процессоре.
  16. ^ . Копф, Йоханнес; Коэн-Ор, Даниэль; Деуссен, Оливер; Lischinski, Дани (2006), "Рекурсивный Ван плитки в режиме реального времени голубой шум", ACM SIGGRAPH 2006 , Нью - Йорк, Нью - Йорк, США.: ACM, С. 509-518, DOI : 10,1145 / 1179352,1141916 , ISBN 1-59593-364-6. Показывает расширенные приложения.
  17. ↑ Кари, Яркко (1990), «Обратимость двумерных клеточных автоматов неразрешима», Клеточные автоматы: теория и эксперимент (Лос-Аламос, Нью-Мексико, 1989) , Physica D: нелинейные явления , 45 , стр. 379–385, Bibcode : 1990PhyD ... 45..379K , DOI : 10.1016 / 0167-2789 (90) 90195-У , МР 1094882 .
  18. Перейти ↑ Burnham, Karen (2014), Грег Иган , Modern Masters of Science Fiction, University of Illinois Press, pp. 72–73, ISBN 9780252096297.

Дальнейшее чтение [ править ]

  • Грюнбаум, Бранко ; Шепард, GC (1987), Tilings and Patterns , New York: WH Freeman, ISBN 0-7167-1193-1.

Внешние ссылки [ править ]

  • Страница Стивена Датча, включающая множество изображений апериодических мозаик
  • Анимированная демонстрация наивного метода мозаики Ванга - требуется Javascript и HTML5