Ван Хао и Бергер: задача домино неразрешима

Плитки, придуманные ради логики

Ван Хао (1921–1995) — китайско-американский логик, ученик Куайна, работавший в Гарварде, в Bell Labs и в IBM. Он занимался не орнаментом, а классической задачей, поставленной ещё ГильбертомДавид Гильбертнемецкий математик · 1862–1943Человек, сделавший Гёттинген столицей математики и задавший ей повестку на весь XX век — двадцатью тремя проблемами и одной программой, которую сам же и не смог спасти.: проблемой разрешения для логики предикатов.

Общая проблема закрыта в 1936 году: алгоритма нет. Но остаётся вопрос про отдельные классы формул — те, у которых кванторы стоят в определённом порядке. Для многих классов алгоритм есть. Ван Хао разбирался с классом $\forall\exists\forall$ и в 1961 году придумал, к чему его свести.

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

Задача домино: дан конечный набор таких плиток; можно ли замостить ими всю плоскость?

Ван Хао показал, что вопрос о выполнимости формул класса $\forall\exists\forall$ сводится к задаче домино. Значит, если бы задача домино решалась алгоритмом, решался бы и кусок логики.

Гипотеза, которая всё бы упростила

Ван Хао высказал предположение, звучащее совершенно естественно:

Гипотеза Ван Хао (1961). Если набор плиток замощает плоскость, то он замощает её и периодически.

Иначе говоря: любой набор либо не годится вовсе, либо годится «скучным» образом — с повторяющимся узором.

Из гипотезы немедленно следовал бы алгоритм. Рассуждение стоит проследить, оно короткое и красивое.

Ключевое слово здесь — «если гипотеза верна».

Аспирант

Диссертацию у Ван Хао писал Роберт Бергер. В 1964 году он защитил её в Гарварде, а в 1966-м вышел мемуар Американского математического общества под названием «Неразрешимость задачи домино».

Бергер доказал ровно противоположное ожидаемому.

Теорема (Бергер, 1966). Задача домино алгоритмически неразрешима.

А отсюда, по тому же рассуждению, прочитанному задом наперёд, следует:

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

Такие наборы называют апериодическими. Первый из них Бергер построил явно; в диссертации он состоял из 20 426 плиток. Позднее в самом мемуаре он сократил его до 104.

Почему это переворачивает сюжет

Остановимся, потому что это главный поворот всей нити.

До 1966 года апериодические замощения никого не интересовали и никем не искались. Их не было в списке задач; никто не подозревал, что они существуют. Кеплеровский узор Aa считался незавершённым чертежом, а не открытием.

И вот их существование выводится логически, из теоремы о неразрешимости, ещё до того, как хоть один из них построен. Логика говорит: раз алгоритма нет, апериодические наборы обязаны существовать — иначе алгоритм был бы. Бергеру осталось предъявить.

Это меняет ответ на вопрос «математика ли это». Апериодический паркет — не головоломка, придуманная человеком с ножницами. Это объект, существование которого доказано от противного, из теории вычислимости, в одном ряду с проблемой тождества слов и десятой проблемой Гильберта.

Сокращение

Дальше началось то, что математики любят: гонка за уменьшением.

104 плитки Бергера сократил до шести Рафаэль Робинсон в 1971 году, причём его набор устроен прозрачно: плитки заставляют выкладывать вложенные друг в друга квадраты всё большего размера, и эта иерархия и не даёт узору замкнуться. Робинсоновская конструкция стала образцом, по которому строят почти все последующие.

⚠ Робинсонов на нашей карте теперь трое, и путать их нельзя. Абрахам Робинсон — нестандартный анализ. Джулия Робинсон — десятая проблема Гильберта. Рафаэль Робинсон — эти шесть плиток; он был мужем Джулии.

Потом счёт пошёл на единицы: 13 плиток у Кулика, 14 у Кари (оба — 1996). В 2015 году Жандель и Рао показали перебором на ЭВМ, что меньше одиннадцати плиток не бывает, и предъявили набор из одиннадцати. Задача закрыта окончательно.

Но это всё про квадратные плитки Ван Хао с цветными сторонами. Если разрешить плиткам иметь любую форму, то уже через три года после Робинсона счёт дойдёт до двух.