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

Дано описание алгоритма и конечное множество входных данных. Надо решить, выполнение алгоритма завершится, будет ли он выполняться бесконечно

Обзор

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

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

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

Рассмотрим множество алгоритмов S, которые принимают на вход натуральное число и на выходе тоже выдают натуральное число.

Выберем какую полную по Тьюрингу язык программирования. Каждый алгоритм можно записать в виде конечной последовательности символов на этом языке. Упорядочим множество S лексикографически (в словарном порядке), при этом каждый алгоритм получит свой порядковый номер. Назовем Анализатором гипотетический алгоритм, который получает на вход пару натуральных чисел (N, X), и:

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

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

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

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

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

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

Случай, когда результатом вычисления функции f является булево значение истина или ложь (или множество {0, 1}) называют задачей, которая может быть разрешимой или неразрешимой в зависимости от вычислимости функции f.

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

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

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

Изображения по теме

  • Проблема остановки