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