Оракул существует

Я не вызывал его вне функции. Я его вызывал только внутри функции. И внутри функции он выдал неправильный ответ.

Оракул существует

я возвращаю 0. конец.

И функция завершается. Значит ваш 0 был неправильным ответом.

Оракул существует

А если вы все параметры внутри предавали правильно,

Во-первых, оракул должен правильно работать для всех функций. В том числе и тех, которые вызывают его с "неправильными" параметрами. Во-вторых — какое бы значение он тут не вернул — правильным оно быть не может, потому что поведение функции будет противоречить тому, что вернул оракул.

Оракул существует

снаружи функции он вернет 1.
внутри он вернет 0.

Не никакого снаружи и внутри. Вызов ровно один. Ответ на него неправильный.

Со стороны это кажется смешным…

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

Оракул существует

если вы хотите вызвать его внутри f

Я его вызвал внутри f. Передал те параметры, что вы сказали (f, 0). Он вернул ответ, который вы сказали. Этот ответ неправильный, функция повела себя по другому.

Оракул существует

Ок, давайте по порядку.

функция, в которой был вызван оракул

f

параметры фунцкции

()

место в функции из которого вызван оракул

вторая строка. Внутри оператора проверки условия.

значения внутренние переменные к даному времени

внутренних переменных нет

итерация вызова если в цикле

не в цикле.

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

Оракул существует

просто передайте ему ctx.

Ок. Не спрашиваю, какое значение должно храниться в ctx. Допустим, правильное.
Передал ctx. Какое значение вернул оракул?

Оракул существует

Покажите как надо. Что сюда вписать и какой результат вернет оракул?

f();
func f() {
  if (O(f, /*здесь может быть ваша реклама*/)) {
    while (true) {}
  }
}

Оракул существует

вычисляется ли оракул рекурсивно или нет.

Что и как вы в вашем оракуле вычисляете — это детали реализации. Хотите — вызывайте себя рекурсивно, если встретили в тексте вызов себя. Хотите, вычисляйте как-то еще. Хотите — не вычисляйте вообще. Только в место вызова ответ правильный верните. Ваш оракул (и никакой другой, к слову) этого не делает.

Просто я удивляюсь тому, что кто-то передает на вход мусор и удивляется, что на выходе — тоже мусор…

Где и какой мусор передавали на вход вашему оракулу и как нужно было передавать правильно?

Оракул существует

Потому что он только что дал неправильный ответ. Не "правильный, но непригодный", а именно неправильный. Оракула вызвали один раз. Спросили об одной функции. Его ответ не совпал с фактическим поведением этой функции.

Или вам больше нравится более мягкая характеристика "Работает. Иногда правильно, но не всегда"? Ок, можно и так сказать)

Оракул существует

По существу вам уже 100 раз написали)

Оракул существует

И будет неправ, потому что функция f в таком случае завершится. А для функции которая завершается, правильный ответ — 1. Оракул не работает.

Оракул существует

Оракул вызывается ровно в одном месте один раз. Нет никаких вызовов "для нас" и "не для нас".
И в этом одном единственном месте своего вызова ответ оракула был неправильным. Ваш оракул не работает.

Оракул существует

То есть ответ 0? Ок, не беда. Перепроверим.

Так. 0 значит, что функция f не завершается. Проверим:

  if (O(f, (f, 0))) {
    while (true) {}
  }

ой. Мы не попали внутрь ифа и функция завершилась. Ответ вашего оракула оказался неправильным :(

Оракул существует

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

Замечательно. Опустим все детали реализации. Считаем, что у оракула halts есть возможность узнать все, о чем вам хочется. Какой ответ он выдаст?

f();
func f() {
  if (halts(f)) {
    while(true) {}
  }
}

Оракул существует

если в нее передавать заданные параметры, то она вычисляет правильный ответ.

Увы, не вычисляет(

https://habr.com/ru/post/436090/#comment_19621996

Оракул существует

O(f, ctx) = 1 при 0 при ctx = (f, 0)

О! У нас именно этот случай. Повезло!
Так, значение 1. Значит функция f завершается. Проверим:

  if (O(f, ctx)) {
    while (true) {}
  }

ой. Мы попали внутрь ифа и в бесконечный цикл. Ответ вашего оракула оказался неправильным :(

два верных результата

Откуда два? В коде только один вызов O. Да и тот вернул неправильный ответ.

Оракул существует

Я понимаю, что он предложил другой оракул. Но подавал он его, все же, именно в качестве опровержения моих слов :)

Оракул существует

Оракул О попросит у вас передавать ему контекст.

Я передал. Вот тут: https://habr.com/post/436090/#comment_19621830

Что вернет ваш оракул?

Если второй оракул для вас не оракул

Речь идет о конкретной задаче. В ней нужно определить, завершает ли алгоритм свое выполнение. Любой алгоритм либо завершается, либо нет. Он не может "завершаться наполовину". То, что вы решили задачу "определить, завершает ли алгоритм свое выполнение, или ответить хз" — это, конечно, круто. Но к исходной задаче это никакого отношения не имеет.

Оракул существует

у вас неправильный пример.
Должен быть
if (O(f, ctx)) {

Ок.

f();
func f() {
  ctx = (f, 0)
  if (O(f, ctx)) {
    while (true) {}
  }
}

Здесь ваш оракул вернет 0? В таком случае его ответ неверный. Выполнение функции завершится. Вернет 1? Ответ тоже неверный. Выполнение функции не завершится.