Примеры неразрешимых задач: задача о замощении
| Определение: |
| Полимино (полиомино, polyomino) - плоская геометрическая фигура, состоящая из одноклеточных квадратов, соединенных по сторонам. |
Постановка задачи
Пусть даны некоторые типы полимино, причем экземпляров каждого типа дается бесконечно много. Верно ли, что используя любое количество полимино можно полностью замостить без пропусков и выступов четверть плоскости? Поворачивать полимино не разрешено.
| Теорема: |
Задача о замощении четверти плоскости полимино неразрешима. |
| Доказательство: |
|
Сведём неразрешимую Halt к данной задаче. Пусть дана машина Тьюринга и слово . Требуется определить, остановится ли данная МТ на входе . Будем эмулировать процесс выполнения МТ путем построения вертикальных рядов, каждый из которых эквивалентен конфигурации МТ на определенном этапе выполнения. Первый ряд заполняется начальной конфигурацией, а каждый следующий ряд соответствует следующей конфигурации.
Теперь на основе заданной МТ будем строить набор полимино, которые будут иметь следующий вид:
На каждой стороне такого полимино находится определенное число выступов/впадин. Каждому символу из алфавита, состоянию и паре из состояния и символа сопоставим некоторое уникальное число (можно ограничить ) – это и будет количество выступов/впадин находящихся на одной стороне полимино.
где – уникальные числа для каждых соседних двух полимино из начальной конфигурации. Первое полимино характеризует начальное состояние, последующие за ним кодируют входное слово, и завершающее полимино требуется для корректного замощения оставшейся части ряда. Далее строим полимино для всех элементов алфавита :
В нем количество впадин слева равно количеству выступов справа. Такой тип полимино передает содержимое ленты МТ следующему ряду. Теперь построим полимино для функции перехода , где :
На рисунке изображены (сверху вниз) полимино соответствующие значениям . Вместе со следующим типом они эмулируют перемещение головки МТ. Далее построим следующий тип полимино:
Эти полимино получают на вход символ алфавита от предыдущего ряда и состояние от соседнего полимино, а затем передает следующему ряду пару из состояния и символа.
Такое полимино имеет уникальное число выступов справа. Ни одно другое полимино из полученного набора не сможет к нему присоединиться, и процесс дальнейшего замощения будет невозможен.
Таким образом, четверть плоскости замостится тогда и только тогда, когда закодировання МТ не останавливается на данном входе. Иными словами есть бесконечное количество конфигураций, не переходящих в конечное состояние. Это значит, что мы сможем замощать плоскость ряд за рядом бесконечное количество раз, что в результате замостит плоскость. Если же МТ остановится, то и замостить четверть плоскости мы не сможем из-за того, что конечное полимино не имеет продолжения.
|
