Апериодические наборы плиток Вана или история возникновения апериодических замощений

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

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

> Проблема домино заключается в поиске такого алгоритма, который способен гарантированно сказать, покрывает или не покрывает заданный набор домино всю плоскость.

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

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

Сначала алгоритм проверял стыкуемость одной плитки, потом квадрата 2?2, 3?3 и так далее. Если в какой-то момент квадрат построить не удавалось, из этого следовало, что набор плиток не может замостить плоскость. Если же плитки покрывают всю плоскость, значит алгоритм обязательно найдет квадрат, даже состоящий из миллиона или миллиарда плиток, который сформирует периодическое покрытие. Третьего, по гипотезе Вана, дано не было.

> Гипотеза Вана утверждала, что если какими-то одинаковыми фигурами можно замостить плоскость бесконечно, то из них обязательно можно составить хотя бы один повторяющийся узор.

Но Ван ошибался.

В 1966 году его аспирант Роберт Бергер опроверг гипотезу учителя. Он доказал, что существуют конечные наборы плиток Вана, которые не допускают периодических замощений, но способны замостить плоскость.

Бергер показал, что процесс выкладывания плиток на плоскость эквивалентен работе машины Тьюринга, где каждый ряд плиток кодирует шаг вычислений. (Как именно — рассказывать интересно, но долго — об этом будет другая заметка.)

Поскольку узор кодирует программу, то проблема обнаружения периодического фрагмента сводится к проблеме доказательства остановки программы. То есть вопрос о том, можно ли набором плиток замостить плоскость, эквивалентен вопросу о том, остановится ли данная программа или нет.

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

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

> Апериодический набор плиток генерирует только хаотические замощения плоскости.

Бергер построил первый апериодический набор, который был огромным и состоял из 20 426 плиток Вана. Это была сенсация. До него апериодические наборы не были известны.

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

1964 год — Роберт Бергер: 104 плитки.

Бергер сократил свой чудовищный набор из более чем 20 тысяч плиток до 104, показав, что даже такая компактная конструкция способна кодировать универсальные вычисления.

1966 год — Питер Лойхли: 40 плиток, 16 цветов.

Швейцарский математик Питер Лойхли использовал абстрактную алгебру и теорию групп, что позволило ему резко уменьшить количество плиток до 40 ценой увеличения числа цветов на сторонах.

1967 — Рафаэль Робинсон: 104 и 52 плитки, 8 цветов.

Робинсон переосмыслил подход Бергера и предложил знаменитые "плитки Робинсона", которые создают иерархическую структуру квадратов возрастающего размера. Это позволило ему сократить набор до 52 плиток, использующих всего 8 цветов.

1968 — Дональд Кнут: 92 плитки (сводятся к 86), 26 цветов

Знаменитый автор "Искусства программирования" не мог пройти мимо задачи о плитках. Кнут предложил набор из 92 плиток, который при оптимизации уменьшался до 86. Любопытно, что Кнут не пытался побить рекорд минимальности — его интересовала структура набора и возможность его декомпозиции.

1971 — Робинсон: 56 плиток (12 цветов) и 35 плиток.

Робинсон продолжил работу над собственным подходом и предложил сразу две версии: набор из 56 плиток с 12 цветами и более компактный вариант из 35 плиток. Это был первый шаг к разделению двух параметров — числа плиток и числа цветов.

1973 — Роджер Пенроуз: 34 плитки.

Пенроуз предложил принципиально иной подход. В письме Робинсону он показал, как его знаменитые мозаики из "воздушных змеев и дротиков" можно преобразовать в 34 плитки Вана.

1973 — Робинсон: 32 плитки, 16 цветов.

В том же году Робинсон предложил еще одну версию своего набора — 32 плитки, 16 цветов. Долгое время этот набор оставался рекордным среди классических подходов.

1977 — Робинсон: 24 плитки, 24 цвета.

Робинсон снова вернулся к задаче и сократил число плиток до 24, но ценой увеличения числа цветов до 24. Это наглядная иллюстрация компромисса: чем меньше плиток, тем больше цветов на сторонах, и наоборот.

1978 — Роберт Амман: 16 плиток, 6 цветов.

Роберт Амман — удивительная фигура в этой истории. Он был математиком-любителем и работал почтовым служащим. Тем не менее его интуиция в области мозаик была феноменальной. Амман предложил набор из 16 плиток с 6 цветами — рекорд, который продержался почти два десятилетия

1987 — Бранко Грюнбаум и Джеффри Шепард: 24 плитки, 9 цветов.

Грюнбаум и Шепард систематизировали теорию замощений и представили собственный набор, оказавший влияние на теорию вычислений.

1995 — Марджори Сенешаль: 64 плитки.

Марджори Сенешаль — математик и историк науки, биографа Аммана. Она предложила набор из **64 плиток**, специально предназначенный для педагогических целей: его структура прозрачна для объяснения апериодичности студентам.

1996 — Юрки Кари: 14 плиток, 6 цветов.

Финский математик Юрки Кари использовал теорию конечных автоматов и пришел к набору из 14 плиток с 6 цветами. Его подход основан на моделировании умножения на константу в системе счисления с иррациональным основанием — красивое соединение теории чисел и теории автоматов.

1996 — Карел Чулик: 13 плиток, 5 цветов.

Чулик, работая в том же направлении, что и Кари, добился дальнейшего уменьшения набора до 13 плиток с 5 цветами. Его метод использует клеточные автоматы и графы де Брейна.

1999 — Кари и Папасоглу: 696 плиток (детерминированный набор).

Кари и Папасоглу построили детерминированный апериодический набор из 696 плиток. Детерминированный означает, что для любой плитки сосед справа и сосед сверху однозначно определяются, — то есть узор вырастает из одной плитки принудительно. Это не рекорд минимальности, но важное концептуальное достижение.

2008 — Николя Оллинже: 104 плитки.

Оллинже предложил новый метод сведения — через моделирование биективных машин Тьюринга — и получил набор из 104 плиток. Любопытно, что это число совпадает с исходным результатом Бергера 1964 года, но на совершенно иной теоретической основе.

2018 — Себастьян Лаббе: 19 плиток, 16 цветов (самоподобный набор).

Лаббе построил самоподобный набор из 19 плиток с 16 цветами. Самоподобие означает, что любое замощение этого набора содержит уменьшенную копию самого себя, — то есть апериодичность здесь опирается на структуру, повторяющуюся на разных масштабах, как фрактал.

2021 — Лаббе и Лепшова: 16 плиток, 8 цветов (минимальный самоподобный набор).

Лаббе в сотрудничестве с Лепшовой улучшил собственный результат до 16 плиток с 8 цветами. Доказано, что этот набор минимален в классе самоподобных — меньше плиток или цветов в самоподобной конструкции получить нельзя.

2021 — Эммануэль Жандел и Майкл Рао: 11 плиток, 5 или 4 цвета (наименьший возможный набор).

Рекорд. Жандел и Рао построили апериодический набор из всего 11 плиток с 4 цветами (для специальной модификации — с 5 цветами). Они доказали, что меньшего числа плиток Вана для апериодического набора не существует: достаточно проанализировать все возможные наборы из 10 и менее плиток, и все они допускают периодические замощения. Это окончательная нижняя граница после почти 60 лет поиска.

На протяжении всей истории охоты на апериодические наборы наблюдается компромисс между числом плиток и числом цветов: уменьшая одно, исследователи обычно увеличивали другое. Жандел и Рао смогли разорвать эту закономерность — их набор минимален по обоим параметрам.

Несколько важнейших прорывов были сделаны людьми без математического образования — в первую очередь Робертом Амманом. Это напоминает историю индийского математика Рамануджана и показывает, что визуальная геометрия мозаик доступна интуитивному пониманию в большей степени, чем многие другие области математики.

Практически все апериодические наборы — это, по сути, упакованные вычислительные устройства. Плитки Вана — это аппаратная реализация универсальных вычислений в геометрическом виде, что делает их важным объектом не только для геометрии, но и для теории вычислений и оснований математики.

На рисунке показан апериодический узор, построенный из наименьшего возможного набора: 11 плиток и 5 цветов.

О практической пользе плиток Вана, их визуальной эстетике и о построении машины Тьюринга поговорим в другой раз.

#ёжик_пишет #алгебра_и_геометрия

Телеграм: t.me/ainewsline

Источник: vk.com

Комментарии: