Проблема остановки (Halting problem) и Смертность (Mortality) в теории вычислимости кратко

Привет, Вы узнаете о том , что такое проблема остановки, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое проблема остановки, halting problem, смертность, mortality , настоятельно рекомендую прочитать все из категории Языки и методы программирования. Теория трансляции.

проблема остановки (англ. Halting problem) — это одна из проблем в теории алгоритмов , которая может неформально быть поставлена в виде:

Даны описание процедуры и ее начальные входные данные. Требуется определить: завершится ли когда-либо выполнение процедуры с этими данными; либо, что процедура все время будет работать без остановки.

Алан Тьюринг доказал в 1936 году, что проблема остановки неразрешима на машине Тьюринга. Другими словами, не существует общего алгоритма решения этой проблемы.

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

В терминах функций проблему можно доступно описать следующим образом:

Для любой функции F(G, start_state), которая может определять, останавливается ли другая функция, всегда можно написать такую функцию G(start_state), при передаче которой в F результат выполнения будет противоположен тому, который предсказывает F.

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

Доказательство

Рассмотрим множество алгоритмов, которые принимают на вход натуральное число и на выходе тоже выдают натуральное число. Выберем какой-нибудь полный по Тьюрингу язык программирования. Каждый алгоритм можно записать в виде конечной последовательности символов на этом языке. Упорядочим множество по алфавиту. При этом каждый алгоритм получит свой порядковый номер; более того существует алгоритм, который по номеру элемента восстанавливает его код в выбранном языке программирования. Назовем Анализатором гипотетический алгоритм, который получает на вход пару натуральных чисел , и:

• останавливается и возвращает 1, если алгоритм с номером не останавливается, получив на вход
• не останавливается в противном случае (если алгоритм с номером останавливается, получив на вход ).

Проблему остановки можно переформулировать следующим образом: существует ли Анализатор?

Теорема. Анализатора не существует.

Докажем это от противного. Об этом говорит сайт https://intellect.icu . Допустим, Анализатор существует. Напишем алгоритм Диагонализатор, который принимает на вход число , передает пару аргументов Анализатору и возвращает результат его работы. Другими словами, Диагонализатор останавливается в том и только том случае, если не останавливается алгоритм с номером , получив на вход число . Пусть — это порядковый номер Диагонализатора в множестве . Запустим Диагонализатор, передав ему это число . Диагонализатор остановится в том и только том случае, если алгоритм с номером (то есть, он сам) не останавливается, получив на вход число (какое мы ему и передали). Из этого противоречия следует, что наше предположение неверно: Анализатора не существует, что и требовалось доказать.

Проблема смертности (Mortality)

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

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

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

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

Вариант, в котором рассматриваются только конечные конфигурации, также неразрешим, как доказал Герман , который называет его «проблемой равномерной остановки». Он показывает, что проблема не просто неразрешима, но -полный .

Для устранения неоднозначности, « смертность матрицы» — это другая проблема, которая также неразрешима.

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

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

• Системы Полу-Туэ и марковские алгоритмы .
• Динамические системы закончились или или , для , где функция перехода кусочно-линейная (здесь в качестве состояния остановки выбирается произвольная точка, например начало координат).

Вау!! 😲 Ты еще не читал? Это зря!

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

Исследование, описанное в статье про проблема остановки, подчеркивает ее значимость в современном мире. Надеюсь, что теперь ты понял что такое проблема остановки, halting problem, смертность, mortality и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Языки и методы программирования. Теория трансляции