Плитки Вана (или домино Вана), впервые предложенные математиком, логиком и философом Хао Ваном в 1961, — это класс формальных систем. Они моделируются визуально с помощью квадратных плиток с раскрашиванием каждой стороны. Определяется набор таких плиток (например, как на иллюстрации), затем копии этих плиток прикладываются друг к другу с условием согласования цветов сторон, но без вращения или симметрического отражения плиток.
Основной вопрос о наборе плиток Вана — могут ли они замостить плоскость или нет, то есть может ли плоскость быть заполнена таким способом. Следующий вопрос, может ли она быть заполнена в виде периодического узора.
В 1961-м году Ван высказал гипотезу, что если конечное число плиток Вана может замостить плоскость, то существует периодическое замощение, то есть мозаика, инвариантная относительно параллельного переноса на вектора в двумерной решётке наподобие обоев. Он также заметил, что эта гипотеза имеет следствием существование алгоритма, определяющего, может ли данный конечный набор плиток Вана замостить плоскость[1][2]. Идея ограничения соединения смежных плиток возникла в игре домино, так что плитки Вана известны также под названием домино Вана [3], а алгоритмическая задача определения, могут ли плитки замостить плоскость, получила известность как задача домино [4].
Задача домино имеет дело с классом всех наборов домино. Задача состоит в определении для каждого набора домино, возможно или нет замощение. Мы говорим, что Задача Домино разрешима или неразрешима, в зависимости от того, существует или нет алгоритм, который по заданному набору произвольного набора домино определяет, разрешима или нет задача замощения для этого набора.
Другими словами, задача домино спрашивает, существует ли эффективный метод, правильно решающий задачу для заданных наборов домино.
В 1966 Бергер решил задачу домино, опровергнув гипотезу Вана. Он доказал, что не может существовать алгоритма, показав, как преобразовать любую машину Тьюринга в набор плиток Вана, так что плитки замощают плоскость в том и только в том случае, если машина Тьюринга не останавливается. Из невозможности решить проблему остановки (задачу проверки, остановится ли, в конце концов, машина Тьюринга) тогда следует невозможность решить задачу замощения Вана [4][4].