проблема останова

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

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