Просмотр исходного текста страницы Примеры неразрешимых задач: задача о замощении

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

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

{{Теорема
|statement=
Задача о замощении четверти плоскости полимино неразрешима.
|proof=



Сведём неразрешимую Halt к данной задаче. 
Пусть дана МТ <tex>M =\langle \Sigma, Q, \Pi, B  \in \Pi, s,\delta: Q \times \Pi \rightarrow Q \times \Pi \times \{ \leftarrow, \downarrow, \rightarrow \} \rangle</tex> и слово <tex>w \in \Sigma^*</tex>. Требуется определить, остановится ли данная МТ на входе <tex>w</tex>.

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

[[Файл:Poly_Idea.jpg]]

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

[[Файл:Poly_Simple.jpg]]

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


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

[[Файл:Poly_Start.jpg]] &nbsp;&nbsp;&nbsp;   [[Файл:Poly_Start_Alph.jpg]]  &nbsp;&nbsp;&nbsp;  [[Файл:Poly_Start_Add.jpg]]

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

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

[[Файл:Poly_Alph.jpg]]

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

Теперь построим полимино для функции перехода <tex>\delta (a, c) = \langle p, d, D \rangle </tex>, где <tex>q \in Q, p \in Q, c \in \Pi, d \in \Pi, D\in \{\leftarrow, \downarrow, \rightarrow \}</tex>:

[[Файл:Poly_Delta.jpg]]

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

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

[[Файл:Poly_Delta2.jpg]]

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


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

[[Файл:Poly_Halt.jpg]]

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


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

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

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


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