74
правки
Изменения
Сдвиг картинок
Проблема останова игры «Жизнь» неразрешима.
|proof =
[[Файл:Platform.png|200px|thumb|right| Платформа с рычагом]]
[[Файл:Cannon.png|200px|thumb|right| Пушка]]
[[Файл:Counter.png|200px|thumb|right| Устройство-счетчик]]
[[Файл:Branch.png|200px|thumb|right| Устройство ветвления]]
Заметим, что если существует МТ, которая по начальной конфигурации уровня в Braid может определить, завершается ли она, то та же МТ может определить, останавливается ли любая МТ, что противоречит неразрешимости проблемы останова для МТ. Следовательно, необходимо описать процесс построения МТ в игре Braid. Построим [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ|счетчиковую машину]], эквивалентную МТ. Подаваемая на вход программа будет содержать следующие операции:
* прибавить: увеличивает на 1 значение выбранного счетчика.
* вычесть и перейти: сравнивает с нулем значение выбранного счетчика. Если оно больше нуля, из него вычитается единица; если равно нулю, происходит переход на указанную строку в программе.
* остановиться.
В нашей машине счетчиками будут являться группы монстров. "Программа" будет выполняться Тимом: чтобы пройти уровень, ему нужно нажать на каждый рычаг на своем пути. Каждый рычаг выполняет либо операцию "добавить", либо "вычесть и перейти". Чтобы допустить переходы (''goto''), некоторые участки пути могут вести к более ранним местам на этом пути.
