-1, если в функции используется halts( т.е. halts(halts) == -1)
Алгоритм работает либо конечное время, либо бесконечное. Третьего варианта быть не может. Если ваш "оракул" для каких-то случаев выдает третий вариант "не знаю", то это значит, что мы в очередной раз вернулись к тому, что ваш "оракул" — не оракул в общем случае и потому ничего не опровергает.
Вообще-то я пришёл сюда с близким вопросом: на основании чего сформулированы требования к оракулу?
Я вам ответил. Оракул должен определять, завершится ли выполнение алгоритма за конечное время. Всё. Сформулированы такие требования на основании описания задачи.
Вместо ответа я получил бессмысленный код, не реализующий никакого алгоритма.
Не "вместо", а "вместе" с ответом. И не "бессмысленный код, не реализующий никакого алгоритма", а код, демонстрирующий невозможность существования такого оракула. Любой код реализует какой-то алгоритм. А вопросы про "осмысленность" и "бессмысленность" алгоритмов — это к философам.
Возможны 4 варианта:
Нет. Код либо работает конечное время, либо бесконечное. Других вариантов нет. И оракул, если он существует, должен давать правильный ответ
почему из четырёх возможных действий выбрано только второе.
Покажите, пожалуйста, где именно кто-то кроме вас производит выбор из ваших 4 действий и где именно кто-то выбирает именно второе из них?
Но если вы будете вычислять значения O(W), то для правильной работы оракул должен знать: он внутри W или снаружи W.
Пусть знает. В моем примере выше оракул знает, в какой среде он запущен. Какое значение он вернет в месте своего вызова? Такое место одно. Оракул вызывается один раз и должен вернуть ровно одно значение. Какое?
а пока — так.
То есть, если отбросить философствования об истории математики, то мы снова возвращаемся к тому, что оракул в общем виде все таки существовать не может.
Для кого "нас"? Есть только один вызов оракула — изнутри функции f. Вот я и спрашиваю, какое значение он вернет. Конкретное значение. Без абстрактных "правильное", "строгое" и т.д.
Если вы передаете ей неправильные параметры, то и работать она будет неправильно.
Я из функции f спрашиваю у оракула, завершится ли функция f. Входных данных у этой функции нет. Он должен вернуть правильный ответ на мой вопрос. Какой ответ он вернет? Какие из моих параметров неправильны?
я придумываю оракул, который нельзя поломать при правильном использовании.
Нет "неправильного" использования. Вызов оракула должен давать ответ на вопрос, завершится ли переданный ему алгоритм. Всегда. Без исключений и оговорок. Кроме непосредственно алгоритма (в виде строки, если хотите) и его входных данных, доступа у оракула ни к чему нет. Ваш оракул не сможет определить, вызвали ли его "изнутри" или "извне".
дайте ему доступ к состояниям той машины, на которой его вычисляют
Пожалуйста. Вот состояние машины, на которой его запускают. Выполняется вот этот код.
Но правильным его можно будет назвать только для случая, когда когда он вызван снаружи относительно функции (т.е. с пустым контекстом).
Когда же он вызван внутри анализируемой функции… он может возвращать как и совпадающий, так и не совпадающий с правильным ответом результат
То есть он не будет корректным оракулом в общем случае. Ч.т.д.
Не говоря уже о том, что у вашего оракула может не быть возможности определить, "снаружи" он вызван или "изнутри".
Анализируемая функция может быть сконструирована так, что внутри нее ваш оракул будет вызван точно таким же образом, каким предусмотрен его вызов снаружи. С таким-же "контекстом", если хотите.
отвечать на вопрос «остановится ли этот алгоритм» для внешнего наблюдателя.
Ваш вариант отвечает не на этот вопрос. А на вопрос "«остановится ли этот алгоритм» при неправильном ответе на вопрос «остановится ли этот алгоритм» для внутреннего наблюдателя".
Почему? Если функция второго оракула должна быть невычислимой на машине Тьюринга, то вы только подтверждаете, что задача неразрешима. Если вычислима, то что мне мешает эту функцию реализовать?
Она не будет вычислять «остановится ли функция f» для пустого контекста (т.е. для математика)?
Повторюсь. Поведение функции f не зависит от контекста. Контекст не входит в Х. Поведение оракул-функции тоже не зависит от контекста. Для одних и тех-же данных она должна давать один и тот-же правильный ответ.
"Для математика" ответ будет правильным только в случае неправильного ответа во внутреннем вызове. А оракул-функция должна давать правильный ответ всегда.
Как я уже говорил, размазывание вычисления значения по нескольким функциям ничего не меняет. Эти несколько функций все равно можно вызвать из проверяемого кода и получить их противоречивый ответ. Как вы будете "скрывать будущее" от следующего кода? Вводом третьего кузена-оракула, который тоже сможет инвертировать значение первых двух братьев?
очевидно, что в Х еще входит и контекст вызова функции
В Х входят только входные данные проверяемой функции. Если функция как-то использует контекст своего вызова, то да, он входит в Х. В данном случае функция f работает абсолютно одинаково, независимо от того, в каком контексте она вызвана. Так что для нее контекст вызова в Х не входит. Значение функции-оракула по определению также не должно зависеть от контекста вызова. Оно зависит только от проверяемого алгоритма, его входных данных и ни от чего больше.
Понятно, что можно описать (да что там, даже реализовать) поведение halts так, чтобы в данном конкретном примере она возвращала что-то непротиворечивое (своей внутренней логике). Но это будет не функция-оракул, а что-то другое.
Кстати,
А если передавать контекст, то у вас она вернет 1 (т.е. halts(f,()) это 1 ), потому что изнутри f она вернет 0 (т.е. halts(f,(f)) это 0 ), и все будет корректно.
При этом у вас вызывающая оракула функция начинает выполнять бесконечный цикл, а у меня набоборот — прекращает.
Да. И еще в моем случае при этом возникает логическое противоречие, а в вашем — нет.
Ни то, ни другое не доказывает ни возможность, ни невозможность реализации оракула.
Ваш пример — да, ничего не доказывает. Мой доказывает невозможность существования (не реализации) оракула.
Оракул, работающий для общего случая, должен работать в том числе и для программы из моего примера. Но для программы из моего примера любой ответ любого оракула будет неверным.
Почитайте о том, как работает доказательство от противного.
Так мы и не создаем "оракула, который будет не правильно работать для некоторых алгоритмов". Мы описали алгоритм, для которого ни один оракул не сможет дать корректный ответ.
Оракул в примере — это функция halts, а не f. Мы ее не создаем, а просто предполагаем ее существование (в виде черного ящика). Если она существует, то она должна корректно работать в том числе и для функции f из моего примера. Но она не может корректно работать для функции f. Из этого следует, что наше исходное предположение о существовании такой функции halts — ложно. Эта функция (оракул) не может существовать.
Что для этого кода противоречий нет? Да, их нет (любой ответ оракула будет правильным и непротиворечивым). Для многих алгоритмов решение проблемы останова вообще тривиально, как, например для "print('Hello world')" или "while(true) {}" и еще многих других. Но возможность создания оракула, который будет правильно работать для некоторых алгоритмов никак не доказывает существование решения для общего случая.
Нет. Бессмысленный код позволяет написать не «выбранный язык программирования», а само предположение. Из чего и следует ложность этого предположения. Доказательством от обратного такой приём называется.
Потому что автор статьи смешал в кучу принцип работы функции, решающей проблему останова и доказательство невозможности существования такой функции.
Оракул и не должен зависать. Он должен говорить, останавливается ли программа, поданная ему на вход. Но если такой оракул существует, то становится возможным написать следующий код:
func f() {
if (halts(f)) {
while(true) {}
}
}
Такой код противоречит сам себе. Если оракул говорит, что функция f останавливается, то условие if (halts(f)) будет истинным, следовательно — управление перейдет к строке с бесконечным циклом и функция не завершится. Получили противоречие. Если оракул говорит, что функция не завершится, то условие if (halts(f)) будет ложным и функция завершится сразу. Снова противоречие. Таким образом, исходное предположение (о том, что существует оракул, определяющий, завершается ли произвольный алгоритм за конечное время) было ложным.
"Размазывание" вычисления значения функции останова по "братьям", "сестрам" и прочим родственникам ничем не поможет.
В вашем конкретном случае достаточно взять, например, две следующие программы, которые вообще игнорируют второго оракула и обращаются только к первому:
If (оракул(N)==0){
While(true){}
}
If (оракул(N)==1){
While(true){}
}
Независимо от того, что у этого оракула значит 1, а что значит 0, одна из программ будет противоречива. Если 0 — это остановка, а 1 — бесконечное выполнение, то противоречивой будет первая программа. Иначе — вторая.
Или же просто убрать это бессмысленное размазывание вот так:
If (оракул1(N) xor оракул2(N) == 1){
While(true){}
}
И получить ситуацию, полностью аналогичную ситуации с одним оракулом.
А если спас плохого человека с низким социальным рейтингом? А если сам человек не хотел, чтоб его спасали? А если уже после спасения этот человек станет условным Гитлером/Брейвиком/etc?
закончил школу на отлично
Объективность этого показателя вообще околонулевая. В 90% случаев для "закончить школу на отлично" есть необходимое условие "иметь хорошие отношения с учителями". А часто это условие даже достаточное.
Если будут объективные факторы, то почему бы и нет?
Если будут — то да, идея отличная. Но только этих объективных факторов столько не наберется. И если действительно ограничиваться только "объективными" факторами, то ситуация будет полностью аналогичной введению всяких KPI разными эффективными менеджерами. Когда по KPI производительность работа испытывает взрывной рост, а по факту разница в лучшем случае на уровне погрешности. Люди просто будут фармить себе рейтинг, например, сдавая кровь. Которая, к слову, как только превратится в "индульгенцию", уже перестанет быть дефицитом и будет никому не нужна.
Алгоритм работает либо конечное время, либо бесконечное. Третьего варианта быть не может. Если ваш "оракул" для каких-то случаев выдает третий вариант "не знаю", то это значит, что мы в очередной раз вернулись к тому, что ваш "оракул" — не оракул в общем случае и потому ничего не опровергает.
Я вам ответил. Оракул должен определять, завершится ли выполнение алгоритма за конечное время. Всё. Сформулированы такие требования на основании описания задачи.
Не "вместо", а "вместе" с ответом. И не "бессмысленный код, не реализующий никакого алгоритма", а код, демонстрирующий невозможность существования такого оракула. Любой код реализует какой-то алгоритм. А вопросы про "осмысленность" и "бессмысленность" алгоритмов — это к философам.
Нет. Код либо работает конечное время, либо бесконечное. Других вариантов нет. И оракул, если он существует, должен давать правильный ответ
Покажите, пожалуйста, где именно кто-то кроме вас производит выбор из ваших 4 действий и где именно кто-то выбирает именно второе из них?
Пусть знает. В моем примере выше оракул знает, в какой среде он запущен. Какое значение он вернет в месте своего вызова? Такое место одно. Оракул вызывается один раз и должен вернуть ровно одно значение. Какое?
То есть, если отбросить философствования об истории математики, то мы снова возвращаемся к тому, что оракул в общем виде все таки существовать не может.
Что? И в какие аксиомы?
Для кого "нас"? Есть только один вызов оракула — изнутри функции f. Вот я и спрашиваю, какое значение он вернет. Конкретное значение. Без абстрактных "правильное", "строгое" и т.д.
Я из функции f спрашиваю у оракула, завершится ли функция f. Входных данных у этой функции нет. Он должен вернуть правильный ответ на мой вопрос. Какой ответ он вернет? Какие из моих параметров неправильны?
Нет "неправильного" использования. Вызов оракула должен давать ответ на вопрос, завершится ли переданный ему алгоритм. Всегда. Без исключений и оговорок. Кроме непосредственно алгоритма (в виде строки, если хотите) и его входных данных, доступа у оракула ни к чему нет. Ваш оракул не сможет определить, вызвали ли его "изнутри" или "извне".
Пожалуйста. Вот состояние машины, на которой его запускают. Выполняется вот этот код.
Текущая инструкция обозначена с помощью >. Какой результат вернет ваш оракул в данном вызове?
И она с этой задачей в общем случае не справляется. By design. Справляется только с некоторыми оговорками, о чем вы сами написали в ветке чуть выше.
С оговорками и "func halts(f, X) {return true;}" — оракул.
То есть он не будет корректным оракулом в общем случае. Ч.т.д.
Не говоря уже о том, что у вашего оракула может не быть возможности определить, "снаружи" он вызван или "изнутри".
Анализируемая функция может быть сконструирована так, что внутри нее ваш оракул будет вызван точно таким же образом, каким предусмотрен его вызов снаружи. С таким-же "контекстом", если хотите.
Ваш вариант отвечает не на этот вопрос. А на вопрос "«остановится ли этот алгоритм» при неправильном ответе на вопрос «остановится ли этот алгоритм» для внутреннего наблюдателя".
Почему? Если функция второго оракула должна быть невычислимой на машине Тьюринга, то вы только подтверждаете, что задача неразрешима. Если вычислима, то что мне мешает эту функцию реализовать?
Повторюсь. Поведение функции f не зависит от контекста. Контекст не входит в Х. Поведение оракул-функции тоже не зависит от контекста. Для одних и тех-же данных она должна давать один и тот-же правильный ответ.
"Для математика" ответ будет правильным только в случае неправильного ответа во внутреннем вызове. А оракул-функция должна давать правильный ответ всегда.
Как я уже говорил, размазывание вычисления значения по нескольким функциям ничего не меняет. Эти несколько функций все равно можно вызвать из проверяемого кода и получить их противоречивый ответ. Как вы будете "скрывать будущее" от следующего кода? Вводом третьего кузена-оракула, который тоже сможет инвертировать значение первых двух братьев?
В Х входят только входные данные проверяемой функции. Если функция как-то использует контекст своего вызова, то да, он входит в Х. В данном случае функция f работает абсолютно одинаково, независимо от того, в каком контексте она вызвана. Так что для нее контекст вызова в Х не входит. Значение функции-оракула по определению также не должно зависеть от контекста вызова. Оно зависит только от проверяемого алгоритма, его входных данных и ни от чего больше.
Понятно, что можно описать (да что там, даже реализовать) поведение halts так, чтобы в данном конкретном примере она возвращала что-то непротиворечивое (своей внутренней логике). Но это будет не функция-оракул, а что-то другое.
Кстати,
А почему не наоборот?
Да. И еще в моем случае при этом возникает логическое противоречие, а в вашем — нет.
Ваш пример — да, ничего не доказывает. Мой доказывает невозможность существования (не реализации) оракула.
Оракул, работающий для общего случая, должен работать в том числе и для программы из моего примера. Но для программы из моего примера любой ответ любого оракула будет неверным.
Почитайте о том, как работает доказательство от противного.
Так мы и не создаем "оракула, который будет не правильно работать для некоторых алгоритмов". Мы описали алгоритм, для которого ни один оракул не сможет дать корректный ответ.
Оракул в примере — это функция halts, а не f. Мы ее не создаем, а просто предполагаем ее существование (в виде черного ящика). Если она существует, то она должна корректно работать в том числе и для функции f из моего примера. Но она не может корректно работать для функции f. Из этого следует, что наше исходное предположение о существовании такой функции halts — ложно. Эта функция (оракул) не может существовать.
И? Что вы этим хотели сказать?
Что для этого кода противоречий нет? Да, их нет (любой ответ оракула будет правильным и непротиворечивым). Для многих алгоритмов решение проблемы останова вообще тривиально, как, например для "print('Hello world')" или "while(true) {}" и еще многих других. Но возможность создания оракула, который будет правильно работать для некоторых алгоритмов никак не доказывает существование решения для общего случая.
Нет. Бессмысленный код позволяет написать не «выбранный язык программирования», а само предположение. Из чего и следует ложность этого предположения. Доказательством от обратного такой приём называется.
Потому что автор статьи смешал в кучу принцип работы функции, решающей проблему останова и доказательство невозможности существования такой функции.
Оракул и не должен зависать. Он должен говорить, останавливается ли программа, поданная ему на вход. Но если такой оракул существует, то становится возможным написать следующий код:
Такой код противоречит сам себе. Если оракул говорит, что функция f останавливается, то условие if (halts(f)) будет истинным, следовательно — управление перейдет к строке с бесконечным циклом и функция не завершится. Получили противоречие. Если оракул говорит, что функция не завершится, то условие if (halts(f)) будет ложным и функция завершится сразу. Снова противоречие. Таким образом, исходное предположение (о том, что существует оракул, определяющий, завершается ли произвольный алгоритм за конечное время) было ложным.
"Размазывание" вычисления значения функции останова по "братьям", "сестрам" и прочим родственникам ничем не поможет.
В вашем конкретном случае достаточно взять, например, две следующие программы, которые вообще игнорируют второго оракула и обращаются только к первому:
Независимо от того, что у этого оракула значит 1, а что значит 0, одна из программ будет противоречива. Если 0 — это остановка, а 1 — бесконечное выполнение, то противоречивой будет первая программа. Иначе — вторая.
Или же просто убрать это бессмысленное размазывание вот так:
И получить ситуацию, полностью аналогичную ситуации с одним оракулом.
А если спас плохого человека с низким социальным рейтингом? А если сам человек не хотел, чтоб его спасали? А если уже после спасения этот человек станет условным Гитлером/Брейвиком/etc?
Объективность этого показателя вообще околонулевая. В 90% случаев для "закончить школу на отлично" есть необходимое условие "иметь хорошие отношения с учителями". А часто это условие даже достаточное.
Если будут — то да, идея отличная. Но только этих объективных факторов столько не наберется. И если действительно ограничиваться только "объективными" факторами, то ситуация будет полностью аналогичной введению всяких KPI разными эффективными менеджерами. Когда по KPI производительность работа испытывает взрывной рост, а по факту разница в лучшем случае на уровне погрешности. Люди просто будут фармить себе рейтинг, например, сдавая кровь. Которая, к слову, как только превратится в "индульгенцию", уже перестанет быть дефицитом и будет никому не нужна.