338
правок
Изменения
Нет описания правки
'''Полимино''' ('''полиомино''', '''polyomino''') - плоская геометрическая фигура, состоящая из <tex>n</tex> одноклеточных квадратов, соединенных по сторонам.
}}
===Пример===
[[file:Polyomino_example.png|300px]]
{{Определение
|definition=
'''Замощение плоскости''' ('''tiling''') - представление плоскости в виде множества полимино.
}}
{{Определение
|definition=
<tex>Tiling_n = \{(P_1, P_2,..., P_k) ~ | ~ \frac{1}{n}</tex> плоскости можно замостить<tex>\}</tex>.
}}
===Пример===
[[file:Tiling_example.png|300px]]
== Постановка задачи ==
Задача о замощении четверти плоскости полимино неразрешима.
|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>.
