Здравствуйте, Pzz, Вы писали:

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

GC>>Первая претензия. Почему именно предполагается существование анализатора, который останавливается, когда
GC>>анализируемая программа зависает и наоборот? По моему это какое-то подыгрывание результату.
Pzz>Потому что по определению машины Тьюринга, валидная программа должна остановиться, чтобы выдать какой-то результат.
Это-то понятно.
Однако сам Тьюринг допускает существование анализатора лишь в заранее невалидной форме —
который зависает, если анализируемая программа завершилась и выдала результат (см. доказательство Тьюринга).

GC>>Почему бы, например, не предположить, что анализатор вернет 1 если анализируемая программа зависнет, и 0 — если остановится?
GC>>То есть анализатор никогда не зависнет. Тогда он сам для себя должен возвратить 0. В таком случае нет никакого противоречия.
Pzz>Чтобы что-то "вернуть", надо остановиться. Пока анализатор продолжает работать, он еще ничего не вернул.
Вы опять ничего не поняли. Я предположил существование валидного анализатора, который всегда останавливается
и выдает результат в зависимости от анализа переданной программы:
1 — если анализируемая программа зависла
0 — если анализируемая программа завершилась (и вернула какое-то значение).
В такой форме анализатор должен вернуть 0 в случае если анализатор будет запущен для самомого себя.

По-моему вы никак не поймете суть моих претензий к доказательству Тьюринга о невозможности создания анализатора.
Тут весьма простая ошибка.
Для того чтобы вы лучше это поняли, я представлю вам ошибочное доказательство того,
что уравнение 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.

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