Я вот тут в форуме Алгоритмы

Автор: GhostCoders
Дата: 08.03.20

(тоже на rsdn) написал про ошибку в доказательстве Тьюринга о неразрешимости проблемы остановки.
Но что-то тот форум какой-то вялый.
Может кто-то здесь прокомментирует?

Доказательство Тьюринга.

Сейчас в соседней ветке прочитал про диагональный элемент и неполноту Геделя.
Возможно, это связано (и Тьюринг строил свое доказательство под впечатлением доказательства Геделя о неполноте арифметики Пеано, вводя диагонализатор).
Но тем не менее.

Тут весьма простая ошибка.
Для того чтобы вы лучше это поняли, я представлю вам ошибочное доказательство того,
что уравнение X — 3 = 5 не имеет решений.

"Уравнение X — 3 = 5 не имеет решений. Докажем это от обратного.
Допустим уравнение X — 3 = 5 имеет какое-то решение.
Скажем, что А — это решение уравнения и А <= 0 (А меньше или равно 0).
В таком случае, при максимально возможном значении А в 0 мы имеем:
0 — 3 = 5
-3 = 5
Очевидно, что -3 не равно 5, более того, -3 < 5.
Для значений А меньших 0, значение в левой части уравнения будет, очевидно, еще меньше, чем -3.
Следовательно, уравнение X — 3 = 5 не имеет решений."

Тут раздается возглас с задней парты и ученик спрашивает учителя:
"А для чего мы предположили что А меньше или равно 0? Только для доказательства того, что это уравнение не имеет решений?!"
"Да" — звучит невозмутимый ответ учителя.
Все остальные ученики в классе поворачивают головы назад и недовольно
смотрят на выскочку, который посмелил бросить тень на гениальное доказательство.

Вот таким-же приемом Тьюринг доказывает невозможность существования анализатора.

В случае уравнения, если мы сделали допущение, что А <= 0, и рассмотрели этот случай,
то мы должны рассмотреть случай, когда А > 0.
Мы же этого не сделали.

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

Вот эти "странные" допущения Тьюринга:

Назовем Анализатором гипотетический алгоритм, который получает на вход пару натуральных чисел (N,X), и:

останавливается и возвращает 1, если алгоритм с номером N не останавливается, получив на вход X
не останавливается в противном случае (если алгоритм с номером N останавливается, получив на вход X).

"Странное" тут в том, что Тьюринг допускает анализатор, который зависает сам.
И не рассматривает остальные варианты.

Другой (мой) вариант существования анализатора, это случай, когда анализатор всегда останавливается
и возвращает 1 или 0 в зависимости от того, зависла или нет анализируемая программа.

Это же просто и естественно (особенно для программистов), иметь анализатор,
который возвратит 1 или 0, типа функции is_halt(), которая принимает на вход некую программу.
Если переданная программа может потенциально зависнуть, то сам анализатор должен быть валиден и всегда останавливаться,
возращая 1 или 0.

Надеюсь, я понятно объяснился.