Существуют ли программы, которые никогда не останавливаются и не имеют доказательств отсутствия завершения?

Как черные дыры в информатике. Мы можем только знать, что они существуют, но когда у нас есть один из них, мы никогда не узнаем, что это один из них.

halting-problem correctness-proof Отакар Мольнар Лопес
источник

Решение проблемы остановки, по крайней мере, так же сложно, как доказательство теорем (учитывая теорему вы можете просто написать такую программу, как , программа завершается тогда и только тогда, когда теорема верна). Если бы не было таких программ, это означало бы, что вы могли бы доказать все теоремы, которые, как известно, являются ложными.

T

$T$ if T is true then halt else loop forever

Бакуриу

@Bakuriu: Как бы вы написали if T is true?

ruakh

@ruakh: традиционный методFor each string S in the (countable) universe of possible strings: If S is a syntactically valid proof of T, halt.

Quuxplusone

@Quuxplusone: Ну да, но это, похоже, не вписывается в конструкцию Бакуриу. , ,

Руах

Это интересно, но я не знаю. Можете ли вы уточнить, пожалуйста?

Evorlor

Ответы:

Есть действительно такие программы. Чтобы доказать это, давайте предположим, что для каждой машины, которая не останавливается, есть доказательство, что она не останавливается.

Эти доказательства являются строками конечной длины, поэтому мы можем перечислить все доказательства длины меньше для некоторого целого числа . $s$ $s$

Затем мы можем использовать это для решения проблемы остановки следующим образом: Учитывая машину Тьюринга и вход , мы используем следующий алгоритм: $M$ $x$

s := 0
while (True)
    test if machine M halts on input x in s steps
    look at all proofs of length s and see if they prove M doesn't halt on input x
    set s := s + 1

Если останавливается на входе , то он останавливается за некоторое конечное число шагов , поэтому наш алгоритм завершается. $M$ $x$ $s$

Если не останавливается на входе , то, по нашему предположению, есть некоторая длина доказательства где есть доказательство того, что не останавливается. Так что в этом случае наш алгоритм всегда завершается. $M$ $x$ $s$ $M$

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

jmite
источник

Я думаю, что отсюда следует и более слабая форма теоремы Гёделя о неполноте. По сути, существуют вещи, которые являются правдой, но не могут быть доказаны. Это один из моих новых любимых мысленных экспериментов.

Джейк,

Как вы думаете, попытка доказать P = NP или попытка найти нечетное идеальное число может быть одной из этих программ?

Отакар Мольнар Лопес

Это не имеет смысла, потому что не завершающие программы не являются ни доказательствами, ни цифрами, но идея, к которой вы стремитесь, была выдвинута. Некоторые говорят, что PvsNP недоказуемо

Джейк

@ Джейк Я считаю, что частью мотивации машин Тьюринга было более четкое выражение идеи, лежащей в основе теоремы Годеля.

cpast

Для более конкретного примера давайте предположим, что теория, которую мы используем для наших доказательств, имеет следующие (вполне разумные, IMO) особенности:

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

С этими допущениями следующая программа никогда не остановится, но не может быть доказана (в рамках теории, которую мы используем) не остановить:

let k := 0;
repeat:
    let k := k + 1;
    let s := binary expansion of k, excluding leading 1 bit;
while s does not encode a proof of a contradiction;
halt.

Ключевой деталью здесь является первое предположение выше, а именно, что теория, которую мы используем для наших доказательств, непротиворечива. Очевидно, нам нужно принять это, чтобы наши доказательства чего-то стоили, но вторая теорема Гёделя о неполноте говорит о том, что для любой достаточно выразительной и эффективно аксиоматизированной теории мы не можем на самом деле доказать это (за исключением, возможно, в какой-то другой теории, последовательность которой мы тогда надо предполагать и тд и тп).

Илмари Каронен
источник