17
правок
Изменения
Новая страница: «== Постановка задачи == Пусть даны некоторые типы полимино, причем экземпляров каждого тип…»
== Постановка задачи ==
Пусть даны некоторые типы полимино, причем экземпляров каждого типа дается бесконечно много.
Верно ли, что используя любое количество полимино можно полностью замостить без пропусков и выступов четверть плоскости? Поворачивать полимино не разрешено.
{{Теорема
|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]] [[Файл:Poly_Start_Alph.jpg]] [[Файл: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]]
Такое полимино имеет уникальное число выступов справа. Ни одно другое полимино из полученного набора не сможет к нему присоединиться, и процесс дальнейшего замощения будет невозможен.
Полученный алгоритм сведения получает на вход МТ и слово, а на выход выдает соответствующий им набор полимино.
Таким образом, четверть плоскости замостится тогда и только тогда, когда закодировання МТ не останавливается на данном входе. Иными словами есть бесконечное количество конфигураций, не переходящих в конечное состояние. Это значит, что мы сможем замощать плоскость ряд за рядом бесконечное количество раз, что в результате замостит плоскость.
Если же МТ остановится, то и замостить четверть плоскости мы не сможем из-за того, что конечное полимино не имеет продолжения.
Значит задача о замощении полимино не разрешима.
}}
Пусть даны некоторые типы полимино, причем экземпляров каждого типа дается бесконечно много.
Верно ли, что используя любое количество полимино можно полностью замостить без пропусков и выступов четверть плоскости? Поворачивать полимино не разрешено.
{{Теорема
|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]] [[Файл:Poly_Start_Alph.jpg]] [[Файл: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]]
Такое полимино имеет уникальное число выступов справа. Ни одно другое полимино из полученного набора не сможет к нему присоединиться, и процесс дальнейшего замощения будет невозможен.
Полученный алгоритм сведения получает на вход МТ и слово, а на выход выдает соответствующий им набор полимино.
Таким образом, четверть плоскости замостится тогда и только тогда, когда закодировання МТ не останавливается на данном входе. Иными словами есть бесконечное количество конфигураций, не переходящих в конечное состояние. Это значит, что мы сможем замощать плоскость ряд за рядом бесконечное количество раз, что в результате замостит плоскость.
Если же МТ остановится, то и замостить четверть плоскости мы не сможем из-за того, что конечное полимино не имеет продолжения.
Значит задача о замощении полимино не разрешима.
}}
