Что такое проблема остановки?
Проблема остановки — это аргумент, призванный показать, что не может быть «алгоритма остановки» (алгоритма, который определяет, остановится или нет другой алгоритм) за конечное количество шагов.
- function H(A, x){
return halts(A(x));
}
Предположим, что существует алгоритм H, так что H(A, x) возвращает истину, если A (x) завершается и возвращает false, если A(x) не завершается. - function A'(A){
while(H(A, A)){
}}
Предположим, что существует алгоритм A', так что A'(A) не завершается, если
H(A, A) возвращает true и завершается, если H(A, A) возвращает false. - Случай 1: Предположим, что A’(A’) завершится, тогда H(A’, A’) вернет true.
Если H(A’, A’) возвращает true, то A’(A’) не завершится. - Случай 2: Предположим, что A’(A’) не завершится, тогда H(A’, A’) возвращает false.
Если H(A’, A’) возвращает false, то A’(A’) завершится. - Следовательно, либо H не существует, либо H не завершается для какого-либо алгоритма (алгоритмов). Другими словами, если H существует, то H не завершается для какого-либо алгоритма(ов).
Каково решение проблемы остановки?
Проблема остановки — это аргумент, призванный показать, что не может быть конечного алгоритма остановки (алгоритма, который определяет, остановится ли какой-либо данный алгоритм за конечное количество шагов). К счастью, ему не удалось опровергнуть существование неконечного алгоритма остановки (алгоритма остановки, у которого есть возможность не останавливаться). Справедливости ради, если мы должны решить, остановится ли данный алгоритм за конечное время, то имеет смысл, чтобы анализируемые алгоритмы были конечными. Проблема остановки демонстрирует, что существует несогласованный алгоритм, который косвенно ссылается сам на себя, а прямо ссылается на алгоритм остановки, и определить, остановится он или нет, невозможно за конечное количество шагов. Излишне говорить, что это не смертный приговор за существование останавливающего алгоритма, как уверяют вас многие теоретики вычислимости. Чтобы решить проблему остановки, мы разрабатываем алгоритм остановки, который останавливается, не возвращая значения, только в тех случаях, когда алгоритм неконечной остановки не останавливается.
- function H(A, x){
return halts(A(x));
}
Предположим, что существует алгоритм H(A, x), который возвращает true, если A(x) останавливается и false, если A(x) не останавливается. - function A'(A){
while(H(A, A)){
}}
Предположим, что существует алгоритм A', так что A'(A) не завершается, если
H(A, A) возвращает true и завершается, если H(A, A) возвращает false. - function V(A, x){
return !iff(A(x), A'(A'));
}
Предположим, что существует алгоритм конечного времени V(A, x ), который возвращает false, если A(x) имеет эквивалентную функциональность A'(A'), и возвращает true в противном случае. V проверяет корректность любых входных алгоритмов по отношению к H. - function H2(A, x){
if(V(A, x)){
return H(A, x);
}}
Мы определяем алгоритм H2 как составлен из трех алгоритмов: H, V и A'.
Если A(x) не эквивалентно A'(A') в отношении функциональности H, то V(A, x) возвращает true. Если V(A, x) возвращает true, то H2(A, x) возвращает H(A, x). Если A(x) имеет эквивалентную функциональность A'(A'), то V(A, x) возвращает false. Если V(A, x) возвращает false, то H2(A, x) останавливается, не возвращая значения, а не зацикливается вечно, как H(A, x). Для обработки ложного приведения типа может потребоваться дополнительная осторожность. Во всех случаях алгоритм остановки H2 останавливается и возвращает только точные значения. Таким образом, проблема остановки опровергается.
