Изменения
Переименовал устройства на правильный оригинал
==Неразрешимость==
Опишем проблему останова в игре Braid следующим образом. Пусть на вход подается уровень, содержащий вышеперечисленные игровые объекты. Требуется определить, возможно ли пройти этот уровень, то есть взять в определенной локации на уровне часть паззла и дойти до выхода с уровня. При этом мы считаем, что игрок двигается оптимально: из входа в очередную комнату к выходу из нее, а если встречает монстра, то прыгает на него и таким образом не может погибнуть.
{{Теорема
В нашей машине счетчиками будут являться группы монстров. ''Программа'' будет выполняться Тимом: чтобы пройти уровень, ему нужно нажать на каждый рычаг на своем пути. Каждый рычаг выполняет либо операцию ''добавить'', либо ''вычесть и перейти''. Чтобы допустить переходы (''goto''), некоторые участки пути могут вести к более ранним местам на этом пути.
Для это нам понадобится соорудить из простых игровых объектов служащие нашим целям '''устройства''' (англ. ''devicesgadgets'').
===Устройства===
Заставляет Тима нажать на рычаг ровно единожды. Тим начинает в точке (1). Он может только упасть вниз к точке (2) и нажать на рычаг. Когда он нажмет на рычаг, платформа под ним поднимется вместе с ним к односторонней поверхности (3) с такой скоростью, чтобы Тим не смог нажать на рычаг еще раз. Поверхность (3) не даст Тиму спуститься вниз, и ему останется лишь пройти к выходу из устройства (4). Когда платформа достигнет поверхности (3), она вернется к своему начальному состоянию, что позволяет использовать устройство столько раз, сколько потребуется. В игре один рычаг может контролировать больше одной платформы, а платформы могут контролироваться более чем одним рычагом, поэтому такое устройство позволит управлять платформами в одной точке уровня из другой точки на этом уровне.
====Устройство-'''перекресток'''====
[[Файл:Crossover.png|250px300px|thumb|right| Устройство-перекресток]]
Позволяет отправлять Тима или монстров вниз по маршрутам произвольной длины.
====Устройство-'''счетчик'''====
===Конструкция машины===
Разместим три устройства-счетчика далеко друг от друга. Состоящий из устройств нажатия рычага и ветвления маршрут, который мы построим для Тима, и будет подаваемой на вход ''программой''. Например, если мы хотим прибавить 1 к счетчику №2 в начале программы, то первая комната на пути будет устройством нажатия рычага, связанным с устройством прибавления единицы во втором устройстве-счетчике. Аналогично, рычаг может быть связан с устройством вычитания единицы в каком-либо счетчике. Тогда при активации, если значение счетчика не равно нулю, один монстр покинет счетчик. Чтобы выполнить переход при равенстве нулю, нам нужно отправить монстра в соответствующее устройство ветвления. Для этого все монстры, покидающие счетчик, будут попадать в соответствующую ему комнату, по которой они будут ходить. В полу этой комнаты будет множество платформ, работающих в качестве люков. Отправим Тима во второе устройство нажатия рычага, которое и откроет один из люков. Построенный нами путь под этим люком будет вести в устройство ветвления. Теперь Тим отправится в это устройство, но его маршрут сделаем значительно длиннее, чтобы он не мог опередить монстра, направляющегося туда же. В зависимости от того, был ли счетчик нулевым, Тим встретит или не встретит монстра в устройстве ветвления и пойдет по определенному пути. Операции ''прибавить'' и ''вычесть и перейти'' описаны. Операция ''остановиться'' проста: построим комнату с частью паззла и выходом с уровня. В эту комнату будет вести выход из очередного устройства, посещенного Тимом, при этом вполне возможно, что в данной конфигурации уровня в нее нельзя будет попасть, потому что Тим всегда будет выбирать другой выход в устройстве ветвления. Тогда уровень оказывается непроходимым.
Таким образом, определение того, возможно ли пройти данный уровень, эквивалентно проблеме останова.
}}
== См.также ==
* [[Неразрешимость задачи об эквивалентности КС-грамматик]]
* [[Игра «Жизнь»]]
== Источники информации ==
* [http://arxiv.org/abs/1412.0784 Linus Hamilton {{---}} Braid is undecidable]
[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]
[[Категория: Примеры неразрешимых задач]]
