Comments 178
Даже если посмотреть на предолженных вами оракулов, мы можем сконструировать вычислимую функцию, которая будет аналогичной той, что рассматривал Тьюринг в своей работе, и мы все еще получим противоречие.
"Размазывание" вычисления значения функции останова по "братьям", "сестрам" и прочим родственникам ничем не поможет.
В вашем конкретном случае достаточно взять, например, две следующие программы, которые вообще игнорируют второго оракула и обращаются только к первому:
If (оракул(N)==0){
While(true){}
}If (оракул(N)==1){
While(true){}
}Независимо от того, что у этого оракула значит 1, а что значит 0, одна из программ будет противоречива. Если 0 — это остановка, а 1 — бесконечное выполнение, то противоречивой будет первая программа. Иначе — вторая.
Или же просто убрать это бессмысленное размазывание вот так:
If (оракул1(N) xor оракул2(N) == 1){
While(true){}
}И получить ситуацию, полностью аналогичную ситуации с одним оракулом.
Три ограничения нужны не для того, чтобы найти или потерять оракула.
Это просто теорема Гёделя о неполноте в приложении к вычислительной технике.
Чтобы не борзели от всемогущества.
Потому что автор статьи смешал в кучу принцип работы функции, решающей проблему останова и доказательство невозможности существования такой функции.
Оракул и не должен зависать. Он должен говорить, останавливается ли программа, поданная ему на вход. Но если такой оракул существует, то становится возможным написать следующий код:
func f() {
if (halts(f)) {
while(true) {}
}
}Такой код противоречит сам себе. Если оракул говорит, что функция f останавливается, то условие if (halts(f)) будет истинным, следовательно — управление перейдет к строке с бесконечным циклом и функция не завершится. Получили противоречие. Если оракул говорит, что функция не завершится, то условие if (halts(f)) будет ложным и функция завершится сразу. Снова противоречие. Таким образом, исходное предположение (о том, что существует оракул, определяющий, завершается ли произвольный алгоритм за конечное время) было ложным.
Нет. Бессмысленный код позволяет написать не «выбранный язык программирования», а само предположение. Из чего и следует ложность этого предположения. Доказательством от обратного такой приём называется.
func f() {
while(true) {
if (halts(f)) {
return 'Завершится.'
}
}
}
?
И? Что вы этим хотели сказать?
Что для этого кода противоречий нет? Да, их нет (любой ответ оракула будет правильным и непротиворечивым). Для многих алгоритмов решение проблемы останова вообще тривиально, как, например для "print('Hello world')" или "while(true) {}" и еще многих других. Но возможность создания оракула, который будет правильно работать для некоторых алгоритмов никак не доказывает существование решения для общего случая.
Так мы и не создаем "оракула, который будет не правильно работать для некоторых алгоритмов". Мы описали алгоритм, для которого ни один оракул не сможет дать корректный ответ.
Оракул в примере — это функция halts, а не f. Мы ее не создаем, а просто предполагаем ее существование (в виде черного ящика). Если она существует, то она должна корректно работать в том числе и для функции f из моего примера. Но она не может корректно работать для функции f. Из этого следует, что наше исходное предположение о существовании такой функции halts — ложно. Эта функция (оракул) не может существовать.
Оракул в примере — это функция halts, а не f.
Правильно. При этом и вас, и у меня она абсолютно одинаково говорит, остановится программа или нет.
При этом у вас вызывающая оракула функция начинает выполнять бесконечный цикл, а у меня набоборот — прекращает. Ни то, ни другое не доказывает ни возможность, ни невозможность реализации оракула.
она абсолютно одинаково говорит, остановится программа или нет
Уточните, пожалуйста, в примере Dim0v выше halts(f) должен вернуть true или false? Представьте себе абсолютно правильный оракул. Какой ответ на ваш взгляд он должен выдать, если у него спросить про f?
А что должен вернуть оракул? Ну давайте так — самозванцев нам не надо, ораклом буду я. Пусть я получил код и данные. Возможны 4 варианта:
1. Я смотрю и ничего не понимаю — язык не знакомый. Я возвращаю «не понимаю» и перехожу к другим делам.
2. Язык знакомый, я вижу, что выполнение программы никогда не закончится. Я так честно и говорю: «нет». И перехожу к другим делам.
3. Вижу, что закончится —> «да». И перехожу к другим делам.
4. Вижу противоречие. За это, как за шуллерство — канделябрами. И перехожу к другим делам.
Я хотел узнать, почему из четырёх возможных действий выбрано только второе. Я не собираюсь опровергать теорему. Я и без математики знаю, что природа не алгоритмична.
Вообще-то я пришёл сюда с близким вопросом: на основании чего сформулированы требования к оракулу?
Я вам ответил. Оракул должен определять, завершится ли выполнение алгоритма за конечное время. Всё. Сформулированы такие требования на основании описания задачи.
Вместо ответа я получил бессмысленный код, не реализующий никакого алгоритма.
Не "вместо", а "вместе" с ответом. И не "бессмысленный код, не реализующий никакого алгоритма", а код, демонстрирующий невозможность существования такого оракула. Любой код реализует какой-то алгоритм. А вопросы про "осмысленность" и "бессмысленность" алгоритмов — это к философам.
Возможны 4 варианта:
Нет. Код либо работает конечное время, либо бесконечное. Других вариантов нет. И оракул, если он существует, должен давать правильный ответ
почему из четырёх возможных действий выбрано только второе.
Покажите, пожалуйста, где именно кто-то кроме вас производит выбор из ваших 4 действий и где именно кто-то выбирает именно второе из них?
Да никто не выбрал второе. Наоборот, второй ответ не подходит. Потому что если оракул ответит нет, то программа из-за этого завершится. И независимый свидетель скажет — ваш оракул ошибся, видите? Он сказал "нет, не завершится", а программа завершилась.
А считать, что машина Тьюринга "мошенничает", это как-то странно.
Судя по вашему ответу, вы считаете, что оракул должен выдавать один из трёх ответов (вариант "это не код" отметаем, он не интересен).
- Да, завершится.
- Нет, не завершится.
- Мошеннический код, ответ не возможен.
Так вот, теорема о том, возможен ли оракул с двумя видами ответов? "Завершится/не завершится". Ведь логика подсказывает, что даже "мошеннический" код либо завершится когда-нибудь, либо не завершится никогда, не так ли? Разве может быть третий вариант?
Но вы и сами видите — нет, такой оракул невозможен. Возможен только оракул с тремя вариантами ответов. Да, нет, "идите отсюда". А с двумя — невозможен. Это не хорошо, не плохо, просто так есть.
язык программирования позволяет написать бессмысленный код?
Язык знакомый
язык не знакомый
Что вы к языку привязались то? Задача не про языки, а про алгоритмы.
Тьюринг-полный там язык, который позволяет написать любую ахинею в рамках доступной архитектуры. Asm, brainfuck, basic, хоть js, суть задачи от этого не меняется.
А суть приводимых вам алгоритмов в том, что для доказательства невозможности написать алгоритм разбирающий любую программу, достаточно привести хотябы один пример программы, для которой написание такого алгоритма невозможно.
func f() {
if (halts(f)) {
while(true) {}
}
}Может быть господин минусёр просветит меня — какой алгоритм реализует код, который даже откомпилировать нельзя (функция halts не определена)?
Так ведь этот код пишется исходя из предположения, что функция halts уже реализована. И возникшее противоречие говорит нам о том, что предположение о существовании halts было неверным.
(минусовал не я, просто решил ответить)
Реализация алгоритма в коде всегда конкретна. На конкретном языке, для конкретной операционной системы, процессора, … Теория алгоритмов этим всем не интересуется.
Короче, эти ускоренные/упрощённые методы доказательства годятся только для запудривания мозгов пятиклассницам.
или не возможна эта конкретная реализация
Какая конкретная реализация? Ее где-то видите только вы. Никто ее в этой ветке не рассматривал.
доказывается несуществование алгоритма совсем по-другому — непосредственно для алгоритма, без каких-либо попыток реализации в коде.
Да. Именно поэтому никто из приводящих классическое доказательство этой проблемы от противного и не рассматривал никакие конкретные реализации функции оракула в коде. Я даже больше скажу. Алгоритмы оракула тоже не рассматривались. Рассматривалась только возможность или невозможность существования такого алгоритма.
Какие-то детали реализации здесь рассматривали только люди, не согласные по каким-то причинам с доказательством Тьюринга. То вводили какие-то контексты (все равно не помогающие вернуть правильный ответ), то требовали чтобы основная функция была реализована с помощью двух независимых вспомогательных функций (что тоже ничем не помогало в решении поставленной проблемы), то еще что-то.
Но это не значит, что не существует алгоритм, который она вроде бы реализует.
В том то и дело, что значит. Потому что см. предыдущие 2 пункта.
эти ускоренные/упрощённые методы доказательства годятся только для запудривания мозгов пятиклассницам.
Вот как.
Если один из самых распространенных видов математического доказательства для вас "упрощенный метод для запудривания мозгов пятиклассницам", то не могли бы вы привести хотя бы один конкретный пример доказательства, которое, на ваш взгляд, не "упрощенное" и годится не только для пятиклассниц? В идеале, конечно, какое-то математическое доказательство, но вообще подойдет доказательство чего угодно. Вот просто любопытно, что вы приведете.
Я тоже вас не минусовал. Минусовать (как и плюсовать, впрочем) никого мне карма не позволяет.
Какая конкретная реализация? Ее где-то видите только вы.
Вы лжёте. Это именно вы здесь написали, что любая фунуция реализует алгоритм.
…один из самых распространенных видов математического доказательства…
Этот «один из самых распространенных видов математического доказательства» не предполагает нарушение закона тождества. Вы предполагаете существование функции, а вывод делаете об алгоритме. Подмена понятия.
Да, функция не существует, вы это доказали, спасибо. Алгоритм тоже не существует, но доказали это не вы и совсем по-другому.
Вы лжёте. Это именно вы здесь написали, что любая фунуция реализует алгоритм.
У вас какая-то каша в голове, честное слово. Я написал
Любой код реализует какой-то алгоритм
Да, это так. Любой компилируемый код и любой псевдокод, каким бы бессмысленным он кому-то не казался, реализует какой-то алгоритм (каким бы бессмысленным он тоже не казался).
Где в этих словах конкретная реализация алгоритма оракула (функции halts)?
Вы предполагаете существование функции, а вывод делаете об алгоритме. Подмена понятия.
Какой смысл вы вкладываете в слово "функция"?
Любой алгоритм предполагает наличие набора (возможно пустого) входных, выходных данных и набора неких операций, определяющих поведение алгоритма (получение выходных данных из входных).
Для функции halts предполагается наличие ровно этих вещей и никаких других.
Да, функция не существует, вы это доказали, спасибо
Не я, а Тьюринг. Я лишь привел его доказательство. Не за что.
Алгоритм тоже не существует, но доказали это не вы
Да, не я. Тьюринг. А чем алгоритм halts отличается от функции halts — одному вам известно.
и совсем по-другому.
Да нет, точно так же, как и я. Только он еще строго формализовал понятие алгоритма, придумав для этого машину Тьюринга. Но на высоком уровне доказательство — ровно такое же доказательство от противного, как и у меня.
Алгори́тм (лат. algorithmi — от арабского имени математика Аль-Хорезми[1]) — конечная совокупность точно заданных правил решения произвольного класса задач или набор инструкций, описывающих порядок действий исполнителя для решения некоторой задачи.
Компилируемость не является определяющим свойством алгоритма.
Конкретный код реализует алгоритм выполнения функцией бесконечного цикла, для некоего «оракула» который определит данную функцию как выполняемую за конечный промежуток времени.
Алгоритм != программа != псевдокод.
Пресловутое 'нанести->смыть->повторить' на шампунях тоже алгоритм, хотя не одно из действий не прописано в существующих языках программирования.
При этом у вас вызывающая оракула функция начинает выполнять бесконечный цикл, а у меня набоборот — прекращает.
Да. И еще в моем случае при этом возникает логическое противоречие, а в вашем — нет.
Ни то, ни другое не доказывает ни возможность, ни невозможность реализации оракула.
Ваш пример — да, ничего не доказывает. Мой доказывает невозможность существования (не реализации) оракула.
Оракул, работающий для общего случая, должен работать в том числе и для программы из моего примера. Но для программы из моего примера любой ответ любого оракула будет неверным.
Почитайте о том, как работает доказательство от противного.
Это не возможность создания оракула. Это возможность создания программы, для которой любой оракул будет работать неправильно.
Представьте себе человека, который делает оракула. А второй проверяет, работает ли оракул. Так вот, второй всегда сможет написать такую программу, что бы оракул первого выдал неверный результат. То есть первый никогда не сможет сделать достаточно хорошего оракула.
Именно это и называется "не существует решения для общего случая".
Бессмысленный для вас? Я бы хотел посмотреть на Тьюринг-полный язык, который НЕ позволил бы написать бессмысленный код.
Это особенность всех доказательств (и в математике тоже) — они рассматривают не "смысл", а целостность. В данном случае рассматривается, существует или не существует такая "бессмысленная" программа. Она существует, из нее следует, что оракул невозможен.
halts(f) то это не то же самое, что вы вызовете f() который внутри себя вызовет halts(f).
А если передавать контекст, то у вас она вернет 1 (т.е. halts(f,()) это 1 ), потому что изнутри f она вернет 0 (т.е. halts(f,(f)) это 0 ), и все будет корректно.
очевидно, что в Х еще входит и контекст вызова функции
В Х входят только входные данные проверяемой функции. Если функция как-то использует контекст своего вызова, то да, он входит в Х. В данном случае функция f работает абсолютно одинаково, независимо от того, в каком контексте она вызвана. Так что для нее контекст вызова в Х не входит. Значение функции-оракула по определению также не должно зависеть от контекста вызова. Оно зависит только от проверяемого алгоритма, его входных данных и ни от чего больше.
Понятно, что можно описать (да что там, даже реализовать) поведение halts так, чтобы в данном конкретном примере она возвращала что-то непротиворечивое (своей внутренней логике). Но это будет не функция-оракул, а что-то другое.
Кстати,
А если передавать контекст, то у вас она вернет 1 (т.е. halts(f,()) это 1 ), потому что изнутри f она вернет 0 (т.е. halts(f,(f)) это 0 ), и все будет корректно.
А почему не наоборот?
Но это будет не функция-оракул, а что-то другое.
в смысле не оракул-функция? Она не будет вычислять «остановится ли функция f» для пустого контекста (т.е. для математика)?
А почему не наоборот?
потому что эта функция зациклится же.
можно и наоборот (0 снаружи, 1 внутри) — заметьте, от этого истинность результата не поменяется.
Она не будет вычислять «остановится ли функция f» для пустого контекста (т.е. для математика)?
Повторюсь. Поведение функции f не зависит от контекста. Контекст не входит в Х. Поведение оракул-функции тоже не зависит от контекста. Для одних и тех-же данных она должна давать один и тот-же правильный ответ.
"Для математика" ответ будет правильным только в случае неправильного ответа во внутреннем вызове. А оракул-функция должна давать правильный ответ всегда.
Поведение оракул-функции тоже не зависит от контекста. Для одних и тех-же данных она должна давать один и тот-же правильный ответ.Мой строгий оракул для одного и того же контекста будет выдавать один и тот же ответ.
Но правильным его можно будет назвать только для случая, когда когда он вызван снаружи относительно функции (т.е. с пустым контекстом).
Когда же он вызван внутри анализируемой функции, он не будет ни правильным, ни неправильным — он может возвращать как и совпадающий, так и не совпадающий с правильным ответом результат (потому что он будет не ответом, а частью решения, и т.о. нацеленным на правильность ответа).
Но правильным его можно будет назвать только для случая, когда когда он вызван снаружи относительно функции (т.е. с пустым контекстом).
Когда же он вызван внутри анализируемой функции… он может возвращать как и совпадающий, так и не совпадающий с правильным ответом результат
То есть он не будет корректным оракулом в общем случае. Ч.т.д.
Не говоря уже о том, что у вашего оракула может не быть возможности определить, "снаружи" он вызван или "изнутри".
Анализируемая функция может быть сконструирована так, что внутри нее ваш оракул будет вызван точно таким же образом, каким предусмотрен его вызов снаружи. С таким-же "контекстом", если хотите.
В принципе, можно не требовать «передавать контекст» внутрь оракула явно, просто дайте ему доступ к состояниям той машины, на которой его вычисляют — он сможет тогда получить доступ к контексту сам.
я придумываю оракул, который нельзя поломать при правильном использовании.
Нет "неправильного" использования. Вызов оракула должен давать ответ на вопрос, завершится ли переданный ему алгоритм. Всегда. Без исключений и оговорок. Кроме непосредственно алгоритма (в виде строки, если хотите) и его входных данных, доступа у оракула ни к чему нет. Ваш оракул не сможет определить, вызвали ли его "изнутри" или "извне".
дайте ему доступ к состояниям той машины, на которой его вычисляют
Пожалуйста. Вот состояние машины, на которой его запускают. Выполняется вот этот код.
f();
func f() {
> if (halts(f)) {
while(true) {}
}
}Текущая инструкция обозначена с помощью >. Какой результат вернет ваш оракул в данном вызове?
Нет «неправильного» использования.
Среда выполнения алгоритма тоже является частью алгоритма. Для примера: вы можете сделать функцию W, которая будет эмулировать машину тьюринга и на ней запустить оракула O, который будет смотреть на f(), в которой будет вызываться O и т.д. ad infinitum. Но если вы будете вычислять значения O(W), то для правильной работы оракул должен знать: он внутри W или снаружи W.
Когда-то в математике нельзя было записать длину диагонали квадрата. Или такое число, чтобы оно давало отрицательные числа при умножении самого на себя, так что когда-то это были такие функции «с оговорками». А теперь все пишут квадратные корни, числа пи, мнимые единицы и прочая и прочая.
Может, если добавить что-то в аксиомы, и будет оракул «в общем виде», а пока — так.
Но если вы будете вычислять значения O(W), то для правильной работы оракул должен знать: он внутри W или снаружи W.
Пусть знает. В моем примере выше оракул знает, в какой среде он запущен. Какое значение он вернет в месте своего вызова? Такое место одно. Оракул вызывается один раз и должен вернуть ровно одно значение. Какое?
а пока — так.
То есть, если отбросить философствования об истории математики, то мы снова возвращаемся к тому, что оракул в общем виде все таки существовать не может.
Может, если добавить что-то в аксиомы
Что? И в какие аксиомы?
для оракула О(f, ctx) у вас неправильный пример.
Должен быть
if (O(f, ctx)) {
где в данном случае ctx = (f, 0), и при таких значениях своих входных параметров он вернет 0.
UPD: в те аксиомы, на основании которых у вас вычисления происходят. Есть же аксиомы стереометрии, аксиоматика теории множеств или вещественных чисел и т.д.
А вот знал бы что (в короткой форме, без выводимых из других аксиом частей) — то писал бы не на хабр.
у вас неправильный пример.
Должен быть
if (O(f, ctx)) {
Ок.
f();
func f() {
ctx = (f, 0)
if (O(f, ctx)) {
while (true) {}
}
}Здесь ваш оракул вернет 0? В таком случае его ответ неверный. Выполнение функции завершится. Вернет 1? Ответ тоже неверный. Выполнение функции не завершится.
O(f, ctx) = 1 при 0 при ctx = (f, 0)
два верных результата, плюс функция f счастливо завершается.
O(f, ctx) = 1 при 0 при ctx = (f, 0)
О! У нас именно этот случай. Повезло!
Так, значение 1. Значит функция f завершается. Проверим:
if (O(f, ctx)) {
while (true) {}
}ой. Мы попали внутрь ифа и в бесконечный цикл. Ответ вашего оракула оказался неправильным :(
два верных результата
Откуда два? В коде только один вызов O. Да и тот вернул неправильный ответ.
O(f, ctx) = 1 при ctx = () и
O(f, ctx) = 0 при ctx = (f, 0)
и т.д.
если вы хотите в символьных выражениях, тогда можно в частном случае развернуть в такой код:
if (O(f, (f, 0))) {
while (true) {}
}
То есть ответ 0? Ок, не беда. Перепроверим.
Так. 0 значит, что функция f не завершается. Проверим:
if (O(f, (f, 0))) {
while (true) {}
}ой. Мы не попали внутрь ифа и функция завершилась. Ответ вашего оракула оказался неправильным :(
Если вы вызывали O(f, (f, 0)), то он вернет правильный, но непригодный для вас ответ.
Оракул вызывается ровно в одном месте один раз. Нет никаких вызовов "для нас" и "не для нас".
И в этом одном единственном месте своего вызова ответ оракула был неправильным. Ваш оракул не работает.
я не запрещаю называть вам белое синим, а шляпу — женой (и наоборот).
Но мне все-таки любопытно: почему вы решили, что он не работает?
(и чтобы не отвечать вопросом на вопрос, а то это все-таки дурной тон).
Я перечислил варианты результатов функции от входных параметров. Оба — валидные, но каждый — на смоем месте вызова. Уверен, что вы не ошиблись с передачей параметров и получили корректный ответ.
Покажите как надо. Что сюда вписать и какой результат вернет оракул?
f();
func f() {
if (O(f, /*здесь может быть ваша реклама*/)) {
while (true) {}
}
}PS: Возможно, это и есть та новая аксиома, которой не хватает для непротиворечивых оракулов… надо думать.
просто передайте ему ctx.
Ок. Не спрашиваю, какое значение должно храниться в ctx. Допустим, правильное.
Передал ctx. Какое значение вернул оракул?
А если вы все параметры внутри предавали правильно, то и оракул от функции+пустой ctx вернет свой вердикт — зациклится она или нет.
А если вы все параметры внутри предавали правильно,
Во-первых, оракул должен правильно работать для всех функций. В том числе и тех, которые вызывают его с "неправильными" параметрами. Во-вторых — какое бы значение он тут не вернул — правильным оно быть не может, потому что поведение функции будет противоречить тому, что вернул оракул.
Сделайте функцию, которая будет работать от положительных чисел, я вам туда передам отрицательное и все вместе будем ходить вокруг да около: «правильная или неправильная» и т.д.
В примере
f();
func f() {
if (O(f, /*здесь может быть ваша реклама*/)) {
while (true) {}
}
}
Функция не принимает никаких параметров на вход. Следовательно O(f) — константа для неизменной среды.
Но если O(f) = 1, то функция зависающая O(f) =0,
А если O(f) = 0, то функция завершает своё выполнение O(f) = 1.
Никаких начальных, конечных, промежуточных и т.п. данных нет.
Оракул можно воспринимать как парсер, например. Который должен по коду ( не запуская функцию ) вернуть результат 0 либо 1.
И в данном случае и возникает противоречие.
Потому что он только что дал неправильный ответ. Не "правильный, но непригодный", а именно неправильный. Оракула вызвали один раз. Спросили об одной функции. Его ответ не совпал с фактическим поведением этой функции.
Или вам больше нравится более мягкая характеристика "Работает. Иногда правильно, но не всегда"? Ок, можно и так сказать)
если вызвать оракул извне, то оракул получит другие значения на вход и вернет другой (а возможно и такой же) результат.
Сейчас же ваш аргумент сводится к простому «скажите оракулу сами, останавливаетесь вы или нет».
Теперь вам не нравится что конкретные значения — конкретные… Тогда передавайте контекст и будет вам общий случай.
это функция, которая возвращает (функция, в которой был вызван оракул + параметры фунцкции + место в функции из которого вызван оракул + значения внутренние переменные к даному времени + итерация вызова если в цикле), вот как-то так.
Ок, давайте по порядку.
функция, в которой был вызван оракул
f
параметры фунцкции
()
место в функции из которого вызван оракул
вторая строка. Внутри оператора проверки условия.
значения внутренние переменные к даному времени
внутренних переменных нет
итерация вызова если в цикле
не в цикле.
Ничего из этого не меняется, потому что вызов один.
И любой ответ оракула на этот вызов будет неправильным.
я возвращаю 0. конец.
И функция завершается. Значит ваш 0 был неправильным ответом.
Он не тот же самый, что для пустого контекста — это да.
f();
func f() {
if (O(f, ())) {
while (true) {}
}
}
Этот код зависнет при выполнении или нет?
Мы вызвали f с пустым контекстом.
Если код зависает, значит оракул сказал что f с пустым контекстом не зависнет = соврал.
Если код не зависает, значит оракул сказал что f с пустым контекстом зависнет = опять соврал.
В чём проблема-то? Откуда у вас там наблюдатели и контексты? Это программирование, а не квантовая физика, в конце концов. Тут есть два варианта 0 либо 1.
А у вас оракул пытается маскироваться под квант, и возвращать разное значение в зависимости от того смотрю я на него или нет.
Просто подумайте, зависнет ли тупо запущенный кусок кода и почему.
нет никаких маскировок, одно только соглашение про побочные эффекты (передача внутрь состояния).
Соглашение очень простое — состояние должно передаваться корректно.
Вот вам простая аналогия из императивного программирования: проход по циклу. Т.е. у меня простой цикл
for (i = 0; i <= N; i++) { foo(i);}
чтобы продемонстрировать корректность работы, я беру элементарный пример в котором N=0, и тогда можно подставить конкретное i=0, что будет выглядеть как
{ foo(0); }
и все работает ОК.
Я понимаю, что можно написать { foo(-1); }. Можно.
Но это уже не будет корректным преобразованием для
for (i = 0; i <= N; i++) { foo(i);}
не так ли?
Если вы вставите внутрь своей функции некорректный вызов моей функции — то это не опровергает и не доказывает ничего (нк, кроме того что мы друг друга так и не поняли ...)
f(x) = x +*-xх
«Все значки правильные? да, правильные. Так найдите производную! Что, не получается? Значит у вас противоречие!»
и так по кругу… эх!
Лучше буду тратить свое время на комментарий ibessonov про диагонализацию и стеки — так оно гораздо более продуктивно будет использоваться…
Программа либо может выполниться за конечное время либо не может. Нет никакого третьего состояния. Если программа сразу падает с ошибкой — она выполняется за конечное время. Если в программе цикл без проверок и выходов — она зависает. Если в коде jmp start; без условий то код зависнет.
Программа абсолютно валидна с точки зрения логики и синтаксиса.
В чём проблема определить завершится она или нет? Какие, к чёрту, производные?
f(x) = x +*-xх
а может найдете логарифм от -1 в вещественных числах? А как насчет последнего цифры в десятичной записи числа пи?
Соревноваться в «кто задаст больше некорректных вопросов» — извините, без меня.
Программа, которую вы написали — невалидна с точки зрения постановки задачи, ее результат ничего не доказывает и не опровергает.
В 1936 году Алан Тьюринг доказал, что нет общего алгоритма, анализирующего другие алгоритмы и указывающий, будет зависать программа или нет.
Чем она, блин, не валидна? Она не является алгоритмом?
То что можно построить оракул который разбирает некоторые типы алгоритмов, никак не доказывает возможность построения оракула для всех алгоритмов и, в принципе, к исходной задаче никакого отношения не имеет.
С таким подходом можно элементарно показать что существует оракул определяющий выполнимость любой задачи длинной не более одной команды. И что? Толку от такого оракула?
Давайте назовём алгоритм приведённый в доказательстве Тьюринга, невалидным и разведём балаболию на 140 комментариев. Нет в условии задачи никакого понятия 'валидности'. Алгоритма анализирующиего другие алгоритмы не существует, а ваш пример не подходит под характеристики, т.к. из множества всех алгоритмов он требует исключить подмножество 'невалидных' характеристики и размер которых не известен. К чему весь трёп?
Я предлагал либо дать доступ к контексту, либо вот — явно передавать контекст внутрь.
Я тоже не брезгливый, мне все равно — передают внутрь функций верные или неверные значения.
Просто я удивляюсь тому, что кто-то передает на вход мусор и удивляется, что на выходе — тоже мусор…
вычисляется ли оракул рекурсивно или нет.
Что и как вы в вашем оракуле вычисляете — это детали реализации. Хотите — вызывайте себя рекурсивно, если встретили в тексте вызов себя. Хотите, вычисляйте как-то еще. Хотите — не вычисляйте вообще. Только в место вызова ответ правильный верните. Ваш оракул (и никакой другой, к слову) этого не делает.
Просто я удивляюсь тому, что кто-то передает на вход мусор и удивляется, что на выходе — тоже мусор…
Где и какой мусор передавали на вход вашему оракулу и как нужно было передавать правильно?
если вы хотите вызвать его внутри f
Я его вызвал внутри f. Передал те параметры, что вы сказали (f, 0). Он вернул ответ, который вы сказали. Этот ответ неправильный, функция повела себя по другому.
Внутри функции f — не ваш оракул. Там текст, полностью совпадающий с текстом вашего оракула. Если вам так проще, то скажу, что это не тот же самый объект, а другой. И этот объект должен по тексту решать — завершится программа или нет.
То есть вы должны не эту прогу починить, а оракул. Что бы он для любой проги смог дать ответ. Но к сожалению, невозможно. Любой оракул будет иногда ошибаться. Для общего случая он невозможен.
Текст оракула, не текст оракула, моя функция или нет — если в нее передавать заданные параметры, то она вычисляет правильный ответ.
если в нее передавать заданные параметры, то она вычисляет правильный ответ.
Увы, не вычисляет(
habr.com/ru/post/436090/#comment_19622020
PS: извините, что передразниваю, но реально — по существу есть возражения?
Что значит, передать контекст? Вы имеете ввиду, что у функции должно быть два параметра? Или она должна обращаться к глобальным переменным? Ради чего? Задача не в том, что бы написать корректную функцию. Наоборот, задача в том, что бы написать НЕ корректную (но без ошибок), что бы оракул дал неверный ответ.
Зачем? Что бы показать, что оракул сломан. И никто не сможет сделать работоспособный оракул, такой, что бы для любой программы смог дать ответ. Всегда можно написать программу такую, что оракул ошибётся.
То есть рабочий оракул невозможен. Об этом и теорема.
Если ваша задача доказать, что «никто не сможет сделать работоспособный оракул, такой, что бы для любой программы смог дать ответ», то пока что с этим есть небольшая заминка.
Что значит, передать контекст? Вы имеете ввиду, что у функции должно быть два параметра? Или она должна обращаться к глобальным переменным? Ради чего?а вот это уже хорошие вопросы.
1) передать значения, по которым оракул мог бы определить — вызван ли он из анализируемой функции и из какого места (+ с какими параметрами).
2) не у функции, а у оракула — да, два параметра
3) глобальные переменные или нет — это уже детали реализации.
4) Для того чтобы дать правильный ответ — зациклится ли некая функция f или нет.
передать значения, по которым оракул мог бы определить — вызван ли он из анализируемой функции и из какого места (+ с какими параметрами).
…
глобальные переменные или нет — это уже детали реализации.
Замечательно. Опустим все детали реализации. Считаем, что у оракула halts есть возможность узнать все, о чем вам хочется. Какой ответ он выдаст?
f();
func f() {
if (halts(f)) {
while(true) {}
}
}Извиняюсь, что вклиниваюсь в дискуссию, но всё-же внесу дополнение:
func f(g) {
if (halts(g, g)) {
while(true) {}
}
}
f(f); //?Всё-таки существование такой f, которая внутри ссылается на саму себя, совсем не очевидно.
В классическом доказательстве предполагается существование функции `halts(f, input)`, возвращающей 1, если `f` останавливается на входе `input` и 0 в противном случае. Какие параметры стоит добавить?
1) передать значения, по которым оракул мог бы определить — вызван ли он из анализируемой функции и из какого места (+ с какими параметрами).
Мне действительно интересно, что это конкретно за значения и каким образом "оракул" будет валидировать, что они переданы правильно.
P.S. давайте не будем тут больше употреблять термин "оракул", он к делу ну вообще не относится.
Тот кто ему передает правильные параметры — тот получит правильные результаты.
ОК. оракул выкидываем. «Ффункция» (чтобы не путать с О-нотацией), подходит?
Какого рода параметры ей надо добавить? Давайте как-то зафиксируем, что они собой представляют, иначе предметного разговора не выйдет. Вы будете понимать под ними одно, а я — совершенно другое.
Я в одном месте halts(f) уже переиспользовал, чтобы он был немного слабее, чем теоретический оракул, а как сильный оракул была функция О(f, ctx).
… давайте вообще от halts уйдем к stops? чтобы не путаться и никого больше не путать.
(третий вариант правки ответа)
я тут долго писал разные варианты алгоритмов, и математические выкладки, но решил, что это все не понадобится, потому что мне не хочется спорить в неконструктивном ключе (т.е. когда непонятное что-то не может существовать. или может. но разницы нет — потому что вы не можете описать что у него внутри, только то, что снаружи).
Я хочу спорить в конструктивном направлении — вот алгоритм, используйте его, и будет вам счастье.
И моя (признаю — это профессиональная деформация) мысль состоит в том, что если у меня нереентерабельная функция, то я не страдаю от экзистенциального ужаса, а запоминаю контекст, и такие вызовы делаю отложенными, после чего все отлично работает (ибо нет рекурсии).
Поэтому мне стало странно, что математики так не умеют, я предложил «свой вариант», и дальше понесся угар и чад — и я в общем не ожидал такого спама в ветках, если честно…
Пытаюсь понять, что такое "нереентерабельная" функция)
Смотрите, в чистом виде stops(f, input) невозможна — это факт, доказаный давным давно, и оспаривать его нет вообще никакого смысла. Главное сейчас — прояснить, почему добавление "контекста" не сделает задачу разрешимой. Давайте поймём, что за контекст передаётся.
Вариант 1 — помимо функции будет передано то, использует ли она внутри себя stops или нет. Информация может быть ложной, поэтому полагаться на неё без валидации нельзя, верно же? stops всегда должна отвечать корректно, независимо от контекста. Но — подобная валидация сама по себе алгоритмически невозможна.
Вариант 2 — даже не знаю, какие у вас были предложения? Я, как и писал ранее, не до конца понял всю идею с контекстом.
EDIT: прочитал комментарий в другой ветке. Вы предполагаете, что информация, в каком месте кода f находится вызов stops и полный стэк вызовов с состоянием всех переменных вам помогут, так?
Ответ — не помогут. Невозможно доказать, что параметр функции stops(f, *) встречается в стэке вызовов, так как не существует алгоритма проверки эквивалентности функций, например.
почему не поможет? Если там будет передаваться место в функции, то вот простой алгоритм:
1) мы принимаем контекст и функцию,
2) если контекст пустой — передаем функцию оракулу, получаем свой ответ.
3) если непустой — в переданной функции заменяем это место на 0 или 1, получаем две новых функции — передаем сами себе с пустым контекстом на вычисление. Если у вас конечная длина программы, то рано или поздно все такие места будут заменены на константы, и можно будет вычислить конкретные значения (да, это долго и неэффективно, но зато детерминированно).
То есть, подытожим:
когда вы вызываете stops(f, input, ()), вы подразумеваете, что если f внутри использует stops, то она передаёт внутрь валидную информацию о том, как именно, т.е. f грубо говоря создаёт копию себя, f0(i), в контексте которой i — это то, на что стоит заменить результат вызова stops(f, input). Давайте для простоты считать, что хотя-бы input всегда пустой, иначе с ума сойдём.
Во-первых, не слишком ли сильное требование для функции f?
Во-вторых, ну получили мы какую-то версию f0, у которой внутри гарантированно нет явного "вызова" stops. Ну как-бы и что с того? Стало проще доказать, что какой-то алгоритм остановится/не остановится? Я бы не сказал.
EDIT:
Если у вас конечная длина программы, то рано или поздно все такие места будут заменены на константы, и можно будет вычислить конкретные значения (да, это долго и неэффективно, но зато детерминированно).
Запускать программу, которая может выполняться бесконечно долго — плохая затея.
Продолжу мысль в этой ветке. Итак, есть функция
func f(g) {
if (stops(g, g)) {
while(true) {}
}
}Предполагается, что "контекстом" для неё будет по сути функция f0, передаваемая внутрь stops:
f0(i) {
if (i) {
while (true) {}
}
}stops перебирает значения i и старается принять решения.
Итак, запускаем f(f). Что получается:
- если предположить, что
f(f)останавливается, тоiподставляется как 1 (результатstops), аf(1)эквивалентна бесконечному циклу, т.е.stopsдолжна быть 0 (f(f)не останавливается). Противоречие. - если же предположить, что
f(f)не останавливается, тоiподставляется как 0, аf(0)эквивалентна пустой программе, т.е.stopsдолжна быть 1 (f(f)останавливается). Опять противоречие.
Как видно, "контекст" и предложеный способ работы stops не привносит абсолютно ничего, противоречие всё там же.
Если там еще есть оракулы — тогда повторяем замену еще раз (т.е. удваиваем количество вариантов. но это не страшно т.к. у функции конечная длина).
При этом не нужно считать все дерево — как только какой-то вариант дает ответ «остановится» — значит берем его (при этом каждый из оракулов сможет повторить эти действия, а свой ответ, т.е. индекс своего 0 или 1 — взять из своего контекста)
по определению оракула
Просил же перестать употреблять этот термин, вы ведь даже не знаете, что такое "оракул" (edit: я понимаю, что это начал делать автор статьи, тем самым вводя читателей в заблуждение). stops — это просто какая-то функция, существование которой мы предполагаем. Абсолютно детерменированная.
Вот пробуются оба варианта, с 0 и с 1, это равносильно анализу функции f0, разве нет?
Пожалуйста, укажите на конкретное место в моих рассуждениях, которое кажется вам неверным. Либо распишите всю свою цепочку рассуждений для приведённой мною функции так же подробно, как это сделал я, спасибо!
1) для начала вот эту функцию
func f(g) {
if (stops(g, g)) {
while(true) {}
}
}
придется немного переписать, чтобы передать внутрь функцию явно (а не ф-ция halts сама брала контекст вычисления неявно каждый раз):
func f(g, stops0) {
if (stops0(g, g, (0))) {
while(true) {}
}
}
2) после этого функция halts(f, f_param, ()) будет анализировать две функции: f(f_param, 0) и f(f_param, 1).
Функция halts(f, f_param, (0)) будет работать в два этапа — сначала вычислит то же, что и halts(f, f_param, ()), а потом вернет тот результат (1 или 0), который получил halts(f, f_param, ()).
3) Если там больше вызовов halts, тогда ее нужно будет переписать в виде:
func f(g, stops0, stops1, ... , stopsN ) {
if (stops0(g, g, (0))) {
while(true) {}
}
.....
if (stopsN(g, g, (N))) {
while(true) {}
}
}
и процесс будет происходить аналогично от
f(f_param, 0,0,0,...,0) и до f(f_param, 1,1,...,1).
PS: И напоследок — по идее так можно будет преобразовать (т.е. чтобы вместо рекурсии был вызов внешней функции) любые вычислимые машиной тьюринга функции (например чтобы каждый шаг был внутри такой обертки). Это будет огромное, но конечно число для перебора.
(хмм… чем-то похоже на пошаговый дебаг программы)
чтобы вместо рекурсии был вызов внешней функции
Извините, я не понимаю, где вы нашли рекурсию.
А теперь по делу:
func f(g, stops0) {
if (stops0(g, g, (0))) {
while(true) {}
}
}Я так понимаю, для данной функции стоит вопрос — чему будет равен результат halts(f, (f, halts), halts) (т.к. у f теперь два входных параметра, я явно описал их как пару). Во всяком случае, такой вопрос должен ставиться. Но давайте делать так, как вы предлагаете, и рассмотрим вариант halts(f, (f, ?), ()). Что бы он собой не представлял.
Далее, я предполагаю, что синтаксис (0) означает функцию, тождественно равную константе 0. Я наверное пропустил, где вводится такое обозначение, но да ладно, из контекста можно догадаться. Значение пустых скобок мне, кстати, не ясно.
после этого функция halts(f, f_param, ()) будет анализировать две функции: f(f_param, 0) и f(f_param, 1).
Опять что-то с обозначениями) Будем разбираться:
halts(f, (f, ?), ()) делает внутри себя 2 вызова:
halts(f, (f, ?), (0)) и halts(f, (f, ?), (1)). В таком виде получается полная бессмыслица, ибо последний параметр в halts по идее в данном "контексте" просто игнорируется. Наверное, имелось ввиду halts(f, (f, (0)), ()) и halts(f, (f, (1)), ()). Тут хоть можно что-то вычислять. Итого — первое выражение равно 1, второе — 0. Потому что f(f, (0)) остановится, а f(f, (1)) — нет.
Буду честен — я действительно старался понять, что вы собираетесь с этим делать дальше, но не смог. На этом моменте я сдаюсь. Какой должен быть ответ и как вы его собираетесь получить?
Кажется, что вы и сами сильно запутались и перестали понимать, где производится запуск функции, а где анализ (исходя из ваших замечаний о рекурсии). Да и суть доказательства вы потеряли. Вместо того, чтобы показать, что контрпример приводит к противоречию, вы стараетесь показать, что какой-то другой пример к противоречию не приведёт. Мне так показалось.
Я советую спокойно, с листочком и ручкой, определить все сигнатуры всех функций, которые вы предлагаете, далее сформулировать анализируемую функцию, её предполагаемые параметры, механизм подстановки (0) и (1) и то, что с этим потом делать. Тщательно всё это проанализировать и уже потом делать выводы. Сейчас же в ваших рассуждениях слишком много несостыковок и их слишком сложно понять из-за отсутствия внятно введённых понятий.
так как не существует алгоритма проверки эквивалентности функцийКстати, а его принципиальная несуществуемость доказана? Как с этим бинарным оракулом.
Ну смотрите, допустим есть функция, которая доказывала бы эквивалентность. Тогда строим следующие 2 функции:
f1() {
f(input)
return 1
}
f2() {
return 1
}Если можно доказать их эквивалентность в общем случае, то f останавливается на входе input, т.е. разрешима проблема остановки! А это не может быть правдой.
Так-то функция определения эквивалентности может помочь оракулу только установить факт того, что поток исполнения анализируемой функции зависит от обращения к самому оракулу (или его эквиваленту), но не избежать противоречия с if (halts(...)) loop_forever(). Разве что исключение выбросить…
P. S. Ну и в целом для кругозора интересно, что принято считать относительно существования алгоритма определения эквивалентности функций.
f1 и f2 эквивалентны тогда и только тогда, когда f(input) отрабатывает за конечно время (не зависает). Это и влечёт за собой разрешимость проблемы остановки при условии, что эквивалентность функций алгоритмически разрешима.
Формулировку последнего предложения, если честно, не понял. Вопрос в том, как понимать «существование алгоритма» или в чём-то другом?
Насколько я понял, проблема, стоящая перед «продвинутым» оракулом (вне контекста оригинальной задачи с бинарным оракулом) в том, чтобы определить, что влияющий на поток исполнения анализируемой функции вызов — это вызов этого же (или эквивалентного) оракула с той же функцией в качестве аргумента. Отсюда любопытство, возможен ли такой «продвинутый» оракул, или с вычислением эквивалентности функций тоже есть какое-то противоречие. Сугубо навскидку мне кажется, что возможно. С другой стороны, максимум, что он может — выкинуть исключение о невозможности принять решение. Так что только исключить функции, содержащие влияющий на поток вызов оракула, из множества допустимых значений на входе этого оракула.
доказана ли невозможность существования алгоритма, определяющего эквивалентность двух функций в смысле отображения множества входных значений на множество выходных, и побочных эффектов.
увы, вот тут пишут, что если такая функция существует, то из нее можно будет построить оракул
доказана ли невозможность существования алгоритма, определяющего эквивалентность двух функций в смысле отображения множества входных значений на множество выходных, и побочных эффектов.
Да, доказана. Например, в моём комментарии, доказательство там банальное.
P.S. в общем случае "побочные эффекты" это просто часть выходного значения, никакого специального отношения к себе они не требуют. Все функции в наших рассуждениях всегда чистые.
У нас на курсе матлогики и нормальные алгоритмы Маркова и машины Поста с Тьюрингом были, все эти вещи еще и на курсе дискретной математики переразобраны и т.д. Пролог (до эрланга руки не дошли, сорри), хаскель, лисп — все понятно и про побочные эффекты с чистыми функциями тоже.
Но у меня с самого начала и до сих пор удивляет, что хотя разница между «прочитать код» и «выполнить код» есть — ее использование нигде я не встретил.
Меня самого заинтересовало то, что на практике-то у меня кроме побочных эффектов, есть еще и «контекст выполнения» алгоритма, а в теории — нет…
Вот отсюда и происходит интерес — есть ли какой-то алгоритм, который будет работать на конечных последовательностях (на бесконечных — понятно, что не будет), и при этом к нему будет неприменима рекурсия (т.е. поведение не будет ей поддаваться) или диагонализация и т.д.
А потом уже к оракулам (может ли такой быть внутри и т.д.).
Давайте уточним — в доказательстве для машин Тьюринга рекурсии нет. Вот точно нет, в принципе как явления (edit: естественно, имеется ввиду рекурсия как вызов подпрограммы. Нигде не требудется явно вызов halts внутри halts или что-то подобное). Если не верите или хотите, чтобы я подробнее расписал, то скажите)
удивляет, что хотя разница между «прочитать код» и «выполнить код» есть — ее использование нигде я не встретил
Ну как же, функция halts принимает как параметр, условно говоря, "программный код", но она его не выполняет, а именно анализирует.
на практике-то у меня кроме побочных эффектов, есть еще и «контекст выполнения» алгоритма, а в теории — нет
Всё в теории есть. Контекст выполнения — часть входного параметра. Например — всё состояние условной оперативной памяти — это же просто очень длинное натуральное число. Изменённое состояние той же памяти в результате выполнения, или состояние окружения ("побочный эффект") — это тоже просто какое-то выходное значение. Именно поэтому в теории рассматривают только чистые функции — они полностью покрывают весь спектр алгоритмов, используемых в реальной жизни. Это может быть не всегда интуитивно ясно, но точно всегда верно.
С другой стороны, возможно, максимально полная частичная функция эквивалентности (область определения не включает функции, вызывающие логическое противоречие) может быть весьма общим решением?
push reality;
call logical_contradiction;максимально полная частичная функция эквивалентности
… может быть весьма общим решением?
Весьма размытые понятия. Ясное дело, что в частных случаях или для определённых классов функций можно доказывать эквивалентность, но в общем случае — нет.
"Функции, вызывающее противоречие" — это инструмент доказательства от противного. В реальности же все рассматриваемые алгоритмы всегда детерминированы. Соответственно, противоречий в них никаких нет.
В реальности же все рассматриваемые алгоритмы всегда детерминированы. Соответственно, противоречий в них никаких нет.Что ж, слава оракулу для практического общего случая х)
По идее, этот «практичный оракул» O должен отказаться от анализа «неправильной» функции F, соответствующей условиям:
— граф потока управления F содержит подграф O', эквивалентный графу потока управления O;
— поток управления F уходит в бесконечный цикл в зависимости от инвертированного значения на выходе O'.
Но тут у меня проблемы с осознанием как минимум того, как, собственно, может происходить это определение эквивалентности кусков алгоритма. Особенно почему-то пугает возможная рекурсия.
Задача останова — штука любопытная, я аж на диване подпрыгнул, но т. к. не обладаю компетенцией для сколь-нибудь глубокого анализа, тут я, наверное, и сойду ).
И будет неправ, потому что функция f в таком случае завершится. А для функции которая завершается, правильный ответ — 1. Оракул не работает.
внутри он вернет 0.
как сделать такую функцию — есть множество вариантов.
Меня лично больше всего огорчает, что математики придумали пример «для опровержения».
Для меня он звучит так что: «давайте сделаем такую операцию, чтобы если ее применить к числу — то результат умноженный сам на себя будет равен первоначальному числу». А потом сразу же «но если ему подать на вход число -1, то мы не сможем получить -1, потому что число умноженное само на себя — всегда положительное. Так что нет такой операции, ЧТД».
Со стороны это кажется смешным…
снаружи функции он вернет 1.
внутри он вернет 0.
Не никакого снаружи и внутри. Вызов ровно один. Ответ на него неправильный.
Со стороны это кажется смешным…
Неудивительно. Потому что ваша аналогия ни разу не аналогична и вы, по всей видимости, тоже не понимаете, как работает доказательство от противного.
Не никакого снаружи и внутри. Вызов ровно один.возможно в математике такого пока нет. Может и есть, но я не разобрался.
Но вот в программах — такое точно есть и даже есть разница (и ее можно найти и нейтрализовать во время выполнения функции, собственно я даже подобными вещами занимался на практике).
Вы молодец, что умеете работать со стеком вызовов. Но сейчас речь об одной конкретной программе. Не о математике. В этой одной конкретной программе есть только один вызов оракула. С одним контекстом. С одним стеком вызовов. Других вызовов оракула нет. И в этом единственном вызове оракул возвращает неправильное значение.
Оракул на вход принимает текст. Если оракулу, который запущен в песочнице, передать текст такой программы, что он выдаст? Если я верно вас понял, это то, что вы называете "снаружи". И он выдаст 1.
Что ж, в таком случае мы берём нашу программу и запускаем halts в песочнице, так, что бы он не смог узнать, что его результат будет использовать другая программа (песочница возможна, думаю тут сомнений нет). Она принимает 1 и зацикливается. Видите проблему?
Вы полагаете, что оракулу нужен контекст. Но нет никакой проблемы написать функцию f, которая будет создавать чистый контекст, как будто оракул запущен "снаружи". Дело в том, что для такой программы (которая подделывает контекст) оракул тоже должен выдавать верный ответ, иначе это не универсальный ответ. А как он выдаст верный, если контекст подделан? Только анализируя текст программы. А когда он его анализирует (просто текст), он не знает, изнутри он запущен или снаружи (мы же контекст подделали с помощью нашей программы f). Значит и изнутри и снаружи он должен выдать один и тот же ответ.
Так же, вполне возможно, что при передаче неполного контекста, то он не сможет вычислить свой результат верно.
Однако же для внешнего вызова оракула (т.е. если ему передать и песочницу и правильный контекст), это не будет критично — он сможет правильно вычислить, что песочница с таким внутренним устройством зациклится.
Нашел более простую проблему в вашем оракуле. Он снаружи вернёт 1, так?
Берём ваш оракул и немного подправим. Он снаружи для этой программы будет возвращать 0, а изнутри — 1. Будете ли вы считать такой оракул тоже верным? Если нет, то почему?
Так что простой ответ: конечно можно подправлять. Просто интерпретация значений 0 и 1 поменяется (т.е. 0 — это будет остановится, 1 — зациклится).
Просто интерпретация значений 0 и 1 поменяется
Не уходите от вопроса. Мой оракул выдает 1, если программа остановится, и выдает 0, если не остановится. Для программы f "снаружи" он выдает ноль.
Мой оракул верный? Не что "лучше для детерминированности", а верный или нет. Для всех остальных программ он выдает точно такой же ответ, как и ваш.
Если вы считаете ваш оракул (который выдает снаружи 1) правильным оракулом, а мой — неправильным, то почему?
Заранее облегчу (или утяжелю, может у вас не та задумка, о которой я предполагаю:) ) вам будущий вопрос:
оракул(оракул, «снаружи») = 1 (т.е. остановится).
пока что с этим есть небольшая заминка
Нет, с этим заминки нет. Доказательство 100% верное. Даже если в моих объяснениях что-то не так, вы всегда можете прочитать более формальное доказательство. Заминка только рассказать вам на пальцах, почему оно верное.
Для того чтобы дать правильный ответ — зациклится ли некая функция f или нет.
Хорошо. Так функция f зациклится или нет?
У меня заминка с оракулом, у которого нет доказательства несуществования, и который сконструирован так, чтобы опровержение оригинального оракула на нем не работало. И теперь я пытаюсь доказать для себя его наличие (или доказать отсутствие, это тоже будет хорошо).
Так функция f зациклится или нет?Это уже к оракулу. Пусть лучше компьютер считает числа, а не люди.
Уход от темы. Оракул не существует просто потому, что не существует ответа. Компьютер будет "считать числа" или человек — не важно. Нельзя сконструировать программу, которая сможет дать ответ на вопрос, если ответ не существует в принципе. Если хотите углубиться в тему — прочитайте про парадоксы. Про брадобрея, который брил всех, кто не брился сам, как самый простой пример.
может быть брадобреи, множества или матлогика считает цифры?
или парадоксы считают цифры?
нет, цифры считают люди, при помощи своих инструментов, и для решения своих практических задач — придумывают новые множества, законы логики, множества, парадоксы и т.д.
Корень из двух, пи, логарифмы, комплексные числа — это все исторические примеры, когда реальные задачи «не помещались» в старых теориях.
Так что я никоим образом не покушаюсь на классическую машину тьюринга и проблему останова в ней.
У меня совершенно другая задача, которую можно по разному сформулировать, можно остановиться на такой постановке: какая должна быть модификация машины тьюринга, в которой такой оракул можно было бы получить (т.е. доказать его непротиворечивость)?
какая должна быть модификация машины тьюринга, в которой такой оракул можно было бы получить
Для этого понятие алгоритма нужно сужать, а не расширять. К слову — расширить его никто ни разу не смог, см. тезис Чёрча.
теория считает цифры?
Вы сначала вводите в разговор цифры, а когда я говорю, что это не существенно, кидаете вот такие возражения. Я их, честно говоря, совсем не понял.
Если вы хотите модифицировать не оракул, а машину Тьюринга — ноль проблем. Конечно возможны и другие машины с другими правилами. Другое дело, что в формальных науках интересны строго формальные системы (что очевидно), а не описательные. Но пожалуйста, если вам интересно. В конце-концов и Тюнинг и фон-Нейман эти системы просто придумали и никакого запрета придумывать другие — не существует.
А разговор о проблеме останова для классической машины Тьюринга, думаю, завершён.
func f() {
if (halts(f)) {
while(true) {
}
}
}Предположим halts(f)вернул true, что это true означает, вам не известно до тех пор, пока алгоритм работает.
Предположим halts(f)вернул false, что это false означает, вам не известно до тех пор, пока алгоритм работает.
Если внутри вашего алгоритма дать значение будущего до того, как ваш алгоритм завершится, алгоритм попытается его опровергнуть.
Поэтому первый оракул вернёт ответ, который для алгоритма не будет иметь значение до тех пор, пока его (ответ) не соотнести с другим значением.
Например halts(f) вернул true. Алгоритм завис. Другой оракул дал обозначение этому true как бесконечное выполнение.
Например halts(f) вернул false. Алгоритм завершился. Другой оракул дал обозначение этому false как конечное выполнение алгоритма.
Причём оракул не всегда возвращает один и тот же результат. Но его ответы не будут противоречить реальности.
По сути, я пытался скрыть от алгоритма будущее, которое запрашивал от оракула алгоритм.
Как я уже говорил, размазывание вычисления значения по нескольким функциям ничего не меняет. Эти несколько функций все равно можно вызвать из проверяемого кода и получить их противоречивый ответ. Как вы будете "скрывать будущее" от следующего кода? Вводом третьего кузена-оракула, который тоже сможет инвертировать значение первых двух братьев?
func f() {
if (halts(f) xor should_invert_halts(f)) {
while(true) {}
}
}Но если halts будет получать свой контекст, то можно будет сделать такого оракула, который будет корректно отвечать на вопрос «остановится ли этот алгоритм» для внешнего наблюдателя.
отвечать на вопрос «остановится ли этот алгоритм» для внешнего наблюдателя.
Ваш вариант отвечает не на этот вопрос. А на вопрос "«остановится ли этот алгоритм» при неправильном ответе на вопрос «остановится ли этот алгоритм» для внутреннего наблюдателя".
а моя функция — она сконструирована, чтобы корректно отвечать на вопросы «зациклится ли ваша функция».
а моя функция — она сконструирована, чтобы корректно отвечать на вопросы «зациклится ли ваша функция».
И она с этой задачей в общем случае не справляется. By design. Справляется только с некоторыми оговорками, о чем вы сами написали в ветке чуть выше.
С оговорками и "func halts(f, X) {return true;}" — оракул.
Если вы передаете ей неправильные параметры, то и работать она будет неправильно.
Если вы передаете ей неправильные параметры, то и работать она будет неправильно.
Я из функции f спрашиваю у оракула, завершится ли функция f. Входных данных у этой функции нет. Он должен вернуть правильный ответ на мой вопрос. Какой ответ он вернет? Какие из моих параметров неправильны?
Для функции f он будет возвращать различные числа (но не случайные, а такие, чтобы вызов оракула от f для вас вернул правильный ответ), которые могут как совпадать так и не совпадать с правильным ответом.
он вернет правильный ответ для вас.
Для кого "нас"? Есть только один вызов оракула — изнутри функции f. Вот я и спрашиваю, какое значение он вернет. Конкретное значение. Без абстрактных "правильное", "строгое" и т.д.
уговорили. Вот вам оракул попроще.
Оракул halts
1) принимает один параметр: функцию.
2) возвращает:
0, если функция зациклится
1, если функция не зациклится
-1, если в функции используется halts( т.е. halts(halts) == -1)
С передачей контекста вычисления — можно было бы сделать и получше оракул, но раз вам оракул O не нравится — вот, можно halts.
-1, если в функции используется halts( т.е. halts(halts) == -1)
Алгоритм работает либо конечное время, либо бесконечное. Третьего варианта быть не может. Если ваш "оракул" для каких-то случаев выдает третий вариант "не знаю", то это значит, что мы в очередной раз вернулись к тому, что ваш "оракул" — не оракул в общем случае и потому ничего не опровергает.
Алгоритм работает либо конечное время, либо бесконечное. Третьего варианта быть не может.не всякий алгоритм, а только построенный по определенным правилам. Также по этим правилам вы можете построить противоречивый оракул.
Однако, если вы можете также построить непротиворечивые оракулы, которые:
Оракул О попросит у вас передавать ему контекст.
или
оракул халт, который откажется вычислять самого себя. Если второй оракул для вас не оракул, тогда ОК, я не гордый — вычеркиваем.
Оракул второго типа сделать потенциально возможно (хотя легко показать, что если он возможен, то только один). Статья (и исходная теорема) о том, возможно ли сделать оракул первого типа. Который выдает не три варианта ответа, а только два.
Оракул О попросит у вас передавать ему контекст.
Я передал. Вот тут: https://habr.com/post/436090/#comment_19621830
Что вернет ваш оракул?
Если второй оракул для вас не оракул
Речь идет о конкретной задаче. В ней нужно определить, завершает ли алгоритм свое выполнение. Любой алгоритм либо завершается, либо нет. Он не может "завершаться наполовину". То, что вы решили задачу "определить, завершает ли алгоритм свое выполнение, или ответить хз" — это, конечно, круто. Но к исходной задаче это никакого отношения не имеет.
Он и не планирует опровергать. Он предложил вам другой оракул "да/нет/не знаю". Такой оракул потенциально возможен. Конечно, с исходной теоремой он ничего общего не имеет, но рассмотреть такой измененный оракул ничего не запрещает (если кому-то интересно)
Я понимаю, что он предложил другой оракул. Но подавал он его, все же, именно в качестве опровержения моих слов :)
Я его давал в иллюстративных целях.
Перефразируя автора данной заметки — он «друг оракула», и защищает его от рекурсии :)
Оригинальное доказательство разве что использует для этого диагонализацию, но суть та же самая.
доступ к второму оракулу вы не имеете
Почему? Если функция второго оракула должна быть невычислимой на машине Тьюринга, то вы только подтверждаете, что задача неразрешима. Если вычислима, то что мне мешает эту функцию реализовать?
Понятно что невозможно создать оракул который бы работал для любой функции. Но описан ли класс функций для которых оракул создать можно? Конкретный пример, можно лио создать оракул для функций, которые не используют оракул в своих вычислениях?
Цитируя википедию: «В терминах императивного программирования — примитивно рекурсивные функции соответствуют программным блокам, в которых используется только арифметические операции, а также условный оператор и оператор арифметического цикла (оператор цикла, в котором число итераций известно на момент начала цикла).»
Что думаете по этому поводу?
Вот вам пример на пальцах: «треугольник — это фигура с тремя углами» — по определению. Строим треугольник, крутим-вертим его и тут внезапно у нашей фигуры четыре угла, т.е. — она неудовлетворяет своему же определению.
Да, в вашем случае мы скорее крутим треугольник и внезапно обнаруживаем, чтот одна из его сторон — не отрезок, а дуга окружности. Да, такой "треугольник" позволит обойти какие-то ограничения "обычного" треугольника (например, сумму углов в 180 градусов). Но только этот "треугольник с дугой" — не треугольник. И к исходной задаче про трегольник (какая бы она ни была) имеет такое же отношение, как и зависающий оракул к исходной проблеме останова.
Зависание — это будет точно такой же ответ "не знаю", как и возврат -1. Немного более хитро сформулированный, да. Но сути это не меняет.
Любой алгоритм либо завершается за конечное время, либо не завершается. Третьего варианта нет. Оракул должен давать ответ, к какому из этих двух вариантов относится переданный ему алгоритм. Если он этот ответ не дает (не важно из-за чего: из-за возврата "третьего" значения, из-за зависания или из-за уничтожения вселенной), то этот оракул не работает. Во всяком случае в рамках исходной задачи. Для какой-то другой задачи, где для оракула ответ "не знаю" является допустимым — да, зависание прекрасный способ сообщить о незнании.
Всё, что доказал Тьюринг — это, что бинарного ответа недостаточно для классификации любых алгоритмов. Нужен ещё вариант "ошибка". А задача остановки сводится к ответу на вопрос "выйдет ли указатель исполнителя за пределы произвольно заданного лимита памяти". Подробнее тут:
У меня так много вопросов… я опущу обсуждение большей части видео и сосредоточусь на мощности множества вещественных чисел и проблеме останова.
"Опровержение" доказательства Кантора — бред. Доказывать от противного, используя внутри доказательство от противного — абсолютная норма. Почитайте доказательство теоремы Менгера, например, там гораздо менее абстрактно. Плюс у Кантора не доказывается, что есть вещественное число, которое не вещественное. Краткий пересказ настоящего доказательства:
- предполагаем, что есть отображение C: R -> N, определённое на всех вещественных чисел и такое, что для разных аргументов результатом будут разные натуральные числа;
- строим конкретное вещественное число, основываясь на этом отображении;
- доказываем, что отображение C не определено на нём, что приводит к противоречию со свойствами C.
Что вас тут не устроило?
Ваше доказательство того, что вещественных чисел вполне может быть счётное количество — тоже бред. Притягивание за уши теории вероятностей и понятий вроде "мат ожидание" неуместно. На чём строится ваше доказательство в итоге? Перескажу, как я понял: выбирая бесконечное количество раз случайные вещественные числа, мы с вероятностью 1 в итоге выберем каждое из них. Кажется вы это утверждали. НО, осуществлять перебор, например используя мат индукцию, можно только для счётного количества элементов. Откуда тогда взялось число 1, если мера любого счётного подмножества равна 0? Вам формализма в рассуждениях не хватает. Это и доказательством то не назовёшь. Выглядит как "если предположить, что множество счётно, то оно счётно". Окей.
Теперь по поводу Тьюринга. Первое — что мешает выразить троичные ответы через двоичный код и рассматривать именно такой подкласс алгоритмов? Причём тут вообще классическая логика, не понимаю.
Теперь, "существовать он вполне может" — это как? Что значит "бросить ошибку"? Завершение с ошибкой — нормальное свойство машин Тьюринга, если в текущем состоянии не найдена команда, соответствующая символу на ленте. Они только так и завершаются, добавление специального состояния принципиально ничего не поменяет.
Анализатор, проверяющий выход "за границы памяти" — ровно то, что вы описали. Диапазон памяти конечен, алфавит конечен, размер программы конечен. Так что запускаем и ждём либо повторения конфигурации, либо выхода за границы. Один из этих вариантов обязательно случится за конечное время.
Другое дело, что такой анализатор ничем не поможет ввиду неограниченности ленты, о чём вы тоже сказали. Зачем тогда была вся заключительная часть?
"Алгоритм некорректен, так как его поведение зависит от результата работы анализатора" — такое свойство банально невычислимо. Вы тоже стараетесь придумать какой-то хак, ведь вам наверное просто не нравится то, что проблема останова неразрешима.
Да и вообще, завершение с ошибкой == остановка, разве нет. Скажите, какой третий вариант можно добавить к паре "остановится / не остановится"? Число шагов либо конечно, либо бесконечно, третьего быть не может, даже если добавить абсурдные и невозможные утверждения.
Скажите, вы обсуждаемые доказательства из науч-поп источников узнавали или действительно знакомы с их математическими формулировками и формальными доказательствами? Ставлю на то, что вы не сможете мне рассказать, что такое машина Тьюринга.
Извиняюсь за такой большой комментарий, меня просто задевает подобная безграмотность.
Доказывать от противного, используя внутри доказательство от противного
Тут нигде нет вложенных доказательств от противного. Есть две посылки в одном доказательстве.
у Кантора не доказывается, что есть вещественное число, которое не вещественное
В рамках исходной посылки, канторовое число сформулировано в форме брадобрея. Его не может существовать не из-за исходной посылки, а из-за формулировки. Поэтому оно ничего не доказывает.
Аналогия с брадобреем: Предположим, что все люди стригутся. Формулируем брадобрея. Получили противоречие. Значит существуют люди, которые не стригутся.
Притягивание за уши теории вероятностей и понятий вроде "мат ожидание" неуместно.
НО, осуществлять перебор, например используя мат индукцию, можно только для счётного количества элементов.
Существование такого перебора, собственно, и доказывает счётность числа элементов. Существование хоть чего-то несчётного доказать не получится без привлечения абсурдных определений.
что мешает выразить троичные ответы через двоичный код и рассматривать именно такой подкласс алгоритмов?
Ничего не мешает. Только доказательство Тьюринга разваливается.
если в текущем состоянии не найдена команда, соответствующая символу на ленте. Они только так и завершаются
Другое дело, что такой анализатор ничем не поможет ввиду неограниченности ленты, о чём вы тоже сказали. Зачем тогда была вся заключительная часть?
Произвольный объём памяти. Выделенное — это квантор всеобщности, ключевая часть доказательства по индукции.
"Алгоритм некорректен, так как его поведение зависит от результата работы анализатора" — такое свойство банально невычислимо.
Докажите.
завершение с ошибкой == остановка, разве нет.
Этот вопрос разбирается при анализе теоремы Гёделя. Ложь и абсурд — разные вещи. Понятие остановимости не применимо к некорректным программам.
Тут нигде нет вложенных доказательств от противного. Есть две посылки в одном доказательстве.
Окей, в доказательстве, которое я привёл, посылка одна.
В рамках исходной посылки, канторовое число сформулировано в форме брадобрея. Его не может существовать не из-за исходной посылки, а из-за формулировки. Поэтому оно ничего не доказывает.
Нет, там приводится вещественное число, удовлетворяющее всем аксиомам вещественных чисел, конструктивно и неоспоримо. Оно существует по построению =) Противоречие возникает не с существованием данного числа, а с существованием соответствующего отображения из R в N.
https://ru.wikipedia.org/wiki/%D0%92%D0%B5%D1%80%D0%BE%D1%8F%D1%82%D0%BD%D0%BE%D1%81%D1%82%D0%BD%D1%8B%D0%B9_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4
Метод состоит в оценке вероятности того, что случайный объект из заданного класса удовлетворяет нужному условию. Если доказано, что эта вероятность положительна, то объект с нужными свойствами существует. Хотя доказательство использует вероятности, окончательный вывод делается определённо, без какой-либо неоднозначности.
Говорю же, неуместно.
Существование такого перебора, собственно, и доказывает счётность числа элементов. Существование хоть чего-то несчётного доказать не получится без привлечения абсурдных определений.
Т.е. согласно вашим рассуждениям, вы априори считаете, что все бесконечные множества (которые содержат счётное подмножество) счётны сами по себе. А доказательство несчётности множества вещественных чисел считаете абсурдом, при этом не указав, что именно там абсурдно. Точнее так — вы указали на часть, кажущуюся вам абсурдной, я привёл контраргумент, уточняющий доказательство Кантора, в который вы, кажется, не захотели вдумываться.
Ничего не мешает. Только доказательство Тьюринга разваливается.
Напомните, в каком месте оно разваливается?
https://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0
Намекаете на специальные завершающие состояния? Их наличие или отсутствие не влияет на исследуемые свойства.
Произвольный объём памяти. Выделенное — это квантор всеобщности, ключевая часть доказательства по индукции.
Стараюсь понять, что вы имеете ввиду. Бесконечная лента и лента заданного неограниченно большого размера — совершенно разные вещи, если вы об этом. Второе — не интересно в рамках проблемы останова.
Докажите.
Из доказательства той же проблемы останова следует, что задача эквивалентности программ тоже неразрешима. Невозможно по программе понять, использует ли она какую-то конкретную "подпрограмму" или нет.
Понятие остановимости не применимо к некорректным программам.
Что такое некорректная программа? Любой набор команд для машины Тьюринга является корректной программой, каким бы бессмысленным он ни был. Машина STOP, кажется вы её так назвали, корректна по построению, если предполагать, что машина HALT существует, что являлось базой доказательства от противного.
Попробую разобраться. Я честно вдумываюсь в то, что вы пишете, поверьте. Итак, Если HALTS существует, то есть противоречие. Значит утверждение "HALTS существует" либо ложно, либо абсурдно, либо неоднозначно.
Полагаю, вы сравниваете такую машину с бородобреем, но немного теряется суть. Существование бородобрея приводит к его несуществованию. Существование же машины HALTS приводит к логическому противоречию, не утверждающему невозможность существования HALTS. И, в отличие от бородобрея, утверждение о несуществовании HALTS к противоречию не приводит, по крайней мере математика таких противоречий до сих пор не знает.
Далее, "абсурдность" и "неоднозначность". Неоднозначности быть не может, так как ложность исключена. Наверное поэтому вы её не упомянули. Остаётся исключить абсурдность.
Итак, есть утверждение: "существует объект, удовлетворяющий данному формальному свойству", которое не может быть истинным. Является ли оно абсурдным? На мой взгляд только в том случае, если его ложность приводит к противоречию. Это самый скользкий момент в ваших рассуждениях, на самом деле, ведь не до конца понятно, что значит "абсурдно" с формальной точки зрения.
Т.е., подводя итог, если исходить из предположения, что непротиворечивость теории алгоритмов в объединении с принятым утверждением о проблеме останова не доказана формально, то выходит, что истинность проблемы останова пока принимать рано, верно? То же касается любых теорем существования. Это определённо любопытный взгляд на математику. Думаю, вам просто сразу следовало сказать, что вы из тех, кто принципиально отрицает доказательства от противного, стало бы проще. В рамках данных убеждений ваш вывод уже имеет больше смысла, но, к сожалению, такая математика оказывается гораздо скучнее, ведь многие теоремы становятся недоказуемыми, или как минимум не имеют известных конструктивных доказательств. Кажется я наконец вас понял.
Тем не менее, то, что вы пишете про счётность множества вещественных чисел, даже при этих допущениях абсолютно неадекватно. При переборе надо доказывать не только то, что перебрали бесконечное множество элементов, а то, что перебрали все элементы. А этого вы не показали.
P.S. Про теорию вероятностей. Думаю вы имеете представление о том, что она строится на теории мер и что значением вероятности являются вещественные числа от 0 до 1. И то, что для непрерывных распределений требуется интегрирование и т.д. Это я к чему? Применять аппарат теории вероятностей к тому, на чём эта теория строится, немного рекурсивно, не находите?
Оракул существует