В чем заключается проблема остановки алгоритма в теоретической информатике?

Проблема остановки (англ. Halting problem) в теоретической информатике заключается в вопросе о том, существует ли общий алгоритм, который, учитывая любую входную программу и входные данные, может определить, остановится ли программа в конечном итоге или будет работать вечно. ru.eitca.org

Неформально проблему можно поставить так: даны описание процедуры и её начальные входные данные, требуется определить, завершится ли когда-либо выполнение процедуры с этими данными или же процедура всё время будет работать без остановки. ru.ruwiki.ru ru.wikipedia.org

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

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