Изменения

Перейти к: навигация, поиск

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

334 байта добавлено, 22:40, 15 января 2016
Добавлены категории, источники информации
Разместим три устройства-счетчика далеко друг от друга. Состоящий из устройств нажатия рычага и ветвления маршрут, который мы построим для Тима, и будет подаваемой на вход "программой". Например, если мы хотим добавить 1 к счетчику №2 в начале программы, то первая комната на пути будет устройством нажатия рычага, связанным с устройством прибавления единицы во втором устройстве-счетчике. Аналогично, рычаг может быть связан с устройством вычитания единицы в каком-либо счетчике. Тогда при активации, если значение счетчика не равно нулю, один монстр покинет счетчик. Чтобы выполнить переход при равенстве нулю, нам нужно отправить монстра в соответствующее устройство ветвления. Для этого все монстры, покидающие счетчик, будут попадать в соответствующую ему комнату, по которой они будут ходить. В полу этой комнаты будет множество платформ, работающих в качестве люков. Отправим Тима во второе устройство нажатия рычага, которое и откроет один из люков. Построенный нами путь под этим люком будет вести в устройство ветвления. Теперь Тим отправится в это устройство, но его маршрут сделаем значительно длиннее, чтобы он не мог опередить монстра, направляющегося туда же. В зависимости от того, был ли счетчик нулевым, Тим встретит или не встретит монстра в устройстве ветвления и пойдет по определенному пути.
Операции "прибавить" и "вычесть и перейти" описаны. Операция "остановиться" проста: построим комнату с частью паззла и выходом с уровня.
}}
== Источники информации ==* [http://arxiv.org/abs/1412.0784 Linus Hamilton {{---}}Braid is undecidable] [[Категория: Теория формальных языков]][[Категория: Теория вычислимости]][[Категория: Примеры неразрешимых задач]]
74
правки

Навигация