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

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

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

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