Проблема остановки — это одна из центральных проблем в теории алгоритмов, которая может неформально быть поставлена в виде:

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

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

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

Источник информации: Википедия

Формулировка проблемы остановки *

Пусть у нас есть строка с закодированной функцией A (всё равно на каком языке, это не принципиально). Требуется создать функцию F, которая определит, будет ли функция A выполняться вечно или нет (зависнет или не зависнет).

Естественно, работа A зависит от входных данных D. Соответственно F должна принимать на вход две переменных: код функции A и входные параметры D. А возвращать F(A, D) будет логическое значение: True — A(D) остановится, False — A(D) будет работать вечно.

По сути, F(A, D) должна проанализировать строки.

Проблем, подобных проблеме остановки, великое множество *

Проблема остановки только одна из множества так называемых массовых проблем. Эти проблемы существуют не только в теории алгоритмов, но и в математической логике. В алгебре такой проблемой является например проблема Туэ (о равенстве конечнопорождённых и конечноопределённых полугрупп). Одна из наиболее известных математических проблем для которой доказана алгоритмическая неразрешимость — десятая проблема Гильберта.

*Ресурс