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

D>Пусть ваш алгоритм с 0 и 1 на выходе существует. Берем его и строим другой: когда ваш алгоритм завершается с ответом о расходимости входного, запускаем бесконечный цикл. Получаем алгоритм, про который Тьюринг доказал, что его не существует
Я понял вашу мысль.
В таком случае "другой" алгоритм будет всегда гарантировано зависать и ломается доказательство Тьюринга, основанное на противоречии.

Таким образом, "другой" анализатор DA(K, X):
1) Вызывает нормальный анализатор A(K, X) (нормальный анализатор никогда не зависает)
2) Игнорирует результат работы нормального анализатора
3) Тут же зависает (например, abc: goto abc) (безусловно зависает)

То есть "другой" анализатор DA(K, X) — фактически всегда зависает.

Что будет?
Диагонализатор D(X) вызовет "другой" анализатор DA(X, X).
DA(X, X) анализатор вызовет сначала нормальный анализатор A(X, X), для программы X (а X это и есть диагонализатор).
Так как "другой" анализатор DA(K, X) всегда зависает (см. выше), то нормальный анализатор,
проанализировав его возвратит 0.
"Другой" анализатор забивает на результат работы нормального анализатора и зависает.
Таким образом диагонализатор D зависнет.
Это первое.

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

Третье. Вообще-то, Тьюринг, ничего не доказал.
В том виде анализатор, что предложил Тьюринг, имеет undefined behavour в зависимости от реализации самого анализатора.
Фактически, допустим, если анализатор как-то интерпретирует полученную программу, это фактически означает бесконечную рекурсию
D(X) -> A(X, X) ->интерпретация-> D(X) -> A(X, X) ...

И тут все implementation specific и зависит от того, какой анализатор первым найдет такую бесконечную рекурсию.
Четный или нечетный относительно самого первого вызова.
Если нечетный анализатор найдет зависание (считая, что первый анализатор имеет номер 1 в стеке вызовов), то вся цепочка вернет значение 1:

1 — зависание — 1 — зависание — 1 — зависание — 1(анализатор определил бесконечную рекурсию и возвратил 1)
Если четный — то самый первый анализатор (в стеке вызовов) зависнет, соответственно и вся цепочка зависнет.

зависание — 1 — зависание — 1 — зависание — 1(анализатор определил бесконечную рекурсию и возвратил 1)

То есть, если мы хотели получить неопределенное поведение такого анализатора, то мы его получили. Не более того.
И никаких выводов о существовании или несуществовании алгоритмов сделать нельзя.

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

D>Пусть ваш алгоритм с 0 и 1 на выходе существует. Берем его и строим другой: когда ваш алгоритм завершается с ответом о расходимости входного, запускаем бесконечный цикл. Получаем алгоритм, про который Тьюринг доказал, что его не существует
Я понял вашу мысль.
В таком случае "другой" алгоритм будет всегда гарантировано зависать и ломается доказательство Тьюринга, основанное на противоречии.

Таким образом, "другой" анализатор DA(K, X):
1) Вызывает нормальный анализатор A(K, X) (нормальный анализатор никогда не зависает)
2) Игнорирует результат работы нормального анализатора
3) Тут же зависает (например, abc: goto abc) (безусловно зависает)

То есть "другой" анализатор DA(K, X) — фактически всегда зависает.

Что будет?
Диагонализатор D(X) вызовет "другой" анализатор DA(X, X).
DA(X, X) анализатор вызовет сначала нормальный анализатор A(X, X), для программы X (а X это и есть диагонализатор).
Так как "другой" анализатор DA(K, X) всегда зависает (см. выше), то нормальный анализатор,
проанализировав его возвратит 0.
"Другой" анализатор забивает на результат работы нормального анализатора и зависает.
Таким образом диагонализатор D зависнет.
Это первое.
Вам хотелось зависнуть, вы и написали программу, которая всегда зависает. Какие выводы из этого можно сделать?
Да никаких!

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

Третье. Вообще-то, Тьюринг, ничего не доказал.
В том виде анализатор, что предложил Тьюринг, имеет undefined behavour в зависимости от реализации самого анализатора.
Фактически, допустим, если анализатор как-то интерпретирует полученную программу, это фактически означает бесконечную рекурсию
D(X) -> A(X, X) ->интерпретация-> D(X) -> A(X, X) ...

И тут все implementation specific и зависит от того, какой анализатор первым найдет такую бесконечную рекурсию.
Четный или нечетный относительно самого первого вызова.
Если нечетный анализатор найдет зависание (считая, что первый анализатор имеет номер 1 в стеке вызовов), то вся цепочка вернет значение 1:

1 — зависание — 1 — зависание — 1 — зависание — 1(анализатор определил бесконечную рекурсию и возвратил 1)
Если четный — то самый первый анализатор (в стеке вызовов) зависнет, соответственно и вся цепочка зависнет.

зависание — 1 — зависание — 1 — зависание — 1(анализатор определил бесконечную рекурсию и возвратил 1)

То есть, если мы хотели получить неопределенное поведение такого анализатора, то мы его получили. Не более того.
И никаких выводов о существовании или несуществовании алгоритмов сделать нельзя.