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