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

GC>·>Ничего не понял. Что за g()? Каким ещё предсказателем?
GC>На самом деле довольно просто.
GC>Вместо русской вики я открыл английскую и сразу понял фокус.
GC>

GC>def g():
GC>    if halts(g):
GC>        loop_forever()
GC>

GC>Допустим анализатор (функция halts) решил, что функция g() зависнет.
Анализатор на вход берёт собственно сам текст этого самого g().

GC>То эта самая функция g(), назло анализатору (для того, чтобы ему "нагадить" и дискредитировать его) нагло возвращает какое-то значение.
Функция уже определена в виде этого кода. Покажи где в этом коде оператор нагаживания, я что-то не вижу.

GC>То есть делает "предсказание" анализатора неверным.
GC>И наоборот, если анализатора для g вернет что она не зависнет, то она зависает.
GC>Но думаю, вы это и сами знали?
У тебя какие-то хитрые алгоритмы, обладающие сознанием, волей и желанием нагадить. С такими алгоритмами да, теоремы доказывать не получится, их только уговаривать можно, Кнутом и Страуструпом.

GC>Да, все верно. Только может быть статическим, а может и интерпретировать программу, например.
GC>При интерпретации программы сохранять список посещенных полных состояний МТ и проверять на каждом шагу,
GC>что новое состояние не находится в этом списке. Если находится — то мы определили, что анализуруемый алгоритм
И что с этим можно сделать полезного?

GC>завис циклически за конечное число шагов. Ациклические зависания таким способом не определить.
И как мы отличим ациклический алгоритм от циклического? Ну сделали мы TREE(3) шагов — цикла не нашлось. Что это значит? Да ничего.

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

GC>·>Ничего не понял. Что за g()? Каким ещё предсказателем?
GC>На самом деле довольно просто.
GC>Вместо русской вики я открыл английскую и сразу понял фокус.
GC>

GC>def g():
GC>    if halts(g):
GC>        loop_forever()
GC>

GC>Допустим анализатор (функция halts) решил, что функция g() зависнет.
Анализатор на вход берёт собственно сам текст этого самого g().

GC>То эта самая функция g(), назло анализатору (для того, чтобы ему "нагадить" и дискредитировать его) нагло возвращает какое-то значение.
Функция уже определена в виде этого кода. Покажи где в этом коде оператор нагаживания, я что-то не вижу.

GC>То есть делает "предсказание" анализатора неверным.
GC>И наоборот, если анализатора для g вернет что она не зависнет, то она зависает.
GC>Но думаю, вы это и сами знали?
У тебя какие-то хитрые алгоритмы, обладающие сознанием, волей и желанием нагадить. С такими алгоритмами да, теоремы доказывать не получится, их только уговаривать можно, Кнутом и Страуструпом.

GC>Да, все верно. Только может быть статическим, а может и интерпретировать программу, например.
GC>При интерпретации программы сохранять список посещенных полных состояний МТ и проверять на каждом шагу,
GC>что новое состояние не находится в этом списке. Если находится — то мы определили, что анализуруемый алгоритм
И что с этим можно сделать полезного?

GC>завис циклически за конечное число шагов. Ациклические зависания таким способом не определить.
И как мы отличим ациклический алгоритм от циклического? Ну сделали мы TREE(3) шагов — цикла не нашлось. Что это значит? Да ничего. Т.е. и циклические алгоритмы таким способом тоже не определить. Можно определить лишь алгоритмы работающие не дольше некоего N кол-ва шагов. Собственно всё. Для этого можно просто счётчик операций запустить и не выпендриваться с запоминанием состояний.