Смертность (теория вычислимости)

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

Напротив, проблема смертности для машин Тьюринга спрашивает, останавливаются ли все выполнения машины, начиная с любой конфигурации .

В приведенном выше утверждении конфигурация определяет как состояние машины (не обязательно ее исходное состояние),положение ленты и ее содержимое. Хотя мы обычно предполагаем, что в начальной конфигурации все ячейки на ленте, кроме конечного числа, являются пустыми, в задаче смертности лента может иметь произвольное содержимое, включая бесконечное количество записанных на ней непустых символов.

Филип К. Хупер доказал в 1966 году ^[1] что проблема смертности неразрешима . Это справедливо как для машины с бесконечной в обе стороны лентой, так и для машины с полубесконечной лентой. Обратите внимание, что этот результат не следует напрямую из хорошо известной проблемы полной функции (Останавливается ли данная машина для каждого ввода?), поскольку последняя проблема касается только допустимых вычислений (начиная с начальной конфигурации).

Неразрешим также вариант, в котором рассматриваются только конечные конфигурации, как доказал Герман: ^[2] который называет это «проблемой равномерной остановки». Он показывает, что проблема не просто неразрешима, но $\Pi _{2}^{0}$ -полный .

Дополнительные модели

Естественно, проблему можно перефразировать для любой вычислительной модели, в которой есть понятия «конфигурация» и «переход». Член модели будет смертен, если не будет конфигурации, ведущей к бесконечной цепочке переходов. Проблема смертности оказалась неразрешимой для:

Системы Полу-Туэ и марковские алгоритмы . ^[1]
Счетные машины ^[3]
Динамические системы закончились ${\mathbb {R} }^{n}$ или ${\mathbb {Q} }^{n}$ или ${\mathbb {Z} }^{n}$ , для $n\geq 2$ , где функция перехода кусочно-линейная ^[4]^[5] (здесь в качестве состояния остановки выбирается произвольная точка, например начало координат).

Ссылки

^ Перейти обратно: ^а ^б Хупер, П. «Неразрешимость проблемы бессмертия машины Тьюринга». Журнал символической логики . 31 (2): 219–234. дои : 10.2307/2269811 .
^ Герман, Габор. «Простое решение проблемы равномерной остановки». Журнал символической логики . 34 (4): 639–640. дои : 10.2307/2270856 .
^ Курц, Стюарт А.; Саймон, Янош (2007). «Неразрешимость обобщенной проблемы Коллатца». Международная конференция по теории и приложениям моделей вычислений, TAMC 2007 . дои : 10.1007/978-3-540-72504-6_49 .
^ Блондель, Винсент Д.; Бурне, Оливье; Койран, Паскаль; Пападимитриу, Христос Х.; Цициклис, Джон Н. (28 марта 2001 г.). «Определение устойчивости и смертности кусочно-аффинных динамических систем» (PDF) . Теоретическая информатика . 255 (1): 687–696. дои : 10.1016/S0304-3975(00)00399-6 . ISSN 0304-3975 .
^ Бен-Амрам, Амир М. (1 января 2015 г.). «Смертность итерированных кусочно-аффинных функций над целыми числами: разрешимость и сложность» . Вычислимость . 4 (1): 19–56. дои : 10.3233/COM-150032 . ISSN 2211-3568 .

Эта по информатике статья незавершена . Вы можете помочь Википедии, расширив ее .

[:0-1] Перейти обратно: ^а ^б Хупер, П. «Неразрешимость проблемы бессмертия машины Тьюринга». Журнал символической логики . 31 (2): 219–234. дои : 10.2307/2269811 .

[2] Герман, Габор. «Простое решение проблемы равномерной остановки». Журнал символической логики . 34 (4): 639–640. дои : 10.2307/2270856 .

[3] Курц, Стюарт А.; Саймон, Янош (2007). «Неразрешимость обобщенной проблемы Коллатца». Международная конференция по теории и приложениям моделей вычислений, TAMC 2007 . дои : 10.1007/978-3-540-72504-6_49 .

[4] Блондель, Винсент Д.; Бурне, Оливье; Койран, Паскаль; Пападимитриу, Христос Х.; Цициклис, Джон Н. (28 марта 2001 г.). «Определение устойчивости и смертности кусочно-аффинных динамических систем» (PDF) . Теоретическая информатика . 255 (1): 687–696. дои : 10.1016/S0304-3975(00)00399-6 . ISSN 0304-3975 .

[5] Бен-Амрам, Амир М. (1 января 2015 г.). «Смертность итерированных кусочно-аффинных функций над целыми числами: разрешимость и сложность» . Вычислимость . 4 (1): 19–56. дои : 10.3233/COM-150032 . ISSN 2211-3568 .

[1]

[2]

[3]

[4]

[5]