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

GC>Программа — принимает на вход натуральное число Х и на выходе дает натуральное число.
GC>Я понимаю, что диагонализатор тут нужен для того, чтобы анализатор анализировал сам себя.
GC>Так как анализируемая программа принимает только один аргумент, то чтобы анализатор анализировал сам себя, нужен
GC>некий "адаптер" в виде диагонализатора.

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

Это, кстати, напрямую связано с бесконечностью памяти. Если бы память была конечной, сложность программы тоже была бы конечной.

GC>По мне это странный подход.
GC>Первая претензия. Почему именно предполагается существование анализатора, который останавливается, когда
GC>анализируемая программа зависает и наоборот? По моему это какое-то подыгрывание результату.

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

GC>Почему бы, например, не предположить, что анализатор вернет 1 если анализируемая программа зависнет, и 0 — если остановится?
GC>То есть анализатор никогда не зависнет. Тогда он сам для себя должен возвратить 0. В таком случае нет никакого противоречия.

Чтобы что-то "вернуть", надо остановиться. Пока анализатор продолжает работать, он еще ничего не вернул.

GC>И такой практический толк в анализаторе, предположенным Тьюрингом, который может сам зависнуть?

Тьюринг отвечал на вопрос, "что такое алгоритм". Его ответ — "алгоритм, это программа для машины Тьюринга, которая останавливается после конечного числа шагов". Не каждая программа для машины Тьюринга является алгоритмом.

Следующих вопрос, какая задача является вычислительно разрешимой. Ответ — та, для которой может быть составлен алгоритм. И оказывается, что не всякая задача, которую можно сформулировать, является вычислительно разрешимой. Классический пример — проблема останова, программа, которая проанализирует другую программу и скажет, останавливается ли она.

GC>Вот запустили мы такой анализотор с какой-то программой и ждет результата.
GC>Прождали день. Этот анализатор все еще работает и на второй день может вернуть 1, или же окночательно завис?
GC>Только для доказательства того, что такой анализатор противоречив?

Да.

GC>По моему, это "доказательство" лишь доказывает, что тот анализатор, допущенный Тьюррингом, именно в такой форме противоречив, а конкретно
GC>имеет неопределенное поведение (undefined behaviour), не более.

Это доказательство доказывает наличие алгоритмически неразрешимых задач.