338
правок
Изменения
м
→Постановка задачи
{{Теорема
|statement=
Задача о замощении четверти плоскости полимино неразрешима.<br><tex>Tiling_4 \notin R</tex>
|proof=
[[m-сводимость|Сведём неразрешимую 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>.
Таким образом, четверть плоскости замостится тогда и только тогда, когда закодировання МТ не останавливается на данном входе. Иными словами есть бесконечное количество конфигураций, не переходящих в конечное состояние. Это значит, что мы сможем замощать плоскость ряд за рядом бесконечное количество раз, что в результате замостит плоскость.
Если же МТ остановится, то и замостить четверть плоскости мы не сможем из-за того, что конечное полимино не имеет продолжения. Значит задача о замощении полимино не разрешима.
}}
* [http://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%BB%D0%B8%D0%BC%D0%B8%D0%BD%D0%BE Полимино — Википедия]
