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

N>

N>function Анализатор(N, X) 
N>{
N>    if (is_halt(N, X))
N>    {
N>       while (true) { }
N>    }
N>    else
N>    {
N>       return 1;
N>    }
N>}
N>

Да, уже нашел на английской википедии, функция g().
И получается, что типа Анализатор (is_halt) в таком случае становится "предсказателем" результата работы этой функции g().
(в смысле не возвращаемого значения, а результата зависнет-не зависнет).

И функция g() имеет все способы чтобы "нагадить" Анализатору, сделав все в точности наоборот, вместо зависания, что-нибудь вернуть,
или вместо успешного завершения зависнуть.

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

Хотя у меня останутся возражения, что, мол, Анализатор возвратил результат функции (зависла или нет)
для того гипотитического запуска этой функции, который он сделал (или мог гипотетически сделать) сам,
а не того запуска, что запустил его самого.

То есть Тьюринг считает, что алгоритм должен работать строго детерминированно — как в функции в функциональных языках программирования,
а не императивных, с наличием глобальных переменных, и когда результат функции зависит от предыдыщих (разные всякие undefined behaviour)
вызовов. Проще говоря, Тьюринг не допускает дребезга результатов алгоритмов (типа как undefined behaviour).

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

N>

N>function Анализатор(N, X) 
N>{
N>    if (is_halt(N, X))
N>    {
N>       while (true) { }
N>    }
N>    else
N>    {
N>       return 1;
N>    }
N>}
N>

Да, уже нашел на английской википедии, функция g().
И получается, что типа Анализатор (is_halt) в таком случае становится "предсказателем" результата работы этой функции g().
(в смысле не возвращаемого значения, а результата зависнет-не зависнет).

И функция g() имеет все способы чтобы "нагадить" Анализатору, сделав все в точности наоборот, вместо зависания, что-нибудь вернуть,
или вместо успешного завершения зависнуть.

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

Хотя у меня останутся возражения, что, мол, Анализатор возвратил результат функции (зависла или нет)
для того гипотитического запуска (или запуска через интерпретацию) этой функции, который он сделал (или мог гипотетически сделать) сам,
а не того запуска, что запустил его самого.

То есть Тьюринг считает, что алгоритм должен работать строго детерминированно — как в функции в функциональных языках программирования,
а не императивных, с наличием глобальных переменных, и когда результат функции зависит от предыдыщих (разные всякие undefined behaviour)
вызовов. Проще говоря, Тьюринг не допускает дребезга результатов алгоритмов (типа как undefined behaviour).