Изменения
→Замощение половины плоскости
|{{Определение
|definition=
'''Полимино''' (англ. ''polyomino'') - — плоская геометрическая фигура, состоящая из <tex>n</tex> одноклеточных квадратов, соединенных по сторонам.
}}
|[[file:Polyomino_example.png|300px|right]]
{{Определение
|definition=
'''Замощение плоскости''' (англ. ''tiling'') - — представление плоскости в виде множества непересекающихся полимино.
}}
Пусть дана плоскость <tex>S</tex> и набор полимино <tex>P</tex>, если <tex>\exists ~ f: N \times N \to P</tex> (говорящая по клетке, какому полимино она соответствует) тогда считается, что можно замостить плоскость <tex>S</tex> данным набором.
== Замощение четверти плоскости ==
{{Шаблон:Задача
|definition=
Пусть даны некоторые типы полимино, причем экземпляров каждого типа дается бесконечно много.
Верно ли, что используя любое количество полимино можно полностью замостить без пропусков и выступов четверть плоскости? Поворачивать полимино не разрешено.
}}
{{Теорема
Пусть дана [[Машина Тьюринга|машина Тьюринга]] <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>.
Для того, чтобы доказать неразрешимость задачи о замощении, для заданной машины Тьюринга <tex>M</tex> и слова <tex>w</tex> построим набор полимино, которым можно замостить четверть плоскости, если МТ не остановится на заданном слове. Если же МТ останавливается, то четверть плоскости полученным набором замостить невозможно. Будем эмулировать процесс выполнения МТ на входе <tex>w \in \Sigma^*</tex> путем построения вертикальных рядов, каждый из которых эквивалентен конфигурации МТ на определенном этапе выполнения.Первый ряд заполняется эквивалентен начальной конфигурациейконфигурации МТ, а каждый следующий ряд соответствует следующей конфигурации. Говоря простым языком, каждый ряд представляет из себя "снимок" состояния машины на соответствующем этапе выполнения.
[[Файл:Polyomino_init.png]]
На рисунке сверху изображены два вертикальных ряда полимино. Первый ряд соответствует МТ и слову <tex>w</tex>. Первое полимино соответствует паре из первого символа и начального состояния, все остальные — символам из <tex>w</tex>. Во втором ряду второе полимино соответствует паре из символа <tex>w[2]</tex> и состояния <tex>q</tex>. То есть МТ сделала переход <tex>\delta (s, w[1]) = \langle q, w[1], \rightarrow \rangle</tex>.
Теперь на основе заданной МТ будем строить набор полимино, которые будут иметь следующий вид:
На каждой стороне такого полимино находится определенное число выступов/впадин.
Каждому символу из алфавита, состоянию и паре из состояния и символа сопоставим некоторое уникальное число (можно ограничить <tex>k \le leqslant |\Pi| + |Q| + |\Pi \times Q| + 1</tex>) – это и будет количество выступов/впадин , находящихся на одной стороне полимино.
[[Файл:Polyomino_start.png]]
где <tex>*i</tex> – уникальные числа уникальное число для каждых соседних двух каждой смежной пары полимино из начальной конфигурации. Первое полимино характеризует начальное состояние, последующие за ним кодируют входное слово, и завершающее полимино требуется для корректного замощения оставшейся части ряда.
Далее строим полимино для всех элементов алфавита <tex>c \in \Pi</tex>:
Эти полимино получают на вход символ алфавита <tex>c</tex> от предыдущего ряда и состояние <tex>p</tex> от соседнего полимино, а затем передает следующему ряду пару из состояния и символа.
Построим последний тип полимино, характеризующие характеризующих состояния <tex>\#_Y</tex> и <tex>\#_N</tex>:
[[Файл:Polyomino_halt.png]]
Полученный алгоритм сведения получает на вход МТ и слово, а на выход выдает соответствующий им набор полимино.
Таким образом, четверть плоскости можно замостить тогда и только тогда, когда закодированная МТ не останавливается на данном входе. Иными словами , есть бесконечное количество конфигураций, не переходящих в конечное состояние. Это значит, что мы сможем замощать плоскость ряд за рядом бесконечное количество раз, что в результате замостит плоскость.
Если же МТ остановится, то и замостить четверть плоскости мы не сможем из-за того, что конечное полимино не имеет продолжения. Значит задача о замощении полимино не разрешима.
Будем действовать также как и предыдущем доказательстве, только одновременно будем строить еще и зеркально отраженные полимино так, чтобы их нельзя было никак соединить с изначальными.
Например, можно сделать новое количество выступов/впадин <tex>k' = \mathrm{cur_k } + \mathrm{max_k}</tex>, где <tex>\mathrm{cur_k}</tex> {{---}} количество выступов/впадин у полимино, от которого образовалось текущее, <tex>\mathrm{max_k}</tex> {{---}} максимальное число выступов/впадин у полимино в первой четверти.
[[Файл:Polyomino_bad_case.png]]
