Изменения

'''Полимино''' ('''полиомино''', 'англ. ''polyomino''') - — плоская геометрическая фигура, состоящая из <tex>n</tex> одноклеточных квадратов, соединенных по сторонам.

'''Замощение плоскости''' ('англ. ''tiling''') - — представление плоскости в виде множества непересекающихся полимино.

Пусть дана плоскость <tex>S</tex> и набор полимино <tex>P</tex>, если <tex>\exists ~ f: N \times N \to P</tex>(говорящая по клетке, какому полимино она соответствует) тогда считается, что можно замостить плоскость <tex>S</tex> данным набором.

== Замощение четверти плоскости =={{ОпределениеШаблон:Задача

Для того, чтобы доказать неразрешимость задачи о замощении, для заданной машины Тьюринга <tex>M</tex> и слова <tex>w</tex> построим набор полимино, которым можно замостить четверть плоскости, если МТ не остановится на заданном слове. Если же МТ останавливается, то четверть плоскости полученным набором замостить невозможно.  Будем эмулировать процесс выполнения МТ на входе <tex>w \in \Sigma^*</tex> путем построения вертикальных рядов, каждый из которых эквивалентен конфигурации МТ на определенном этапе выполнения.Первый ряд заполняется эквивалентен начальной конфигурациейконфигурации МТ, а каждый следующий ряд соответствует следующей конфигурации. Говоря простым языком, каждый ряд представляет из себя "снимок" состояния машины на соответствующем этапе выполнения.

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

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

Теперь построим полимино для функции перехода <tex>\delta (aq, 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>:

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

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

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

== Ссылки Замощение половины плоскости == {{Теорема|statement=Задача о замощении половины плоскости полимино неразрешима.|proof=Будем действовать также как и предыдущем доказательстве, только одновременно будем строить еще и зеркально отраженные полимино так, чтобы их нельзя было никак соединить с изначальными.  Например, можно сделать новое количество выступов/впадин <tex>k' = \mathrm{cur_k} + \mathrm{max_k}</tex>, где <tex>\mathrm{cur_k}</tex> {{---}} количество выступов/впадин у полимино, от которого образовалось текущее, <tex>\mathrm{max_k}</tex> {{---}} максимальное число выступов/впадин у полимино в первой четверти. [[Файл:Polyomino_bad_case.png]] Сделаем так для всех полимино кроме первого столбца. Для него добавим специальное соединение, к которому подходит только зеркально отраженное полимино. [[Файл:Polyomino_init_2.png]] }} == Замощение целой плоскости == {{Теорема|statement=Задача о замощении целой плоскости полимино неразрешима.|proof=Аналогично замощению половины плоскости.}} == См. также ==* [[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ| Задача о выводе в полусистеме Туэ]]* [[Примеры неразрешимых задач: проблема соответствий Поста | Проблема соответствий Поста]]* [[M-сводимость | M-сводимость]]* [[Неразрешимость исчисления предикатов первого порядка]] == Источники информации ==