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

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

Учитывая Машина Тьюринга, решите, останавливается ли он при запуске в любой конфигурации (не обязательно в начальной)

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

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

Этот Информатика статья - это заглушка. Вы можете помочь Википедии расширяя это. v т е