Примеры неразрешимых задач: задача о замощении — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «== Постановка задачи == Пусть даны некоторые типы полимино, причем экземпляров каждого тип…»)
(нет различий)

Версия 01:21, 23 февраля 2011

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

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

Теорема:
Задача о замощении четверти плоскости полимино неразрешима.
Доказательство:
[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].

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

Poly Idea.jpg

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

Poly Simple.jpg

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


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

Poly Start.jpg     Poly Start Alph.jpg     Poly Start Add.jpg

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

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

Poly Alph.jpg

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

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

Poly Delta.jpg

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

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

Poly Delta2.jpg

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


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

Poly Halt.jpg

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


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

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

Если же МТ остановится, то и замостить четверть плоскости мы не сможем из-за того, что конечное полимино не имеет продолжения.


Значит задача о замощении полимино не разрешима.
[math]\triangleleft[/math]