Русская Википедия:Плитки Вана

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Файл:Wang 11 tiles.svg
Этот набор из 11 плиток Вана может заполнить плоскость только апериодично.
Файл:Wang tesselation.svg
Пример замощения Вана 13-ю плитками.

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

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

Задача домино

В 1961-м году Ван высказал гипотезу, что если конечное число плиток Вана может замостить плоскость, то существует периодическое замощение, то есть мозаика, инвариантная относительно параллельного переноса на вектора в двумерной решётке наподобие обоев. Он также заметил, что эта гипотеза имеет следствием существование алгоритма, определяющего, может ли данный конечный набор плиток Вана замостить плоскостьШаблон:SfnШаблон:Sfn. Идея ограничения соединения смежных плиток возникла в игре домино, так что плитки Вана известны также под названием домино Вана Шаблон:Sfn, а алгоритмическая задача определения, могут ли плитки замостить плоскость, получила известность как задача домино Шаблон:Sfn.

По словам студента Вана Шаблон:Не переведено 5 Шаблон:Sfn,

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

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

В 1966 Бергер решил задачу домино, опровергнув гипотезу Вана. Он доказал, что не может существовать алгоритма, показав, как преобразовать любую машину Тьюринга в набор плиток Вана, так что плитки замощают плоскость в том и только в том случае, если машина Тьюринга не останавливается. Из невозможности решить проблему остановки (задачу проверки, остановится ли, в конце концов, машина Тьюринга) тогда следует невозможность решить задачу замощения Вана Шаблон:SfnШаблон:Sfn.

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

Комбинация результата Бергера с наблюдением Вана показывает, что должен существовать конечный набор плиток Вана, замощающих плоскость, но лишь Шаблон:Не переведено 5. Этим свойством обладает мозаика Пенроуза и расположение атомов в квазикристалле. Хотя оригинальный набор Бергера содержал 20.426 плиток, он предположил, что меньшие наборы могут также существовать, включая подмножества его оригинального набора, и в неопубликованных тезисах его диссертации он сократил число плиток до 104. Позднее были найдены ещё меньшие наборы Шаблон:SfnШаблон:SfnШаблон:Sfn. Например, набор из 11 плиток и 4 цветов, приведённый выше, является непериодическим набором, и был открыт Эммануэлем Жанделем и Майклом Рао в 2015 году, используя полный перебор для доказательства того, что 10 плиток или 3 цветов недостаточно для апериодичности[1].

Обобщения

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

Приложения

Плитки Вана недавно стали популярным средством создания Шаблон:Не переведено 5 текстур, полей высот и других больших неповторяющихся двумерных наборов данных. Небольшое число заранее вычисленных или созданных вручную плиток могут быть собраны быстро и дёшево без очевидных повторений и периодичности. В этом случае обычные непериодичные мозаики показали бы свою структуру. Куда менее ограничивающие наборы, которые обеспечивают выбор по меньшей мере двух вариантов для любых двух цветов сторон, более приемлемы, поскольку замощаемость легко обеспечивается и каждая плитка может быть выбрана псевдослучайно Шаблон:SfnШаблон:SfnШаблон:SfnШаблон:Sfn. Плитки Вана используются также при проверке разрешимости теории клеточных автоматов Шаблон:Sfn.

В культуре

Короткий рассказ Грега Игана «Ковёр Вана», впоследствии расширенный до новеллы Шаблон:Не переведено 5, рассказывает о вселенной, заполненной организмами и мыслящими существами в виде плиток Вана, образованными узорами сложных молекулШаблон:Sfn.

См. также

Примечания

Шаблон:Примечания

Литература

Ссылки

Шаблон:Геометрические мозаики

Шаблон:Rq

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Шаблон:Citation. (Showed an aperiodic set of 11 tiles with 4 colors)}
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Плитки_Вана&oldid=10601348