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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Замощение половины плоскости)
м (Замощение половины плоскости)
Строка 87: Строка 87:
 
Будем действовать также как и предыдущем доказательстве, только одновременно будем строить еще и зеркально отраженные полимино так, чтобы их нельзя было никак соединить с изначальными.  
 
Будем действовать также как и предыдущем доказательстве, только одновременно будем строить еще и зеркально отраженные полимино так, чтобы их нельзя было никак соединить с изначальными.  
  
Например, можно сделать новое количество выступов/впадин <tex>k</tex> такое, что ни один полимино из первой четверти не сможет соединиться с отраженным .
+
Например, можно сделать новое количество выступов/впадин такое, что ни один полимино из первой четверти не сможет соединиться с отраженным.
  
 
[[Файл:Polyomino_bad_case.png]]
 
[[Файл:Polyomino_bad_case.png]]

Версия 13:01, 19 января 2014


Определения

Определение:
Полимино (полиомино, 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]\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]

Ссылки