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

Материал из Викиконспекты
Перейти к: навигация, поиск


Определения

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


Определение:
Замощение плоскости (tiling) - представление плоскости в виде множества непересекающихся полимино.

Пусть дана плоскость [math]S[/math] и набор полимино [math]P[/math], если [math]\exists ~ f: N \times N \to P[/math] (говорящая по клетке, какому полимино она соответствует) тогда считается, что можно замостить плоскость [math]S[/math] данным набором.


Определение:
[math]Tiling_n = \{(P_1, P_2,..., P_k) ~ | ~ \frac{1}{n}[/math] плоскости можно замостить[math]\}[/math].

Tiling example.png

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

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

Теорема:
Задача о замощении четверти плоскости полимино неразрешима.
Доказательство:
[math]\triangleright[/math]

Сведём задачу останова к данной задаче. Пусть дана машина Тьюринга [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].

Будем эмулировать процесс выполнения МТ путем построения вертикальных рядов, каждый из которых эквивалентен конфигурации МТ на определенном этапе выполнения. Первый ряд заполняется начальной конфигурацией, а каждый следующий ряд соответствует следующей конфигурации.

Polyomino init.png

Теперь на основе заданной МТ будем строить набор полимино, которые будут иметь следующий вид:

Polyomino gen.png

На каждой стороне такого полимино находится определенное число выступов/впадин. Каждому символу из алфавита, состоянию и паре из состояния и символа сопоставим некоторое уникальное число (можно ограничить [math]k \le |\Pi| + |Q| + |\Pi \times Q| + 1[/math]) – это и будет количество выступов/впадин находящихся на одной стороне полимино.


Сначала построим набор полимино, который задаёт начальную конфигурацию:

Polyomino start.png

где [math]*[/math] – уникальные числа для каждых соседних двух полимино из начальной конфигурации. Первое полимино характеризует начальное состояние, последующие за ним кодируют входное слово, и завершающее полимино требуется для корректного замощения оставшейся части ряда.

Далее строим полимино для всех элементов алфавита [math]c \in \Pi[/math]:

Polyomino alph.png

В нем количество впадин слева равно количеству выступов справа. Такой тип полимино передает содержимое ленты МТ следующему ряду.

Теперь построим полимино для функции перехода [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]:

Polyomino delta.png

На рисунке изображены (сверху вниз) полимино соответствующие значениям [math]D = \{\leftarrow, \downarrow, \rightarrow \}[/math]. Вместе со следующим типом они эмулируют перемещение головки МТ.

Далее построим следующий тип полимино:

Polyomino delta2.png

Эти полимино получают на вход символ алфавита [math]c[/math] от предыдущего ряда и состояние [math]p[/math] от соседнего полимино, а затем передает следующему ряду пару из состояния и символа.


Построим последний тип полимино, характеризующие состояния [math]\#_Y[/math] и [math]\#_N[/math]:

Polyomino halt.png

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


Полученный алгоритм сведения получает на вход МТ и слово, а на выход выдает соответствующий им набор полимино.

Таким образом, четверть плоскости можно замостить тогда и только тогда, когда закодированная МТ не останавливается на данном входе. Иными словами есть бесконечное количество конфигураций, не переходящих в конечное состояние. Это значит, что мы сможем замощать плоскость ряд за рядом бесконечное количество раз, что в результате замостит плоскость.

Если же МТ остановится, то и замостить четверть плоскости мы не сможем из-за того, что конечное полимино не имеет продолжения. Значит задача о замощении полимино не разрешима.
[math]\triangleleft[/math]

Замощение половины плоскости

Теорема:
Задача о замощении половины плоскости полимино неразрешима.
Доказательство:
[math]\triangleright[/math]

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

Например, можно покрасить стороны новых полимино в другой цвет и ввести правило, по которому можно соединять полимино, только если цвета их общей стороны совпадают.

Polyomino bad case.png

Сделаем так для всех полимино кроме первого ряда. Для него добавим специальное соединение, к которому подходит только зеркально отраженное полимино.

Polyomino init 2.png
[math]\triangleleft[/math]

Замощение целой плоскости

Теорема:
Задача о замощении половины плоскости полимино неразрешима.
Доказательство:
[math]\triangleright[/math]
Аналогично замощению половины плоскости.
[math]\triangleleft[/math]

Ссылки

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Примеры_неразрешимых_задач:_задача_о_замощении&oldid=35685»