Примеры неразрешимых задач: задача о замощении

Определение:

Полимино (полиомино, polyomino) - плоская геометрическая фигура, состоящая из [math]n[/math] одноклеточных квадратов, соединенных по сторонам.

Постановка задачи

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

Теорема:

Задача о замощении четверти плоскости полимино неразрешима.

Доказательство:

[math]\triangleright[/math]

Сведём неразрешимую Halt к данной задаче. Пусть дана машина Тьюринга [math]M =\langle \Sigma, Q, \Pi, B \in \Pi, s,\delta: Q \times \Pi \rightarrow Q \times \Pi \times \{ \leftarrow, \downarrow, \rightarrow \} \rangle[/math] и слово [math]w \in \Sigma^*[/math]. Требуется определить, остановится ли данная МТ на входе [math]w[/math]. Будем эмулировать процесс выполнения МТ путем построения вертикальных рядов, каждый из которых эквивалентен конфигурации МТ на определенном этапе выполнения. Первый ряд заполняется начальной конфигурацией, а каждый следующий ряд соответствует следующей конфигурации. Теперь на основе заданной МТ будем строить набор полимино, которые будут иметь следующий вид: На каждой стороне такого полимино находится определенное число выступов/впадин. Каждому символу из алфавита, состоянию и паре из состояния и символа сопоставим некоторое уникальное число (можно ограничить [math]k \le |\Pi| + |Q| + |\Pi \times Q| + 1[/math]) – это и будет количество выступов/впадин находящихся на одной стороне полимино. Сначала построим набор полимино, который задаёт начальную конфигурацию:         где [math]*[/math] – уникальные числа для каждых соседних двух полимино из начальной конфигурации. Первое полимино характеризует начальное состояние, последующие за ним кодируют входное слово, и завершающее полимино требуется для корректного замощения оставшейся части ряда. Далее строим полимино для всех элементов алфавита [math]c \in \Pi[/math]: В нем количество впадин слева равно количеству выступов справа. Такой тип полимино передает содержимое ленты МТ следующему ряду. Теперь построим полимино для функции перехода [math]\delta (a, c) = \langle p, d, D \rangle [/math], где [math]q \in Q, p \in Q, c \in \Pi, d \in \Pi, D\in \{\leftarrow, \downarrow, \rightarrow \}[/math]: На рисунке изображены (сверху вниз) полимино соответствующие значениям [math]D = \{\leftarrow, \downarrow, \rightarrow \}[/math]. Вместе со следующим типом они эмулируют перемещение головки МТ. Далее построим следующий тип полимино: Эти полимино получают на вход символ алфавита [math]c[/math] от предыдущего ряда и состояние [math]p[/math] от соседнего полимино, а затем передает следующему ряду пару из состояния и символа. Построим последний тип полимино, характеризующие состояния [math]\#_Y[/math] и [math]\#_N[/math]: Такое полимино имеет уникальное число выступов справа. Ни одно другое полимино из полученного набора не сможет к нему присоединиться, и процесс дальнейшего замощения будет невозможен. Полученный алгоритм сведения получает на вход МТ и слово, а на выход выдает соответствующий им набор полимино. Таким образом, четверть плоскости замостится тогда и только тогда, когда закодировання МТ не останавливается на данном входе. Иными словами есть бесконечное количество конфигураций, не переходящих в конечное состояние. Это значит, что мы сможем замощать плоскость ряд за рядом бесконечное количество раз, что в результате замостит плоскость. Если же МТ остановится, то и замостить четверть плоскости мы не сможем из-за того, что конечное полимино не имеет продолжения. Значит задача о замощении полимино не разрешима.

[math]\triangleleft[/math]

• Полимино — Википедия