Неразрешимость игры Braid — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Полное описание счетчиковой машины)
м (rollbackEdits.php mass rollback)
 
(не показано 12 промежуточных версий 3 участников)
Строка 2: Строка 2:
  
 
==Игровые объекты==
 
==Игровые объекты==
[[Файл:Tim.png|150px|thumb|right| Тим и часть паззла]]
+
 
 
: '''Тим''' (англ. ''Tim'') — главный герой игры. Возвышение перед ним иллюстрирует максимальную высоту его прыжка. На возвышении находится часть паззла. Цель игры — заполучить ее.
 
: '''Тим''' (англ. ''Tim'') — главный герой игры. Возвышение перед ним иллюстрирует максимальную высоту его прыжка. На возвышении находится часть паззла. Цель игры — заполучить ее.
: '''Монстр''' (англ. ''monstar''). Ходит по прямой линии, падает с возвышений, разворачивается, когда сталкивается с препятствием. Тим может оттолкнуться от него, чтобы прыгнуть выше.
+
: '''Монстр''' (англ. ''monstar''). Ходит по прямой линии, падает с возвышений, разворачивается, когда сталкивается с препятствием. Если Тим приземлится монстру на голову, то монстр погибнет, а Тим подскочит выше, чем при своем обычном прыжке. Лобовое столкновение с монстром для Тима смертельно.
[[Файл:Monstar.png|150px|thumb|right| Монстр]]
+
 
 
: '''Рычаг''' (англ. ''lever'') и '''платформа''' (англ. ''platform''). Подъем платформы контролируется нажатием рычага. Платформу можно установить таким образом, чтобы она поднималась при нажатии рычага и падала, столкнувшись с другим объектом.
 
: '''Рычаг''' (англ. ''lever'') и '''платформа''' (англ. ''platform''). Подъем платформы контролируется нажатием рычага. Платформу можно установить таким образом, чтобы она поднималась при нажатии рычага и падала, столкнувшись с другим объектом.
 +
: '''Односторонние поверхности''' (англ. ''one-way surfaces'') позволяют проходить сквозь них в одну сторону, но не пускают обратно. На иллюстрации Тим может запрыгнуть на поверхность (2), но не сможет спуститься вниз. Монстр пройдет из области (1) в область (2), но не пройдет назад.
  
: '''Односторонние поверхности''' (англ. ''one-way surfaces'') позволяют проходить сквозь них в одну сторону, но не пускают обратно. На иллюстрации Тим может запрыгнуть на поверхность (2), но не сможет спуститься вниз. Монстр пройдет из области (1) в область (2), но не пройдет назад.
 
[[Файл:Oneway.png|150px|thumb|right| Односторонние поверхности]]
 
 
: '''Пушка''' (англ. ''cannon''). С некоторой периодичностью пушка стреляет определенными игровыми объектами (монстрами, кроликами, огненными шарами или облаками).
 
: '''Пушка''' (англ. ''cannon''). С некоторой периодичностью пушка стреляет определенными игровыми объектами (монстрами, кроликами, огненными шарами или облаками).
 
: '''Кролик''' (англ. ''bunny''). Монстр убивает кролика, сталкиваясь с ним. Это может быть использовано, чтобы отделить одного монстра от группы монстров.
 
: '''Кролик''' (англ. ''bunny''). Монстр убивает кролика, сталкиваясь с ним. Это может быть использовано, чтобы отделить одного монстра от группы монстров.
  
 +
{| cellpadding="3" style="margin-left: auto; margin-right: auto;"
 +
| [[Файл:Tim.png|200px|thumb|right| Тим и часть паззла]]
 +
| [[Файл:Monstar.png|200px|thumb|right| Монстр]]
 +
| [[Файл:Oneway.png|200px|thumb|right| Односторонние поверхности]]
 +
|}
 +
 +
{| cellpadding="3" style="margin-left: auto; margin-right: auto;"
 +
| [[Файл:Platform.png|200px|thumb|right| Платформа с рычагом]]
 +
| [[Файл:Cannon.png|200px|thumb|right| Пушка]]
 +
| [[Файл:Bunny.png|80px|thumb|right| Кролик]]
 +
|}
 
==Перемотка времени==
 
==Перемотка времени==
Игрок может зажимать клавишу Shift, чтобы отматывать время назад, чтобы исправить соверешенную ошибку или даже отменить смерть персонажа. Обычно эта механика упрощает прохождение игроку, но никак не влияет на вычислимость игры. Однако, в Braid некоторые объекты существуют вне времени и на них не действует перемотка. Например, вневременной кролик продолжит прыгать вперед, даже когда весь мир возвращается назад во времени. На таких объектах основывается большинство уникальных головоломок в Braid. После отмотки времени назад Тим может промотать его снова вперед, аналогично командам ''undo'' и ''redo'' в различных редакторах. Как и с командами ''undo'' и ''redo'', совершение каких-либо действий после отмотки времени назад не позволит промотать его вперед.
+
Игрок может зажимать определенную клавишу, чтобы отматывать время назад, чтобы исправить соверешенную ошибку или даже отменить смерть персонажа. Обычно эта механика упрощает прохождение игроку, но никак не влияет на вычислимость игры. Однако, в Braid некоторые объекты существуют вне времени и на них не действует перемотка. Например, вневременной кролик продолжит прыгать вперед, даже когда весь мир возвращается назад во времени. На таких объектах основывается большинство уникальных головоломок в Braid. После отмотки времени назад Тим может промотать его снова вперед, аналогично командам ''undo'' и ''redo'' в различных редакторах. Как и с командами ''undo'' и ''redo'', совершение каких-либо действий после отмотки времени назад не позволит промотать его вперед.
  
 
==Неразрешимость==
 
==Неразрешимость==
 +
 +
Опишем проблему останова в игре Braid следующим образом. Пусть на вход подается уровень, содержащий вышеперечисленные игровые объекты. Требуется определить, возможно ли пройти этот уровень, то есть взять в определенной локации на уровне часть паззла и дойти до выхода с уровня. При этом мы считаем, что игрок двигается оптимально: из входа в очередную комнату к выходу из нее, а если встречает монстра, то прыгает на него и таким образом не может погибнуть.
 +
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Проблема останова игры «Жизнь» неразрешима.
+
Проблема останова игры Braid неразрешима.
 
|proof =  
 
|proof =  
Заметим, что если существует МТ, которая по начальной конфигурации уровня в Braid может определить, завершается ли она, то та же МТ может определить, останавливается ли любая МТ, что противоречит неразрешимости проблемы останова для МТ. Следовательно, необходимо описать процесс построения МТ в игре Braid. Построим [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ|счетчиковую машину]], эквивалентную МТ. Подаваемая на вход программа будет содержать следующие операции:
 
* прибавить: увеличивает на 1 значение выбранного счетчика.
 
* вычесть и перейти: сравнивает с нулем значение выбранного счетчика. Если оно больше нуля, из него вычитается единица; если равно нулю, происходит переход на указанную строку в программе.
 
* остановиться.
 
  
[[Файл:Platform.png|200px|thumb|right| Платформа с рычагом]]  
+
Если по Braid возможно построить [[Машина Тьюринга|машину Тьюринга]], то проблема останова игры неразрешима. Следовательно, необходимо описать процесс построения МТ в игре Braid. Построим [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ|счетчиковую машину]], эквивалентную МТ. Подаваемая на вход программа будет содержать следующие операции:
[[Файл:Cannon.png|200px|thumb|right| Пушка]]
+
# Прибавить: увеличивает на 1 значение выбранного счетчика.
[[Файл:Bunny.png|50px|thumb|right| Кролик]]
+
# Вычесть и перейти: сравнивает с нулем значение выбранного счетчика. Если оно больше нуля, из него вычитается единица; если равно нулю, происходит переход на указанную строку в программе.
[[Файл:Pull.png|200px|thumb|right| Устройство нажатия рычага]]
+
# Остановиться.
[[Файл:Crossover.png|200px|thumb|right| Устройство-перекресток]]
+
 
[[Файл:Counter.png|200px|thumb|right| Устройство-счетчик]]
+
В нашей машине счетчиками будут являться группы монстров. ''Программа'' будет выполняться Тимом: чтобы пройти уровень, ему нужно нажать на каждый рычаг на своем пути. Каждый рычаг выполняет либо операцию ''добавить'', либо ''вычесть и перейти''. Чтобы допустить переходы (''goto''), некоторые участки пути могут вести к более ранним местам на этом пути.
[[Файл:Branch.png|200px|thumb|right| Устройство ветвления]]
+
 
 +
Для это нам понадобится соорудить из простых игровых объектов служащие нашим целям '''устройства''' (англ. ''gadgets'').
 +
 
 +
===Устройства===
 +
====Устройство '''нажатия рычага'''====
 +
[[Файл:Pull.png|300px|thumb|right| Устройство нажатия рычага]]
 +
Заставляет Тима нажать на рычаг ровно единожды. Тим начинает в точке (1). Он может только упасть вниз к точке (2) и нажать на рычаг. Когда он нажмет на рычаг, платформа под ним поднимется вместе с ним к односторонней поверхности (3) с такой скоростью, чтобы Тим не смог нажать на рычаг еще раз. Поверхность (3) не даст Тиму спуститься вниз, и ему останется лишь пройти к выходу из устройства (4). Когда платформа достигнет поверхности (3), она вернется к своему начальному состоянию, что позволяет использовать устройство столько раз, сколько потребуется. В игре один рычаг может контролировать больше одной платформы, а платформы могут контролироваться более чем одним рычагом, поэтому такое устройство позволит управлять платформами в одной точке уровня из другой точки на этом уровне.
 +
====Устройство-'''перекресток'''====
 +
[[Файл:Crossover.png|300px|thumb|right| Устройство-перекресток]]
 +
Позволяет отправлять Тима или монстров вниз по маршрутам произвольной длины.
 +
====Устройство-'''счетчик'''====
 +
[[Файл:Counter.png|300px|thumb|right| Устройство-счетчик]]
 +
Позволяет прибавлять или вычитать единицу. В точке (1) находится некоторое количество монстров <tex>n</tex> {{---}} значение счетчика. Этим значением могут управлять устройства вычитания и прибавления единицы.
 +
=====Устройство прибавления единицы=====
 +
Пушка постоянно выстреливает новых монстров. Они отскакивают от платформы (2) и умирают на шипах. Устройство активируется, когда Тим нажимает рычаг, контролирующий платформу (2). Платформа ненадолго приподнимается, пропуская под собой одного монстра, и падает обратно. При каждой активации вышедший таким образом монстр проходит через одностороннюю поверхность (3) и оказывается заперт в участке (1), увеличивая таким образом счетчик на 1.
 +
=====Устройство вычитания единицы=====
 +
Пушка постоянно выстреливает новых кроликов. Как и в устройстве прибавления единицы, они отскакивают от платформы и умирают на шипах. При каждой активации платформа ненадолго сдвигается, пропуская одного кролика, который долетает до нижней границы (1) и касается ее. Если в участке (1) есть монстры, кролик погибнет от столкновения с одним из них, а тот при столкновении подскочит до верхней платформы и выйдет к участку (5). В противном случае кролик долетит до шипов (4) и погибнет там. Таким образом, при каждой активации, если значение счетчика не 0, один монстр убирается из счетчика и отправляется по определенному маршруту. Стоит заметить, что он не погибает, а идет по своему пути, что мы используем в устройстве ветвления.
 +
====Устройство '''ветвления'''====
 +
[[Файл:Branch.png|300px|thumb|right| Устройство ветвления]]
 +
Отправляет Тима по одному из двух различных путей в зависимости от того, есть ли в устройстве монстр. Тим попадает в устройство в точке (1). Площадка и лестница (2) находятся слишком высоко, чтобы запрыгнуть на них, поэтому, если в устройстве монстра нет, Тим может только дойти до конца и выйти в точке (3). Если же монстр есть, Тим не может пройти к выходу (3), и ему остается только прыгнуть на монстра, тем самым убивая его и подскакивая выше, чем при обычном прыжке. Единственное место для этого {{---}} участок (2), и при прыжке на монстра Тим окажется на площадке без возможности спуститься вниз. Он может покинуть устройство только поднявшись по лестнице. Наличие или отсутствие монстра определяет, какой из выходов сможет использовать Тим.
  
В нашей машине счетчиками будут являться группы монстров. "Программа" будет выполняться Тимом: чтобы пройти уровень, ему нужно нажать на каждый рычаг на своем пути. Каждый рычаг выполняет либо операцию "добавить", либо "вычесть и перейти". Чтобы допустить переходы (''goto''), некоторые участки пути могут вести к более ранним местам на этом пути.
+
===Конструкция машины===
  
Для это нам понадобится соорудить из простых игровых объектов следующие ''устройства'':
+
Разместим три устройства-счетчика далеко друг от друга. Состоящий из устройств нажатия рычага и ветвления маршрут, который мы построим для Тима, и будет подаваемой на вход ''программой''. Например, если мы хотим прибавить 1 к счетчику №2 в начале программы, то первая комната на пути будет устройством нажатия рычага, связанным с устройством прибавления единицы во втором устройстве-счетчике.  
* устройство '''нажатия рычага''': заставляет Тима нажать на рычаг ровно единожды. Тим начинает в точке (1). Он может только упасть вниз к точке (2) и нажать на рычаг. Когда он нажмет на рычаг, платформа под ним поднимется вместе с ним к односторонней поверхности (3) с такой скоростью, чтобы Тим не смог нажать на рычаг еще раз. Поверхность (3) не даст Тиму спуститься вниз, и ему останется лишь пройти к выходу из устройства (4). Когда платформа достигнет поверхности (3), она вернется к своему начальному состоянию, что позволяет использовать устройство столько раз, сколько потребуется. В игре один рычаг может контролировать больше одной платформы, а платформы могут контролироваться более чем одним рычагом, поэтому такое устройство позволит управлять платформами в одной точке уровня из другой точки на этом уровне.
 
* устройство-'''перекресток''': позволяет отправлять Тима или монстров вниз по маршрутам произвольной длины.
 
* устройство-'''счетчик''': позволяет прибавлять или вычитать единицу. В точке (1) находится некоторое количество монстров <tex>n</tex> {{---}} значение счетчика. Этим значением могут управлять устройства вычитания и прибавления единицы.
 
** устройство прибавления единицы: пушка постоянно выстреливает новых монстров. Они отскакивают от платформы (2) и умирают на шипах. Устройство активируется, когда Тим нажимает рычаг, контролирующий платформу (2). Платформа ненадолго приподнимается, пропуская под собой одного монстра, и падает обратно. При каждой активации вышедший таким образом монстр проходит через одностороннюю поверхность (3) и оказывается заперт в участке (1), увеличивая таким образом счетчик на 1.
 
** устройство вычитания единицы: пушка постоянно выстреливает новых кроликов. Как и в устройстве прибавления единицы, они отскакивают от платформы и умирают на шипах. При каждой активации платформа ненадолго сдвигается, пропуская одного кролика, который долетает до нижней границы (1) и касается ее. Если в участке (1) есть монстры, кролик погибнет от столкновения с одним из них, а тот при столкновении подскочит до верхней платформы и выйдет к участку (5). В противном случае кролик долетит до шипов (4) и погибнет там. Таким образом, при каждой активации, если значение счетчика не 0, один монстр убирается из счетчика и отправляется по определенному маршруту. Стоит заметить, что он не погибает, а идет по своему пути, что мы используем в устройстве ветвления.
 
* устройство '''ветвления''': отправляет Тима по одному из двух различных путей в зависимости от того, есть ли в устройстве монстр. Тим попадает в устройство в точке (1). Площадка и лестница (2) находятся слишком высоко, чтобы запрыгнуть на них, поэтому, если в устройстве монстра нет, Тим может только дойти до конца и выйти в точке (3). Если же монстр есть, Тим не может пройти к выходу (3), и ему остается только прыгнуть на монстра, тем самым убивая его и подскакивая выше, чем при обычном прыжке. Единственное место для этого {{---}} участок (2), и при прыжке на монстра Тим окажется на площадке без возможности спуститься вниз. Он может покинуть устройство только поднявшись по лестнице. Наличие или отсутствие монстра определяет, какой из выходов сможет использовать Тим.
 
  
Разместим три устройства-счетчика далеко друг от друга. Состоящий из устройств нажатия рычага и ветвления маршрут, который мы построим для Тима, и будет подаваемой на вход "программой". Например, если мы хотим добавить 1 к счетчику №2 в начале программы, то первая комната на пути будет устройством нажатия рычага, связанным с устройством прибавления единицы во втором устройстве-счетчике. Аналогично, рычаг может быть связан с устройством вычитания единицы в каком-либо счетчике. Тогда при активации, если значение счетчика не равно нулю, один монстр покинет счетчик. Чтобы выполнить переход при равенстве нулю, нам нужно отправить монстра в соответствующее устройство ветвления. Для этого все монстры, покидающие счетчик, будут попадать в соответствующую ему комнату, по которой они будут ходить. В полу этой комнаты будет множество платформ, работающих в качестве люков. Отправим Тима во второе устройство нажатия рычага, которое и откроет один из люков. Построенный нами путь под этим люком будет вести в устройство ветвления. Теперь Тим отправится в это устройство, но его маршрут сделаем значительно длиннее, чтобы он не мог опередить монстра, направляющегося туда же. В зависимости от того, был ли счетчик нулевым, Тим встретит или не встретит монстра в устройстве ветвления и пойдет по определенному пути.
+
Аналогично, рычаг может быть связан с устройством вычитания единицы в каком-либо счетчике. Тогда при активации, если значение счетчика не равно нулю, один монстр покинет счетчик. Чтобы выполнить переход при равенстве нулю, нам нужно отправить монстра в соответствующее устройство ветвления. Для этого все монстры, покидающие счетчик, будут попадать в соответствующую ему комнату, по которой они будут ходить. В полу этой комнаты будет множество платформ, работающих в качестве люков. Отправим Тима во второе устройство нажатия рычага, которое и откроет один из люков. Построенный нами путь под этим люком будет вести в устройство ветвления. Теперь Тим отправится в это устройство, но его маршрут сделаем значительно длиннее, чтобы он не мог опередить монстра, направляющегося туда же. В зависимости от того, был ли счетчик нулевым, Тим встретит или не встретит монстра в устройстве ветвления и пойдет по определенному пути.
Операции "прибавить" и "вычесть и перейти" описаны. Операция "остановиться" проста: построим комнату с частью паззла и выходом с уровня.
 
  
 +
Операции ''прибавить'' и ''вычесть и перейти'' описаны. Операция ''остановиться'' проста: построим комнату с частью паззла и выходом с уровня. В эту комнату будет вести выход из очередного устройства, посещенного Тимом, при этом вполне возможно, что в данной конфигурации уровня в нее нельзя будет попасть, потому что Тим всегда будет выбирать другой выход в устройстве ветвления. Тогда уровень оказывается непроходимым.
 +
 +
Таким образом, определение того, возможно ли пройти данный уровень, эквивалентно проблеме останова.
 
}}
 
}}
 +
 +
== См.также ==
 +
* [[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]]
 +
* [[Примеры неразрешимых задач: задача о замощении|Задача о замощении]]
 +
* [[Примеры неразрешимых задач: однозначность грамматики|Однозначность грамматики]]
 +
* [[Неразрешимость задачи об эквивалентности КС-грамматик]]
 +
* [[Игра «Жизнь»]]
 +
 +
== Источники информации ==
 +
* [http://arxiv.org/abs/1412.0784 Linus Hamilton {{---}} Braid is undecidable]
 +
 +
[[Категория: Теория формальных языков]]
 +
[[Категория: Теория вычислимости]]
 +
[[Категория: Примеры неразрешимых задач]]

Текущая версия на 19:26, 4 сентября 2022

Игра Braid — изданный в 2008 году платформер-головоломка, основным элементом которого является способность главного героя поворачивать время вспять.

Игровые объекты

Тим (англ. Tim) — главный герой игры. Возвышение перед ним иллюстрирует максимальную высоту его прыжка. На возвышении находится часть паззла. Цель игры — заполучить ее.
Монстр (англ. monstar). Ходит по прямой линии, падает с возвышений, разворачивается, когда сталкивается с препятствием. Если Тим приземлится монстру на голову, то монстр погибнет, а Тим подскочит выше, чем при своем обычном прыжке. Лобовое столкновение с монстром для Тима смертельно.
Рычаг (англ. lever) и платформа (англ. platform). Подъем платформы контролируется нажатием рычага. Платформу можно установить таким образом, чтобы она поднималась при нажатии рычага и падала, столкнувшись с другим объектом.
Односторонние поверхности (англ. one-way surfaces) позволяют проходить сквозь них в одну сторону, но не пускают обратно. На иллюстрации Тим может запрыгнуть на поверхность (2), но не сможет спуститься вниз. Монстр пройдет из области (1) в область (2), но не пройдет назад.
Пушка (англ. cannon). С некоторой периодичностью пушка стреляет определенными игровыми объектами (монстрами, кроликами, огненными шарами или облаками).
Кролик (англ. bunny). Монстр убивает кролика, сталкиваясь с ним. Это может быть использовано, чтобы отделить одного монстра от группы монстров.
Тим и часть паззла
Монстр
Односторонние поверхности
Платформа с рычагом
Пушка
Кролик

Перемотка времени

Игрок может зажимать определенную клавишу, чтобы отматывать время назад, чтобы исправить соверешенную ошибку или даже отменить смерть персонажа. Обычно эта механика упрощает прохождение игроку, но никак не влияет на вычислимость игры. Однако, в Braid некоторые объекты существуют вне времени и на них не действует перемотка. Например, вневременной кролик продолжит прыгать вперед, даже когда весь мир возвращается назад во времени. На таких объектах основывается большинство уникальных головоломок в Braid. После отмотки времени назад Тим может промотать его снова вперед, аналогично командам undo и redo в различных редакторах. Как и с командами undo и redo, совершение каких-либо действий после отмотки времени назад не позволит промотать его вперед.

Неразрешимость

Опишем проблему останова в игре Braid следующим образом. Пусть на вход подается уровень, содержащий вышеперечисленные игровые объекты. Требуется определить, возможно ли пройти этот уровень, то есть взять в определенной локации на уровне часть паззла и дойти до выхода с уровня. При этом мы считаем, что игрок двигается оптимально: из входа в очередную комнату к выходу из нее, а если встречает монстра, то прыгает на него и таким образом не может погибнуть.

Теорема:
Проблема останова игры Braid неразрешима.
Доказательство:
[math]\triangleright[/math]

Если по Braid возможно построить машину Тьюринга, то проблема останова игры неразрешима. Следовательно, необходимо описать процесс построения МТ в игре Braid. Построим счетчиковую машину, эквивалентную МТ. Подаваемая на вход программа будет содержать следующие операции:

  1. Прибавить: увеличивает на 1 значение выбранного счетчика.
  2. Вычесть и перейти: сравнивает с нулем значение выбранного счетчика. Если оно больше нуля, из него вычитается единица; если равно нулю, происходит переход на указанную строку в программе.
  3. Остановиться.

В нашей машине счетчиками будут являться группы монстров. Программа будет выполняться Тимом: чтобы пройти уровень, ему нужно нажать на каждый рычаг на своем пути. Каждый рычаг выполняет либо операцию добавить, либо вычесть и перейти. Чтобы допустить переходы (goto), некоторые участки пути могут вести к более ранним местам на этом пути.

Для это нам понадобится соорудить из простых игровых объектов служащие нашим целям устройства (англ. gadgets).

Устройства

Устройство нажатия рычага

Устройство нажатия рычага

Заставляет Тима нажать на рычаг ровно единожды. Тим начинает в точке (1). Он может только упасть вниз к точке (2) и нажать на рычаг. Когда он нажмет на рычаг, платформа под ним поднимется вместе с ним к односторонней поверхности (3) с такой скоростью, чтобы Тим не смог нажать на рычаг еще раз. Поверхность (3) не даст Тиму спуститься вниз, и ему останется лишь пройти к выходу из устройства (4). Когда платформа достигнет поверхности (3), она вернется к своему начальному состоянию, что позволяет использовать устройство столько раз, сколько потребуется. В игре один рычаг может контролировать больше одной платформы, а платформы могут контролироваться более чем одним рычагом, поэтому такое устройство позволит управлять платформами в одной точке уровня из другой точки на этом уровне.

Устройство-перекресток

Устройство-перекресток

Позволяет отправлять Тима или монстров вниз по маршрутам произвольной длины.

Устройство-счетчик

Устройство-счетчик

Позволяет прибавлять или вычитать единицу. В точке (1) находится некоторое количество монстров [math]n[/math] — значение счетчика. Этим значением могут управлять устройства вычитания и прибавления единицы.

Устройство прибавления единицы

Пушка постоянно выстреливает новых монстров. Они отскакивают от платформы (2) и умирают на шипах. Устройство активируется, когда Тим нажимает рычаг, контролирующий платформу (2). Платформа ненадолго приподнимается, пропуская под собой одного монстра, и падает обратно. При каждой активации вышедший таким образом монстр проходит через одностороннюю поверхность (3) и оказывается заперт в участке (1), увеличивая таким образом счетчик на 1.

Устройство вычитания единицы

Пушка постоянно выстреливает новых кроликов. Как и в устройстве прибавления единицы, они отскакивают от платформы и умирают на шипах. При каждой активации платформа ненадолго сдвигается, пропуская одного кролика, который долетает до нижней границы (1) и касается ее. Если в участке (1) есть монстры, кролик погибнет от столкновения с одним из них, а тот при столкновении подскочит до верхней платформы и выйдет к участку (5). В противном случае кролик долетит до шипов (4) и погибнет там. Таким образом, при каждой активации, если значение счетчика не 0, один монстр убирается из счетчика и отправляется по определенному маршруту. Стоит заметить, что он не погибает, а идет по своему пути, что мы используем в устройстве ветвления.

Устройство ветвления

Устройство ветвления

Отправляет Тима по одному из двух различных путей в зависимости от того, есть ли в устройстве монстр. Тим попадает в устройство в точке (1). Площадка и лестница (2) находятся слишком высоко, чтобы запрыгнуть на них, поэтому, если в устройстве монстра нет, Тим может только дойти до конца и выйти в точке (3). Если же монстр есть, Тим не может пройти к выходу (3), и ему остается только прыгнуть на монстра, тем самым убивая его и подскакивая выше, чем при обычном прыжке. Единственное место для этого — участок (2), и при прыжке на монстра Тим окажется на площадке без возможности спуститься вниз. Он может покинуть устройство только поднявшись по лестнице. Наличие или отсутствие монстра определяет, какой из выходов сможет использовать Тим.

Конструкция машины

Разместим три устройства-счетчика далеко друг от друга. Состоящий из устройств нажатия рычага и ветвления маршрут, который мы построим для Тима, и будет подаваемой на вход программой. Например, если мы хотим прибавить 1 к счетчику №2 в начале программы, то первая комната на пути будет устройством нажатия рычага, связанным с устройством прибавления единицы во втором устройстве-счетчике.

Аналогично, рычаг может быть связан с устройством вычитания единицы в каком-либо счетчике. Тогда при активации, если значение счетчика не равно нулю, один монстр покинет счетчик. Чтобы выполнить переход при равенстве нулю, нам нужно отправить монстра в соответствующее устройство ветвления. Для этого все монстры, покидающие счетчик, будут попадать в соответствующую ему комнату, по которой они будут ходить. В полу этой комнаты будет множество платформ, работающих в качестве люков. Отправим Тима во второе устройство нажатия рычага, которое и откроет один из люков. Построенный нами путь под этим люком будет вести в устройство ветвления. Теперь Тим отправится в это устройство, но его маршрут сделаем значительно длиннее, чтобы он не мог опередить монстра, направляющегося туда же. В зависимости от того, был ли счетчик нулевым, Тим встретит или не встретит монстра в устройстве ветвления и пойдет по определенному пути.

Операции прибавить и вычесть и перейти описаны. Операция остановиться проста: построим комнату с частью паззла и выходом с уровня. В эту комнату будет вести выход из очередного устройства, посещенного Тимом, при этом вполне возможно, что в данной конфигурации уровня в нее нельзя будет попасть, потому что Тим всегда будет выбирать другой выход в устройстве ветвления. Тогда уровень оказывается непроходимым.

Таким образом, определение того, возможно ли пройти данный уровень, эквивалентно проблеме останова.
[math]\triangleleft[/math]

См.также

Источники информации