Но, как всегда, есть нюансы.
Если интересно прошу под кат.
Введение
В 1936 году Алан Тьюринг доказал, что нет общего алгоритма, анализирующего другие алгоритмы и указывающий, будет зависать программа или нет.
Хотелось бы сразу расставить все точки над ё и описать термины которые используются мной чтобы не было не понимания.
Зависание программы – алгоритм будет работать БЕСКОНЕЧНОЕ количество времени вне зависимости от скорости выполнения команд, и параллельных вычислений. Какой бы большой суперкомпьютер мы бы не построили, алгоритм всегда будет выполняться бесконечное количество времени.
Выполнение программы за конечное время – алгоритм на любой машине закончит свои вычисления какими бы объемными они не были. Например если алгоритм выполняется 300 миллионов лет это не значит, что он завис, просто на текущих ресурсах ему надо выполняться 300 миллионов лет и он ВСЕГДА завершится.
Теперь можно продолжать.
Доказательство Тьюринга можно описать так: есть некий оракул S (алгоритм) на вход которого подаётся описание алгоритма N и входные данные X. Программа останавливается и возвращает 1, если алгоритм N не останавливается, получив на вход X.
Программа не останавливается в противном случае, если алгоритм N останавливается, получив на вход X. Если же мы скормим нашему оракулу описание самого себя, то будет противоречие и алгоритм будет противоречить сам себе. Подробно можно посмотреть на вики.
Оракул существует, но ему нужен брат
Вас не смущает тот факт, что оракул должен зависнуть если алгоритм, который он анализирует останавливается, меня вот прям сильно сей факт смущает, поэтому для доказательства немного подкорректируем вывод оракула. Пусть оракул возвращает 1 либо 0. Ну что с того, спросите вы, ничего не поменялось, если мы на псевдокоде напишем:
If (оракул(N)==0){
While (true){
}
} То противоречие останется, но если мы добавим брата оракула, то всё становится интересней:
Пусть у нас есть два оракула, входные параметры одинаковы у обоих оракулов, но выводы различаются:
S1 возвращает 0 или 1 но что значат эти 0 или 1 неизвестно, об этом знает только второй оракул.
S2 возвращает 0 или 1 для обозначения данных первого оракула, но не даёт информации о работе алгоритма. 1 означает что у первого оракула 1 будет означать бесконечное выполнение алгоритма, 0 остановка. А вот ноль на оборот у первого оракула 0 будет означать бесконечное выполнение алгоритма, 1 остановка.
Оракулы ВСЕГДА выполняют анализ за конечное время, но с оговоркой. Описание оговорки будет чуть ниже.
Два оракула нужны для того, чтобы алгоритм получив данные от одного оракула не смог узнать о своём будущем, до полного выполнения всей программы. Так как узнав результат своей работы, алгоритм может изменить своё поведение, тем самым опровергнув утверждение оракула.
Оракулы запускаются на двух параллельных машинах Тьюринга, синхронизированных такт в такт. Оракулы соединены очень быстрой связью, настолько быстрой что решения они принимают одновременно.
Теперь как это будет выглядеть на псевдокоде:
Запрос к первому оракулу
If (оракул(N)==0){
While(true){
}
}Запрос к второму оракулу
If (оракул(N)==0){
While(true){
}
}Оба оракула вернут ноль что будет означать что алгоритм зависнет.
В конце выполненных алгоритмов мы можем взять и соотнести данные тем самым получив ответ.
Но есть еще один нюанс, все входные данные должны быть конечными. Ресурсы машины, также должны быть конечными. Если хоть что-то будет бесконечным, то гарантировать анализ оракулами за конечное время нельзя.
Заключение
Так как Алан Тьюринг доказал, что общего алгоритма быть не может, значит с большой долей вероятности в нашей теории кроется ошибка. Поэтому всех неравнодушных прошу в комментарии помочь найти такую ситуацию, которая бы смогла помочь решить текущую задачку.
Комментарии (142)
Sychuan
14.01.2019 23:46+1Мелкие замечания
1. Оракул — это черный ящик, а не обычный алгоритм или машина Тьюринга, который может делать что-то магическое. Например, мы не можем доказать что алгоритм не может вычислять X, т.к. это сложно, но можем доказать, что он не может вычислять X даже с оракулом.
2. В английской википедии доказательство написано гораздо яснее. Доказательство Тьюринга тоже более понятное.
3.Ресурсы машины, также должны быть конечными
У машины Тьюринга бесконечная память, а у вас машина с конечной памятью, т.е. вроде как гораздо более слабая, способна решать проблему останова. А если у нее не хватит ленты для ввода? Как-то это подозрительно.
4. «S1 возвращает 0 или 1 но что значат эти 0 или 1 неизвестно, об этом знает только второй оракул.» Мы можем узнать, что означают 1 и 0 после нескольких попыток от второго оракула. Почему они не могут быть одним алгоритмом? Зачем их два?
5.Два оракула нужны для того, чтобы алгоритм получив данные от одного оракула не смог узнать о своём будущем
Как алгоритм узнает будущее?
По-моему у вас есть оракул, который отвечает может ли остановится алгоритм или нет. Это, конечно, может быть, но смысла в таком не очень много.
Dim0v
15.01.2019 03:18"Размазывание" вычисления значения функции останова по "братьям", "сестрам" и прочим родственникам ничем не поможет.
В вашем конкретном случае достаточно взять, например, две следующие программы, которые вообще игнорируют второго оракула и обращаются только к первому:
If (оракул(N)==0){ While(true){} }
If (оракул(N)==1){ While(true){} }
Независимо от того, что у этого оракула значит 1, а что значит 0, одна из программ будет противоречива. Если 0 — это остановка, а 1 — бесконечное выполнение, то противоречивой будет первая программа. Иначе — вторая.
Или же просто убрать это бессмысленное размазывание вот так:
If (оракул1(N) xor оракул2(N) == 1){ While(true){} }
И получить ситуацию, полностью аналогичную ситуации с одним оракулом.
EndUser
15.01.2019 07:47Три ограничения нужны не для того, чтобы найти или потерять оракула.
Это просто теорема Гёделя о неполноте в приложении к вычислительной технике.
Чтобы не борзели от всемогущества.
andyudol
15.01.2019 11:25Почему у Тюринга оракул останавливается и возвращает 1, если алгоритм N не останавливается? Почему не наоборот? Он сам это как-то обосновывает?
Dim0v
15.01.2019 12:56Потому что автор статьи смешал в кучу принцип работы функции, решающей проблему останова и доказательство невозможности существования такой функции.
Оракул и не должен зависать. Он должен говорить, останавливается ли программа, поданная ему на вход. Но если такой оракул существует, то становится возможным написать следующий код:
func f() { if (halts(f)) { while(true) {} } }
Такой код противоречит сам себе. Если оракул говорит, что функция f останавливается, то условие if (halts(f)) будет истинным, следовательно — управление перейдет к строке с бесконечным циклом и функция не завершится. Получили противоречие. Если оракул говорит, что функция не завершится, то условие if (halts(f)) будет ложным и функция завершится сразу. Снова противоречие. Таким образом, исходное предположение (о том, что существует оракул, определяющий, завершается ли произвольный алгоритм за конечное время) было ложным.
andyudol
15.01.2019 13:13То есть доказательство ложности предположения основано на том, что выбранный язык программирования позволяет написать бессмысленный код?
Dim0v
15.01.2019 13:23Нет. Бессмысленный код позволяет написать не «выбранный язык программирования», а само предположение. Из чего и следует ложность этого предположения. Доказательством от обратного такой приём называется.
andyudol
15.01.2019 14:06func f() { while(true) { if (halts(f)) { return 'Завершится.' } } }
?Dim0v
15.01.2019 14:25И? Что вы этим хотели сказать?
Что для этого кода противоречий нет? Да, их нет (любой ответ оракула будет правильным и непротиворечивым). Для многих алгоритмов решение проблемы останова вообще тривиально, как, например для "print('Hello world')" или "while(true) {}" и еще многих других. Но возможность создания оракула, который будет правильно работать для некоторых алгоритмов никак не доказывает существование решения для общего случая.
andyudol
15.01.2019 14:32+1Да, но возможность создания оракула, который будет не правильно работать для некоторых алгоритмов никак не доказывает не существование решения для общего случая.
Dim0v
15.01.2019 14:43Так мы и не создаем "оракула, который будет не правильно работать для некоторых алгоритмов". Мы описали алгоритм, для которого ни один оракул не сможет дать корректный ответ.
Оракул в примере — это функция halts, а не f. Мы ее не создаем, а просто предполагаем ее существование (в виде черного ящика). Если она существует, то она должна корректно работать в том числе и для функции f из моего примера. Но она не может корректно работать для функции f. Из этого следует, что наше исходное предположение о существовании такой функции halts — ложно. Эта функция (оракул) не может существовать.
andyudol
15.01.2019 16:12Оракул в примере — это функция halts, а не f.
Правильно. При этом и вас, и у меня она абсолютно одинаково говорит, остановится программа или нет.
При этом у вас вызывающая оракула функция начинает выполнять бесконечный цикл, а у меня набоборот — прекращает. Ни то, ни другое не доказывает ни возможность, ни невозможность реализации оракула.Hardcoin
15.01.2019 16:20она абсолютно одинаково говорит, остановится программа или нет
Уточните, пожалуйста, в примере Dim0v выше halts(f) должен вернуть true или false? Представьте себе абсолютно правильный оракул. Какой ответ на ваш взгляд он должен выдать, если у него спросить про f?
andyudol
16.01.2019 14:38Вообще-то я пришёл сюда с близким вопросом: на основании чего сформулированы требования к оракулу? Вместо ответа я получил бессмысленный код, не реализующий никакого алгоритма. Это было настолько неожиданно, что я растерялся. Может быть фигню сморозил. Уж извините тогда.
А что должен вернуть оракул? Ну давайте так — самозванцев нам не надо, ораклом буду я. Пусть я получил код и данные. Возможны 4 варианта:
1. Я смотрю и ничего не понимаю — язык не знакомый. Я возвращаю «не понимаю» и перехожу к другим делам.
2. Язык знакомый, я вижу, что выполнение программы никогда не закончится. Я так честно и говорю: «нет». И перехожу к другим делам.
3. Вижу, что закончится —> «да». И перехожу к другим делам.
4. Вижу противоречие. За это, как за шуллерство — канделябрами. И перехожу к другим делам.
Я хотел узнать, почему из четырёх возможных действий выбрано только второе. Я не собираюсь опровергать теорему. Я и без математики знаю, что природа не алгоритмична.Dim0v
16.01.2019 15:36Вообще-то я пришёл сюда с близким вопросом: на основании чего сформулированы требования к оракулу?
Я вам ответил. Оракул должен определять, завершится ли выполнение алгоритма за конечное время. Всё. Сформулированы такие требования на основании описания задачи.
Вместо ответа я получил бессмысленный код, не реализующий никакого алгоритма.
Не "вместо", а "вместе" с ответом. И не "бессмысленный код, не реализующий никакого алгоритма", а код, демонстрирующий невозможность существования такого оракула. Любой код реализует какой-то алгоритм. А вопросы про "осмысленность" и "бессмысленность" алгоритмов — это к философам.
Возможны 4 варианта:
Нет. Код либо работает конечное время, либо бесконечное. Других вариантов нет. И оракул, если он существует, должен давать правильный ответ
почему из четырёх возможных действий выбрано только второе.
Покажите, пожалуйста, где именно кто-то кроме вас производит выбор из ваших 4 действий и где именно кто-то выбирает именно второе из них?
Hardcoin
16.01.2019 15:50Да никто не выбрал второе. Наоборот, второй ответ не подходит. Потому что если оракул ответит нет, то программа из-за этого завершится. И независимый свидетель скажет — ваш оракул ошибся, видите? Он сказал "нет, не завершится", а программа завершилась.
А считать, что машина Тьюринга "мошенничает", это как-то странно.
Судя по вашему ответу, вы считаете, что оракул должен выдавать один из трёх ответов (вариант "это не код" отметаем, он не интересен).
- Да, завершится.
- Нет, не завершится.
- Мошеннический код, ответ не возможен.
Так вот, теорема о том, возможен ли оракул с двумя видами ответов? "Завершится/не завершится". Ведь логика подсказывает, что даже "мошеннический" код либо завершится когда-нибудь, либо не завершится никогда, не так ли? Разве может быть третий вариант?
Но вы и сами видите — нет, такой оракул невозможен. Возможен только оракул с тремя вариантами ответов. Да, нет, "идите отсюда". А с двумя — невозможен. Это не хорошо, не плохо, просто так есть.
Jouretz
16.01.2019 15:54язык программирования позволяет написать бессмысленный код?
Язык знакомый
язык не знакомый
Что вы к языку привязались то? Задача не про языки, а про алгоритмы.
Тьюринг-полный там язык, который позволяет написать любую ахинею в рамках доступной архитектуры. Asm, brainfuck, basic, хоть js, суть задачи от этого не меняется.
А суть приводимых вам алгоритмов в том, что для доказательства невозможности написать алгоритм разбирающий любую программу, достаточно привести хотябы один пример программы, для которой написание такого алгоритма невозможно.andyudol
16.01.2019 17:40-1Никаких алгоритмов мне не приводили. Мне привели код, который рализует (якобы) алгоритм, который не может существовать.
balexa
15.01.2019 16:25Это не вызывающая оракула функция, это функция которая подается оракулу. Суть в том, что оракул — это тоже программа. И да, в данном примере ему предлагают проверить самого себя.
И вам объясняют, что если оракул допустить, что оракул существует, то в данном примере получается логическое противоречие. Значит, его не существует. Это называется доказательство от противного. То что вы можете подобрать непротиворечивый пример, никто и не спорит. Заканчивайте тупить.
Dim0v
15.01.2019 16:45При этом у вас вызывающая оракула функция начинает выполнять бесконечный цикл, а у меня набоборот — прекращает.
Да. И еще в моем случае при этом возникает логическое противоречие, а в вашем — нет.
Ни то, ни другое не доказывает ни возможность, ни невозможность реализации оракула.
Ваш пример — да, ничего не доказывает. Мой доказывает невозможность существования (не реализации) оракула.
Оракул, работающий для общего случая, должен работать в том числе и для программы из моего примера. Но для программы из моего примера любой ответ любого оракула будет неверным.
Почитайте о том, как работает доказательство от противного.
Hardcoin
15.01.2019 16:14+1Это не возможность создания оракула. Это возможность создания программы, для которой любой оракул будет работать неправильно.
Представьте себе человека, который делает оракула. А второй проверяет, работает ли оракул. Так вот, второй всегда сможет написать такую программу, что бы оракул первого выдал неверный результат. То есть первый никогда не сможет сделать достаточно хорошего оракула.
Именно это и называется "не существует решения для общего случая".
Hardcoin
15.01.2019 16:09Бессмысленный для вас? Я бы хотел посмотреть на Тьюринг-полный язык, который НЕ позволил бы написать бессмысленный код.
Это особенность всех доказательств (и в математике тоже) — они рассматривают не "смысл", а целостность. В данном случае рассматривается, существует или не существует такая "бессмысленная" программа. Она существует, из нее следует, что оракул невозможен.
vassabi
15.01.2019 17:17очевидно, что в Х еще входит и контекст вызова функции. Т.е. если вы вызовете
halts(f) то это не то же самое, что вы вызовете f() который внутри себя вызовет halts(f).
А если передавать контекст, то у вас она вернет 1 (т.е. halts(f,()) это 1 ), потому что изнутри f она вернет 0 (т.е. halts(f,(f)) это 0 ), и все будет корректно.Dim0v
15.01.2019 18:39очевидно, что в Х еще входит и контекст вызова функции
В Х входят только входные данные проверяемой функции. Если функция как-то использует контекст своего вызова, то да, он входит в Х. В данном случае функция f работает абсолютно одинаково, независимо от того, в каком контексте она вызвана. Так что для нее контекст вызова в Х не входит. Значение функции-оракула по определению также не должно зависеть от контекста вызова. Оно зависит только от проверяемого алгоритма, его входных данных и ни от чего больше.
Понятно, что можно описать (да что там, даже реализовать) поведение halts так, чтобы в данном конкретном примере она возвращала что-то непротиворечивое (своей внутренней логике). Но это будет не функция-оракул, а что-то другое.
Кстати,
А если передавать контекст, то у вас она вернет 1 (т.е. halts(f,()) это 1 ), потому что изнутри f она вернет 0 (т.е. halts(f,(f)) это 0 ), и все будет корректно.
А почему не наоборот?
vassabi
15.01.2019 19:16+1Но это будет не функция-оракул, а что-то другое.
в смысле не оракул-функция? Она не будет вычислять «остановится ли функция f» для пустого контекста (т.е. для математика)?
А почему не наоборот?
потому что эта функция зациклится же.
можно и наоборот (0 снаружи, 1 внутри) — заметьте, от этого истинность результата не поменяется.Dim0v
15.01.2019 19:49Она не будет вычислять «остановится ли функция f» для пустого контекста (т.е. для математика)?
Повторюсь. Поведение функции f не зависит от контекста. Контекст не входит в Х. Поведение оракул-функции тоже не зависит от контекста. Для одних и тех-же данных она должна давать один и тот-же правильный ответ.
"Для математика" ответ будет правильным только в случае неправильного ответа во внутреннем вызове. А оракул-функция должна давать правильный ответ всегда.
vassabi
15.01.2019 21:30Поведение оракул-функции тоже не зависит от контекста. Для одних и тех-же данных она должна давать один и тот-же правильный ответ.
Мой строгий оракул для одного и того же контекста будет выдавать один и тот же ответ.
Но правильным его можно будет назвать только для случая, когда когда он вызван снаружи относительно функции (т.е. с пустым контекстом).
Когда же он вызван внутри анализируемой функции, он не будет ни правильным, ни неправильным — он может возвращать как и совпадающий, так и не совпадающий с правильным ответом результат (потому что он будет не ответом, а частью решения, и т.о. нацеленным на правильность ответа).Dim0v
16.01.2019 03:26Но правильным его можно будет назвать только для случая, когда когда он вызван снаружи относительно функции (т.е. с пустым контекстом).
Когда же он вызван внутри анализируемой функции… он может возвращать как и совпадающий, так и не совпадающий с правильным ответом результатТо есть он не будет корректным оракулом в общем случае. Ч.т.д.
Не говоря уже о том, что у вашего оракула может не быть возможности определить, "снаружи" он вызван или "изнутри".
Анализируемая функция может быть сконструирована так, что внутри нее ваш оракул будет вызван точно таким же образом, каким предусмотрен его вызов снаружи. С таким-же "контекстом", если хотите.vassabi
16.01.2019 11:31вы придумываете функции, чтобы «сломать» оракул, а я придумываю оракул, который нельзя поломать при правильном использовании.
В принципе, можно не требовать «передавать контекст» внутрь оракула явно, просто дайте ему доступ к состояниям той машины, на которой его вычисляют — он сможет тогда получить доступ к контексту сам.Dim0v
16.01.2019 12:52я придумываю оракул, который нельзя поломать при правильном использовании.
Нет "неправильного" использования. Вызов оракула должен давать ответ на вопрос, завершится ли переданный ему алгоритм. Всегда. Без исключений и оговорок. Кроме непосредственно алгоритма (в виде строки, если хотите) и его входных данных, доступа у оракула ни к чему нет. Ваш оракул не сможет определить, вызвали ли его "изнутри" или "извне".
дайте ему доступ к состояниям той машины, на которой его вычисляют
Пожалуйста. Вот состояние машины, на которой его запускают. Выполняется вот этот код.
f(); func f() { > if (halts(f)) { while(true) {} } }
Текущая инструкция обозначена с помощью >. Какой результат вернет ваш оракул в данном вызове?
vassabi
16.01.2019 15:01Нет «неправильного» использования.
Среда выполнения алгоритма тоже является частью алгоритма. Для примера: вы можете сделать функцию W, которая будет эмулировать машину тьюринга и на ней запустить оракула O, который будет смотреть на f(), в которой будет вызываться O и т.д. ad infinitum. Но если вы будете вычислять значения O(W), то для правильной работы оракул должен знать: он внутри W или снаружи W.
Когда-то в математике нельзя было записать длину диагонали квадрата. Или такое число, чтобы оно давало отрицательные числа при умножении самого на себя, так что когда-то это были такие функции «с оговорками». А теперь все пишут квадратные корни, числа пи, мнимые единицы и прочая и прочая.
Может, если добавить что-то в аксиомы, и будет оракул «в общем виде», а пока — так.Dim0v
16.01.2019 15:26Но если вы будете вычислять значения O(W), то для правильной работы оракул должен знать: он внутри W или снаружи W.
Пусть знает. В моем примере выше оракул знает, в какой среде он запущен. Какое значение он вернет в месте своего вызова? Такое место одно. Оракул вызывается один раз и должен вернуть ровно одно значение. Какое?
а пока — так.
То есть, если отбросить философствования об истории математики, то мы снова возвращаемся к тому, что оракул в общем виде все таки существовать не может.
Может, если добавить что-то в аксиомы
Что? И в какие аксиомы?
vassabi
16.01.2019 15:43для halts — я в другой ветке написал.
для оракула О(f, ctx) у вас неправильный пример.
Должен быть
if (O(f, ctx)) {
где в данном случае ctx = (f, 0), и при таких значениях своих входных параметров он вернет 0.
UPD: в те аксиомы, на основании которых у вас вычисления происходят. Есть же аксиомы стереометрии, аксиоматика теории множеств или вещественных чисел и т.д.
А вот знал бы что (в короткой форме, без выводимых из других аксиом частей) — то писал бы не на хабр.Dim0v
16.01.2019 15:51у вас неправильный пример.
Должен быть
if (O(f, ctx)) {Ок.
f(); func f() { ctx = (f, 0) if (O(f, ctx)) { while (true) {} } }
Здесь ваш оракул вернет 0? В таком случае его ответ неверный. Выполнение функции завершится. Вернет 1? Ответ тоже неверный. Выполнение функции не завершится.
vassabi
16.01.2019 16:20O(f, ctx) = 1 при ctx = () и
O(f, ctx) = 1 при 0 при ctx = (f, 0)
два верных результата, плюс функция f счастливо завершается.Dim0v
16.01.2019 16:26O(f, ctx) = 1 при 0 при ctx = (f, 0)
О! У нас именно этот случай. Повезло!
Так, значение 1. Значит функция f завершается. Проверим:
if (O(f, ctx)) { while (true) {} }
ой. Мы попали внутрь ифа и в бесконечный цикл. Ответ вашего оракула оказался неправильным :(
два верных результата
Откуда два? В коде только один вызов O. Да и тот вернул неправильный ответ.
vassabi
16.01.2019 16:33там небольшая опечатка, правильно так:
O(f, ctx) = 1 при ctx = () и
O(f, ctx) = 0 при ctx = (f, 0)
и т.д.
если вы хотите в символьных выражениях, тогда можно в частном случае развернуть в такой код:
if (O(f, (f, 0))) {
while (true) {}
}Dim0v
16.01.2019 16:37+1То есть ответ 0? Ок, не беда. Перепроверим.
Так. 0 значит, что функция f не завершается. Проверим:
if (O(f, (f, 0))) { while (true) {} }
ой. Мы не попали внутрь ифа и функция завершилась. Ответ вашего оракула оказался неправильным :(
vassabi
16.01.2019 16:39ответ оракула вам будет равен 1, как и полагается при вызове O(f, ()).
Если вы вызывали O(f, (f, 0)), то он вернет правильный, но непригодный для вас ответ.Dim0v
16.01.2019 16:45+1Оракул вызывается ровно в одном месте один раз. Нет никаких вызовов "для нас" и "не для нас".
И в этом одном единственном месте своего вызова ответ оракула был неправильным. Ваш оракул не работает.vassabi
16.01.2019 16:58-1…
я не запрещаю называть вам белое синим, а шляпу — женой (и наоборот).
Но мне все-таки любопытно: почему вы решили, что он не работает?Jouretz
16.01.2019 17:02+1Потому что возвращает 'непригодный' (aka 'невалидный') результат?
vassabi
16.01.2019 17:04-1а вы ей передали на вход валидный результат?
(и чтобы не отвечать вопросом на вопрос, а то это все-таки дурной тон).
Я перечислил варианты результатов функции от входных параметров. Оба — валидные, но каждый — на смоем месте вызова. Уверен, что вы не ошиблись с передачей параметров и получили корректный ответ.Dim0v
16.01.2019 17:09Покажите как надо. Что сюда вписать и какой результат вернет оракул?
f(); func f() { if (O(f, /*здесь может быть ваша реклама*/)) { while (true) {} } }vassabi
16.01.2019 17:29-1просто передайте ему ctx.
PS: Возможно, это и есть та новая аксиома, которой не хватает для непротиворечивых оракулов… надо думать.Dim0v
16.01.2019 18:37просто передайте ему ctx.
Ок. Не спрашиваю, какое значение должно храниться в ctx. Допустим, правильное.
Передал ctx. Какое значение вернул оракул?vassabi
16.01.2019 18:58ответ: вычисленное на основании переданных параметров.
А если вы все параметры внутри предавали правильно, то и оракул от функции+пустой ctx вернет свой вердикт — зациклится она или нет.Dim0v
16.01.2019 19:03А если вы все параметры внутри предавали правильно,
Во-первых, оракул должен правильно работать для всех функций. В том числе и тех, которые вызывают его с "неправильными" параметрами. Во-вторых — какое бы значение он тут не вернул — правильным оно быть не может, потому что поведение функции будет противоречить тому, что вернул оракул.
vassabi
16.01.2019 19:06оракул будет работать для всех функций, кроме тех, где его вызовут с неверными параметрами.
Сделайте функцию, которая будет работать от положительных чисел, я вам туда передам отрицательное и все вместе будем ходить вокруг да около: «правильная или неправильная» и т.д.Dim0v
16.01.2019 19:13Ответ моей функции в таком случае будет неправильным. Как и неправильный ответ вашего оракула. А значит моя функция не работает в общем случае. Как и ваш оракул.
vassabi
17.01.2019 01:19в общем случае контекстов (всяких, в том числе некорректных) — она не работает.
Но если контекст относительно f будет корректный, тогда она сработает для данного f.
Jouretz
16.01.2019 17:30+1В том-то и вся фишка.
В примере
f();
func f() {
if (O(f, /*здесь может быть ваша реклама*/)) {
while (true) {}
}
}
Функция не принимает никаких параметров на вход. Следовательно O(f) — константа для неизменной среды.
Но если O(f) = 1, то функция зависающая O(f) =0,
А если O(f) = 0, то функция завершает своё выполнение O(f) = 1.
Никаких начальных, конечных, промежуточных и т.п. данных нет.
Оракул можно воспринимать как парсер, например. Который должен по коду ( не запуская функцию ) вернуть результат 0 либо 1.
И в данном случае и возникает противоречие.
Dim0v
16.01.2019 17:04+1Потому что он только что дал неправильный ответ. Не "правильный, но непригодный", а именно неправильный. Оракула вызвали один раз. Спросили об одной функции. Его ответ не совпал с фактическим поведением этой функции.
Или вам больше нравится более мягкая характеристика "Работает. Иногда правильно, но не всегда"? Ок, можно и так сказать)
vassabi
16.01.2019 17:22-1оракула вызвала функция внутри себя от определенных параметров, она получила свой результат.
если вызвать оракул извне, то оракул получит другие значения на вход и вернет другой (а возможно и такой же) результат.
ibessonov
16.01.2019 17:25+1Давайте я тут переспрошу — «оракул» валидирует эти значения? Если нет, то что нас обязывает заранее передавать туда правильный ответ? Не вижу ни одной причины для этого.
Сейчас же ваш аргумент сводится к простому «скажите оракулу сами, останавливаетесь вы или нет».vassabi
16.01.2019 17:32-1т.к. вы отказались от переменной ctx, я вам назвал конкретные значения.
Теперь вам не нравится что конкретные значения — конкретные… Тогда передавайте контекст и будет вам общий случай.ibessonov
16.01.2019 17:37Я пытаюсь понять, что представляет собой контекст. Вот прям конкретно — это какое-то число или какая-то функция?
vassabi
16.01.2019 17:58вот сейчас попробую «прям конкретно» сформулировать (хотя и не смогу претендовать на корректность, но мы же для этого и спорим тут не так ли — чтобы уточнить формулировки ):
это функция, которая возвращает (функция, в которой был вызван оракул + параметры фунцкции + место в функции из которого вызван оракул + значения внутренние переменные к даному времени + итерация вызова если в цикле), вот как-то так.Dim0v
16.01.2019 18:42Ок, давайте по порядку.
функция, в которой был вызван оракул
f
параметры фунцкции
()
место в функции из которого вызван оракул
вторая строка. Внутри оператора проверки условия.
значения внутренние переменные к даному времени
внутренних переменных нет
итерация вызова если в цикле
не в цикле.
Ничего из этого не меняется, потому что вызов один.
И любой ответ оракула на этот вызов будет неправильным.vassabi
16.01.2019 18:59ответ оракула — с этими параметрами мне нужно вернуть значение противоположное оракулу с пустым контекстом, по соглашению — у него должно быть 1 (если возможны оба варианта), так что я возвращаю 0. конец.
Dim0v
16.01.2019 19:07я возвращаю 0. конец.
И функция завершается. Значит ваш 0 был неправильным ответом.
vassabi
17.01.2019 01:27почему неправильным?
Он не тот же самый, что для пустого контекста — это да.Jouretz
17.01.2019 03:35Да, господи.
f(); func f() { if (O(f, ())) { while (true) {} } }
Этот код зависнет при выполнении или нет?
Мы вызвали f с пустым контекстом.
Если код зависает, значит оракул сказал что f с пустым контекстом не зависнет = соврал.
Если код не зависает, значит оракул сказал что f с пустым контекстом зависнет = опять соврал.
В чём проблема-то? Откуда у вас там наблюдатели и контексты? Это программирование, а не квантовая физика, в конце концов. Тут есть два варианта 0 либо 1.
А у вас оракул пытается маскироваться под квант, и возвращать разное значение в зависимости от того смотрю я на него или нет.
Просто подумайте, зависнет ли тупо запущенный кусок кода и почему.vassabi
17.01.2019 11:13так, давайте только без квантовой физики.
нет никаких маскировок, одно только соглашение про побочные эффекты (передача внутрь состояния).
Соглашение очень простое — состояние должно передаваться корректно.
Вот вам простая аналогия из императивного программирования: проход по циклу. Т.е. у меня простой цикл
for (i = 0; i <= N; i++) { foo(i);}
чтобы продемонстрировать корректность работы, я беру элементарный пример в котором N=0, и тогда можно подставить конкретное i=0, что будет выглядеть как
{ foo(0); }
и все работает ОК.
Я понимаю, что можно написать { foo(-1); }. Можно.
Но это уже не будет корректным преобразованием для
for (i = 0; i <= N; i++) { foo(i);}
не так ли?
Если вы вставите внутрь своей функции некорректный вызов моей функции — то это не опровергает и не доказывает ничего (нк, кроме того что мы друг друга так и не поняли ...)Jouretz
17.01.2019 11:20К чему столько текста? Приведённый кусок кода из 6 строчек зависнет или нет?
vassabi
17.01.2019 11:26чтобы вы поняли, что вы мне предлагаете находить производную от функции:
f(x) = x +*-xх
«Все значки правильные? да, правильные. Так найдите производную! Что, не получается? Значит у вас противоречие!»
и так по кругу… эх!
Лучше буду тратить свое время на комментарий ibessonov про диагонализацию и стеки — так оно гораздо более продуктивно будет использоваться…Jouretz
17.01.2019 11:37Какие к чёрту производные?
Программа либо может выполниться за конечное время либо не может. Нет никакого третьего состояния. Если программа сразу падает с ошибкой — она выполняется за конечное время. Если в программе цикл без проверок и выходов — она зависает. Если в коде jmp start; без условий то код зависнет.
Программа абсолютно валидна с точки зрения логики и синтаксиса.
В чём проблема определить завершится она или нет? Какие, к чёрту, производные?vassabi
17.01.2019 11:57все символы правильные, вычислите мне производную по х:
f(x) = x +*-xх
а может найдете логарифм от -1 в вещественных числах? А как насчет последнего цифры в десятичной записи числа пи?
Соревноваться в «кто задаст больше некорректных вопросов» — извините, без меня.
Программа, которую вы написали — невалидна с точки зрения постановки задачи, ее результат ничего не доказывает и не опровергает.Jouretz
17.01.2019 12:09В 1936 году Алан Тьюринг доказал, что нет общего алгоритма, анализирующего другие алгоритмы и указывающий, будет зависать программа или нет.
Чем она, блин, не валидна? Она не является алгоритмом?
То что можно построить оракул который разбирает некоторые типы алгоритмов, никак не доказывает возможность построения оракула для всех алгоритмов и, в принципе, к исходной задаче никакого отношения не имеет.
С таким подходом можно элементарно показать что существует оракул определяющий выполнимость любой задачи длинной не более одной команды. И что? Толку от такого оракула?
Jouretz
16.01.2019 16:46+1Это как? Мне подходит, например, любой правильный ответ, я не брезгливый.
vassabi
16.01.2019 17:03-1это так, что есть разница — вычисляется ли оракул рекурсивно или нет.
Я предлагал либо дать доступ к контексту, либо вот — явно передавать контекст внутрь.
Я тоже не брезгливый, мне все равно — передают внутрь функций верные или неверные значения.
Просто я удивляюсь тому, что кто-то передает на вход мусор и удивляется, что на выходе — тоже мусор…Dim0v
16.01.2019 17:06+1вычисляется ли оракул рекурсивно или нет.
Что и как вы в вашем оракуле вычисляете — это детали реализации. Хотите — вызывайте себя рекурсивно, если встретили в тексте вызов себя. Хотите, вычисляйте как-то еще. Хотите — не вычисляйте вообще. Только в место вызова ответ правильный верните. Ваш оракул (и никакой другой, к слову) этого не делает.
Просто я удивляюсь тому, что кто-то передает на вход мусор и удивляется, что на выходе — тоже мусор…
Где и какой мусор передавали на вход вашему оракулу и как нужно было передавать правильно?
vassabi
16.01.2019 17:28-1если вы хотите узнать — есть зациклится ли f — то вы передаете ей "()", если вы хотите вызвать его внутри f, то передаете (это в данном случае. Если f — другая, то и значения второго параметра будут другими) "(f, 0)"
Dim0v
16.01.2019 18:45если вы хотите вызвать его внутри f
Я его вызвал внутри f. Передал те параметры, что вы сказали (f, 0). Он вернул ответ, который вы сказали. Этот ответ неправильный, функция повела себя по другому.
vassabi
16.01.2019 19:01если вы внутри f вызвали его с параметрами (), то вызов его вне функции f с параметрами () будет возвращать 0.
Hardcoin
16.01.2019 16:01+1Внутри функции f — не ваш оракул. Там текст, полностью совпадающий с текстом вашего оракула. Если вам так проще, то скажу, что это не тот же самый объект, а другой. И этот объект должен по тексту решать — завершится программа или нет.
То есть вы должны не эту прогу починить, а оракул. Что бы он для любой проги смог дать ответ. Но к сожалению, невозможно. Любой оракул будет иногда ошибаться. Для общего случая он невозможен.
vassabi
16.01.2019 16:22вы сейчас описали свои желания? хорошо, учтем.
Текст оракула, не текст оракула, моя функция или нет — если в нее передавать заданные параметры, то она вычисляет правильный ответ.Dim0v
16.01.2019 16:28+1если в нее передавать заданные параметры, то она вычисляет правильный ответ.
Увы, не вычисляет(
vassabi
16.01.2019 16:37-1вычисляет-вычисляет
habr.com/ru/post/436090/#comment_19622020
PS: извините, что передразниваю, но реально — по существу есть возражения?Dim0v
16.01.2019 16:50+1По существу вам уже 100 раз написали)
vassabi
16.01.2019 18:14когда видно отступы — тогда я вижу, кому я отвечал, а кто — мне.
А когда ветка длинная — то я уже начинаю теряться, кто кому и что отвечал.
по существу, мы с вами так и топчемся на месте, но передать смысл своей идеи мне вам пока не удаётся, увы…
И все идёт к тому, что так и не получится.
Hardcoin
16.01.2019 15:56Что значит, передать контекст? Вы имеете ввиду, что у функции должно быть два параметра? Или она должна обращаться к глобальным переменным? Ради чего? Задача не в том, что бы написать корректную функцию. Наоборот, задача в том, что бы написать НЕ корректную (но без ошибок), что бы оракул дал неверный ответ.
Зачем? Что бы показать, что оракул сломан. И никто не сможет сделать работоспособный оракул, такой, что бы для любой программы смог дать ответ. Всегда можно написать программу такую, что оракул ошибётся.
То есть рабочий оракул невозможен. Об этом и теорема.
vassabi
16.01.2019 16:29Если ваша задача придумать такой оракул, который сломается — да пожалуйста. Можете сразу объявить, что вы придумали оракул 0, который выдает всегда 0 и поэтому можно написать правильную функцию, на которой он не работает.
Если ваша задача доказать, что «никто не сможет сделать работоспособный оракул, такой, что бы для любой программы смог дать ответ», то пока что с этим есть небольшая заминка.
Что значит, передать контекст? Вы имеете ввиду, что у функции должно быть два параметра? Или она должна обращаться к глобальным переменным? Ради чего?
а вот это уже хорошие вопросы.
1) передать значения, по которым оракул мог бы определить — вызван ли он из анализируемой функции и из какого места (+ с какими параметрами).
2) не у функции, а у оракула — да, два параметра
3) глобальные переменные или нет — это уже детали реализации.
4) Для того чтобы дать правильный ответ — зациклится ли некая функция f или нет.Dim0v
16.01.2019 16:34+1передать значения, по которым оракул мог бы определить — вызван ли он из анализируемой функции и из какого места (+ с какими параметрами).
…
глобальные переменные или нет — это уже детали реализации.Замечательно. Опустим все детали реализации. Считаем, что у оракула halts есть возможность узнать все, о чем вам хочется. Какой ответ он выдаст?
f(); func f() { if (halts(f)) { while(true) {} } }ibessonov
16.01.2019 16:39Извиняюсь, что вклиниваюсь в дискуссию, но всё-же внесу дополнение:
func f(g) { if (halts(g, g)) { while(true) {} } } f(f); //?
Всё-таки существование такой f, которая внутри ссылается на саму себя, совсем не очевидно.
vassabi
16.01.2019 16:42для оракула это не так важно, ваш вариант будет иметь тот же результат.
ibessonov
16.01.2019 16:46Я, к сожалению, не очень внимательно прочитал все комментарии. Вы говорили о какого-то рода контексте, передаваемом в «оракул» O, правильно? Можно более подробно об этом?
В классическом доказательстве предполагается существование функции `halts(f, input)`, возвращающей 1, если `f` останавливается на входе `input` и 0 в противном случае. Какие параметры стоит добавить?ibessonov
16.01.2019 17:061) передать значения, по которым оракул мог бы определить — вызван ли он из анализируемой функции и из какого места (+ с какими параметрами).
Мне действительно интересно, что это конкретно за значения и каким образом "оракул" будет валидировать, что они переданы правильно.
P.S. давайте не будем тут больше употреблять термин "оракул", он к делу ну вообще не относится.
vassabi
16.01.2019 17:25-1во-первых, оракул, как и любая функция, не сможет валидировать правильность. Он выполняет свой внутренний алгоритм.
Тот кто ему передает правильные параметры — тот получит правильные результаты.
ОК. оракул выкидываем. «Ффункция» (чтобы не путать с О-нотацией), подходит?ibessonov
16.01.2019 17:28Давайте просто говорить о функции `halts`, чтобы не было неясностей.
Какого рода параметры ей надо добавить? Давайте как-то зафиксируем, что они собой представляют, иначе предметного разговора не выйдет. Вы будете понимать под ними одно, а я — совершенно другое.vassabi
16.01.2019 17:52надо как-то зафиксироваться, а то тут просто спам пошел в ветках.
Я в одном месте halts(f) уже переиспользовал, чтобы он был немного слабее, чем теоретический оракул, а как сильный оракул была функция О(f, ctx).
… давайте вообще от halts уйдем к stops? чтобы не путаться и никого больше не путать.
(третий вариант правки ответа)
я тут долго писал разные варианты алгоритмов, и математические выкладки, но решил, что это все не понадобится, потому что мне не хочется спорить в неконструктивном ключе (т.е. когда непонятное что-то не может существовать. или может. но разницы нет — потому что вы не можете описать что у него внутри, только то, что снаружи).
Я хочу спорить в конструктивном направлении — вот алгоритм, используйте его, и будет вам счастье.
И моя (признаю — это профессиональная деформация) мысль состоит в том, что если у меня нереентерабельная функция, то я не страдаю от экзистенциального ужаса, а запоминаю контекст, и такие вызовы делаю отложенными, после чего все отлично работает (ибо нет рекурсии).
Поэтому мне стало странно, что математики так не умеют, я предложил «свой вариант», и дальше понесся угар и чад — и я в общем не ожидал такого спама в ветках, если честно…ibessonov
16.01.2019 18:06Пытаюсь понять, что такое "нереентерабельная" функция)
Смотрите, в чистом видеstops(f, input)невозможна — это факт, доказаный давным давно, и оспаривать его нет вообще никакого смысла. Главное сейчас — прояснить, почему добавление "контекста" не сделает задачу разрешимой. Давайте поймём, что за контекст передаётся.
Вариант 1 — помимо функции будет передано то, использует ли она внутри себя
stopsили нет. Информация может быть ложной, поэтому полагаться на неё без валидации нельзя, верно же?stopsвсегда должна отвечать корректно, независимо от контекста. Но — подобная валидация сама по себе алгоритмически невозможна.
Вариант 2 — даже не знаю, какие у вас были предложения? Я, как и писал ранее, не до конца понял всю идею с контекстом.
EDIT: прочитал комментарий в другой ветке. Вы предполагаете, что информация, в каком месте кода
fнаходится вызовstopsи полный стэк вызовов с состоянием всех переменных вам помогут, так?
Ответ — не помогут. Невозможно доказать, что параметр функцииstops(f, *)встречается в стэке вызовов, так как не существует алгоритма проверки эквивалентности функций, например.vassabi
16.01.2019 18:28нереентерабельная функция НРФ — которая не умеет работать с вызовами себя самой (или функцией, которая вызывает внутри себя НРФ и т.д.).
почему не поможет? Если там будет передаваться место в функции, то вот простой алгоритм:
1) мы принимаем контекст и функцию,
2) если контекст пустой — передаем функцию оракулу, получаем свой ответ.
3) если непустой — в переданной функции заменяем это место на 0 или 1, получаем две новых функции — передаем сами себе с пустым контекстом на вычисление. Если у вас конечная длина программы, то рано или поздно все такие места будут заменены на константы, и можно будет вычислить конкретные значения (да, это долго и неэффективно, но зато детерминированно).ibessonov
16.01.2019 18:40То есть, подытожим:
когда вы вызываетеstops(f, input, ()), вы подразумеваете, что еслиfвнутри используетstops, то она передаёт внутрь валидную информацию о том, как именно, т.е.fгрубо говоря создаёт копию себя,f0(i), в контексте которой i — это то, на что стоит заменить результат вызоваstops(f, input). Давайте для простоты считать, что хотя-быinputвсегда пустой, иначе с ума сойдём.
Во-первых, не слишком ли сильное требование для функции
f?
Во-вторых, ну получили мы какую-то версиюf0, у которой внутри гарантированно нет явного "вызова"stops. Ну как-бы и что с того? Стало проще доказать, что какой-то алгоритм остановится/не остановится? Я бы не сказал.
EDIT:
Если у вас конечная длина программы, то рано или поздно все такие места будут заменены на константы, и можно будет вычислить конкретные значения (да, это долго и неэффективно, но зато детерминированно).
Запускать программу, которая может выполняться бесконечно долго — плохая затея.
KodyWiremane
16.01.2019 20:14так как не существует алгоритма проверки эквивалентности функций
Кстати, а его принципиальная несуществуемость доказана? Как с этим бинарным оракулом.ibessonov
16.01.2019 21:14Ну смотрите, допустим есть функция, которая доказывала бы эквивалентность. Тогда строим следующие 2 функции:
f1() { f(input) return 1 } f2() { return 1 }
Если можно доказать их эквивалентность в общем случае, то
fостанавливается на входеinput, т.е. разрешима проблема остановки! А это не может быть правдой.KodyWiremane
16.01.2019 22:36Мне бы более развёрнутую формулировку — например, что за функция здесь подразумевается под f (и почему останавливается) и откуда берётся input. А то под этим постом столько f переопределено, что у меня глаза разбегаются. На первый взгляд, f1 и f2 эквивалентны, только если f внутри переливает из пустого в порожнее (по крайней мере, при заданном input, если это константа).
Так-то функция определения эквивалентности может помочь оракулу только установить факт того, что поток исполнения анализируемой функции зависит от обращения к самому оракулу (или его эквиваленту), но не избежать противоречия с if (halts(...)) loop_forever(). Разве что исключение выбросить…
P. S. Ну и в целом для кругозора интересно, что принято считать относительно существования алгоритма определения эквивалентности функций.ibessonov
16.01.2019 22:47В моём примере f — это какая-то произвольная функция, а input — какой-то её вход. Ведь проблема остановки — по произвольной функции и её входу определить, завершится ли она или нет.
f1 и f2 эквивалентны тогда и только тогда, когда f(input) отрабатывает за конечно время (не зависает). Это и влечёт за собой разрешимость проблемы остановки при условии, что эквивалентность функций алгоритмически разрешима.
Формулировку последнего предложения, если честно, не понял. Вопрос в том, как понимать «существование алгоритма» или в чём-то другом?KodyWiremane
16.01.2019 23:18Суть последнего предложения, как и первого моего комментария в этой ветке, такова: доказана ли невозможность существования алгоритма, определяющего эквивалентность двух функций в смысле отображения множества входных значений на множество выходных, и побочных эффектов.
Насколько я понял, проблема, стоящая перед «продвинутым» оракулом (вне контекста оригинальной задачи с бинарным оракулом) в том, чтобы определить, что влияющий на поток исполнения анализируемой функции вызов — это вызов этого же (или эквивалентного) оракула с той же функцией в качестве аргумента. Отсюда любопытство, возможен ли такой «продвинутый» оракул, или с вычислением эквивалентности функций тоже есть какое-то противоречие. Сугубо навскидку мне кажется, что возможно. С другой стороны, максимум, что он может — выкинуть исключение о невозможности принять решение. Так что только исключить функции, содержащие влияющий на поток вызов оракула, из множества допустимых значений на входе этого оракула.vassabi
17.01.2019 00:42доказана ли невозможность существования алгоритма, определяющего эквивалентность двух функций в смысле отображения множества входных значений на множество выходных, и побочных эффектов.
увы, вот тут пишут, что если такая функция существует, то из нее можно будет построить оракул
vassabi
16.01.2019 16:45в этом коде он внутри функции f вернет 0
Dim0v
16.01.2019 16:49+1И будет неправ, потому что функция f в таком случае завершится. А для функции которая завершается, правильный ответ — 1. Оракул не работает.
vassabi
16.01.2019 18:07снаружи функции он вернет 1.
внутри он вернет 0.
как сделать такую функцию — есть множество вариантов.
Меня лично больше всего огорчает, что математики придумали пример «для опровержения».
Для меня он звучит так что: «давайте сделаем такую операцию, чтобы если ее применить к числу — то результат умноженный сам на себя будет равен первоначальному числу». А потом сразу же «но если ему подать на вход число -1, то мы не сможем получить -1, потому что число умноженное само на себя — всегда положительное. Так что нет такой операции, ЧТД».
Со стороны это кажется смешным…Dim0v
16.01.2019 18:48снаружи функции он вернет 1.
внутри он вернет 0.Не никакого снаружи и внутри. Вызов ровно один. Ответ на него неправильный.
Со стороны это кажется смешным…
Неудивительно. Потому что ваша аналогия ни разу не аналогична и вы, по всей видимости, тоже не понимаете, как работает доказательство от противного.
vassabi
16.01.2019 19:04Не никакого снаружи и внутри. Вызов ровно один.
возможно в математике такого пока нет. Может и есть, но я не разобрался.
Но вот в программах — такое точно есть и даже есть разница (и ее можно найти и нейтрализовать во время выполнения функции, собственно я даже подобными вещами занимался на практике).Dim0v
16.01.2019 19:10Вы молодец, что умеете работать со стеком вызовов. Но сейчас речь об одной конкретной программе. Не о математике. В этой одной конкретной программе есть только один вызов оракула. С одним контекстом. С одним стеком вызовов. Других вызовов оракула нет. И в этом единственном вызове оракул возвращает неправильное значение.
Hardcoin
17.01.2019 11:25Оракул на вход принимает текст. Если оракулу, который запущен в песочнице, передать текст такой программы, что он выдаст? Если я верно вас понял, это то, что вы называете "снаружи". И он выдаст 1.
Что ж, в таком случае мы берём нашу программу и запускаем halts в песочнице, так, что бы он не смог узнать, что его результат будет использовать другая программа (песочница возможна, думаю тут сомнений нет). Она принимает 1 и зацикливается. Видите проблему?
Вы полагаете, что оракулу нужен контекст. Но нет никакой проблемы написать функцию f, которая будет создавать чистый контекст, как будто оракул запущен "снаружи". Дело в том, что для такой программы (которая подделывает контекст) оракул тоже должен выдавать верный ответ, иначе это не универсальный ответ. А как он выдаст верный, если контекст подделан? Только анализируя текст программы. А когда он его анализирует (просто текст), он не знает, изнутри он запущен или снаружи (мы же контекст подделали с помощью нашей программы f). Значит и изнутри и снаружи он должен выдать один и тот же ответ.
vassabi
17.01.2019 11:41Вопрос про «подделку» контекста очень хороший. Конечно, если он неявный и доступен только для чтения, то такой проблемы можно избежать, но это заслуживает отдельного внимания, да.
Так же, вполне возможно, что при передаче неполного контекста, то он не сможет вычислить свой результат верно.
Однако же для внешнего вызова оракула (т.е. если ему передать и песочницу и правильный контекст), это не будет критично — он сможет правильно вычислить, что песочница с таким внутренним устройством зациклится.
Hardcoin
17.01.2019 11:49Нашел более простую проблему в вашем оракуле. Он снаружи вернёт 1, так?
Берём ваш оракул и немного подправим. Он снаружи для этой программы будет возвращать 0, а изнутри — 1. Будете ли вы считать такой оракул тоже верным? Если нет, то почему?
vassabi
17.01.2019 12:01Он тоже верный, но для детерминированности лучше задать, что он вернет снаружи «зацикливается», только если функция действительно зацикливается, при любых значениях оракула внутри функции (и в случае когда их там нет).
Так что простой ответ: конечно можно подправлять. Просто интерпретация значений 0 и 1 поменяется (т.е. 0 — это будет остановится, 1 — зациклится).
Hardcoin
17.01.2019 11:11пока что с этим есть небольшая заминка
Нет, с этим заминки нет. Доказательство 100% верное. Даже если в моих объяснениях что-то не так, вы всегда можете прочитать более формальное доказательство. Заминка только рассказать вам на пальцах, почему оно верное.
Для того чтобы дать правильный ответ — зациклится ли некая функция f или нет.
Хорошо. Так функция f зациклится или нет?
vassabi
17.01.2019 11:21доказательство несуществования оригинального оракула я и не оспариваю. Он был сконструирован, чтобы несуществовать — и это несуществование легко доказывается.
У меня заминка с оракулом, у которого нет доказательства несуществования, и который сконструирован так, чтобы опровержение оригинального оракула на нем не работало. И теперь я пытаюсь доказать для себя его наличие (или доказать отсутствие, это тоже будет хорошо).
Так функция f зациклится или нет?
Это уже к оракулу. Пусть лучше компьютер считает числа, а не люди.
kuldiegor Автор
15.01.2019 18:46Здравствуйте. Давайте я попробую объяснить на вашем примере.
func f() {
if (halts(f)) {
while(true) {
}
}
}
Предположим halts(f)вернул true, что это true означает, вам не известно до тех пор, пока алгоритм работает.
Предположим halts(f)вернул false, что это false означает, вам не известно до тех пор, пока алгоритм работает.
Если внутри вашего алгоритма дать значение будущего до того, как ваш алгоритм завершится, алгоритм попытается его опровергнуть.
Поэтому первый оракул вернёт ответ, который для алгоритма не будет иметь значение до тех пор, пока его (ответ) не соотнести с другим значением.
Например halts(f) вернул true. Алгоритм завис. Другой оракул дал обозначение этому true как бесконечное выполнение.
Например halts(f) вернул false. Алгоритм завершился. Другой оракул дал обозначение этому false как конечное выполнение алгоритма.
Причём оракул не всегда возвращает один и тот же результат. Но его ответы не будут противоречить реальности.
По сути, я пытался скрыть от алгоритма будущее, которое запрашивал от оракула алгоритм.Dim0v
15.01.2019 18:53Как я уже говорил, размазывание вычисления значения по нескольким функциям ничего не меняет. Эти несколько функций все равно можно вызвать из проверяемого кода и получить их противоречивый ответ. Как вы будете "скрывать будущее" от следующего кода? Вводом третьего кузена-оракула, который тоже сможет инвертировать значение первых двух братьев?
func f() { if (halts(f) xor should_invert_halts(f)) { while(true) {} } }vassabi
15.01.2019 19:11пожалуйста, можете вводить и кузена.
Но если halts будет получать свой контекст, то можно будет сделать такого оракула, который будет корректно отвечать на вопрос «остановится ли этот алгоритм» для внешнего наблюдателя.Dim0v
15.01.2019 19:55отвечать на вопрос «остановится ли этот алгоритм» для внешнего наблюдателя.
Ваш вариант отвечает не на этот вопрос. А на вопрос "«остановится ли этот алгоритм» при неправильном ответе на вопрос «остановится ли этот алгоритм» для внутреннего наблюдателя".
vassabi
15.01.2019 21:24это уже ваша внутренняя функция, что хотите, то и делайте. Я не запрещаю вам даже от рандома логику работы запитывать.
а моя функция — она сконструирована, чтобы корректно отвечать на вопросы «зациклится ли ваша функция».Dim0v
16.01.2019 03:33а моя функция — она сконструирована, чтобы корректно отвечать на вопросы «зациклится ли ваша функция».
И она с этой задачей в общем случае не справляется. By design. Справляется только с некоторыми оговорками, о чем вы сами написали в ветке чуть выше.
С оговорками и "func halts(f, X) {return true;}" — оракул.
vassabi
16.01.2019 11:24моя оговорка состоит только в правильности передачи ей параметров.
Если вы передаете ей неправильные параметры, то и работать она будет неправильно.Dim0v
16.01.2019 12:55Если вы передаете ей неправильные параметры, то и работать она будет неправильно.
Я из функции f спрашиваю у оракула, завершится ли функция f. Входных данных у этой функции нет. Он должен вернуть правильный ответ на мой вопрос. Какой ответ он вернет? Какие из моих параметров неправильны?
vassabi
16.01.2019 14:37-1он вернет правильный ответ для вас.
Для функции f он будет возвращать различные числа (но не случайные, а такие, чтобы вызов оракула от f для вас вернул правильный ответ), которые могут как совпадать так и не совпадать с правильным ответом.Dim0v
16.01.2019 15:15+1он вернет правильный ответ для вас.
Для кого "нас"? Есть только один вызов оракула — изнутри функции f. Вот я и спрашиваю, какое значение он вернет. Конкретное значение. Без абстрактных "правильное", "строгое" и т.д.
vassabi
16.01.2019 15:36ОК.
уговорили. Вот вам оракул попроще.
Оракул halts
1) принимает один параметр: функцию.
2) возвращает:
0, если функция зациклится
1, если функция не зациклится
-1, если в функции используется halts( т.е. halts(halts) == -1)
С передачей контекста вычисления — можно было бы сделать и получше оракул, но раз вам оракул O не нравится — вот, можно halts.Dim0v
16.01.2019 15:43-1, если в функции используется halts( т.е. halts(halts) == -1)
Алгоритм работает либо конечное время, либо бесконечное. Третьего варианта быть не может. Если ваш "оракул" для каких-то случаев выдает третий вариант "не знаю", то это значит, что мы в очередной раз вернулись к тому, что ваш "оракул" — не оракул в общем случае и потому ничего не опровергает.
vassabi
16.01.2019 16:04Алгоритм работает либо конечное время, либо бесконечное. Третьего варианта быть не может.
не всякий алгоритм, а только построенный по определенным правилам. Также по этим правилам вы можете построить противоречивый оракул.
Однако, если вы можете также построить непротиворечивые оракулы, которые:
Оракул О попросит у вас передавать ему контекст.
или
оракул халт, который откажется вычислять самого себя. Если второй оракул для вас не оракул, тогда ОК, я не гордый — вычеркиваем.Hardcoin
16.01.2019 16:13Оракул второго типа сделать потенциально возможно (хотя легко показать, что если он возможен, то только один). Статья (и исходная теорема) о том, возможно ли сделать оракул первого типа. Который выдает не три варианта ответа, а только два.
Dim0v
16.01.2019 16:20Оракул О попросит у вас передавать ему контекст.
Я передал. Вот тут: https://habr.com/post/436090/#comment_19621830
Что вернет ваш оракул?
Если второй оракул для вас не оракул
Речь идет о конкретной задаче. В ней нужно определить, завершает ли алгоритм свое выполнение. Любой алгоритм либо завершается, либо нет. Он не может "завершаться наполовину". То, что вы решили задачу "определить, завершает ли алгоритм свое выполнение, или ответить хз" — это, конечно, круто. Но к исходной задаче это никакого отношения не имеет.
Hardcoin
16.01.2019 16:08Он и не планирует опровергать. Он предложил вам другой оракул "да/нет/не знаю". Такой оракул потенциально возможен. Конечно, с исходной теоремой он ничего общего не имеет, но рассмотреть такой измененный оракул ничего не запрещает (если кому-то интересно)
Dim0v
16.01.2019 16:23Я понимаю, что он предложил другой оракул. Но подавал он его, все же, именно в качестве опровержения моих слов :)
vassabi
16.01.2019 16:35другой оракул — слабее оргинального, согласен.
Я его давал в иллюстративных целях.
Перефразируя автора данной заметки — он «друг оракула», и защищает его от рекурсии :)
Sychuan
16.01.2019 21:43Насколько я помню оригинальное доказательство не включает в себя рекурсию.
vassabi
17.01.2019 01:15не просто включает, а именно на ней и строится.
Оригинальное доказательство разве что использует для этого диагонализацию, но суть та же самая.
kuldiegor Автор
15.01.2019 19:24В том то всё и дело что доступ к второму оракулу вы не имеете. Одновременно к двум оракулам доступ имеет только наблюдатель. Одновременно вызвать двух оракулов в одном алгоритме нельзя. Выше vassabi всё верно расписал про контексты.
vassabi
15.01.2019 19:26можно хоть три моих оракула вызывать, хоть рекурсивно — он спокойно с этим сможет разобраться (главное, чтобы их можно было хотя бы перенумеровать относительно мест вызовов).
Dim0v
15.01.2019 19:52доступ к второму оракулу вы не имеете
Почему? Если функция второго оракула должна быть невычислимой на машине Тьюринга, то вы только подтверждаете, что задача неразрешима. Если вычислима, то что мне мешает эту функцию реализовать?
Gribs
16.01.2019 00:11А у меня такой вопрос.
Понятно что невозможно создать оракул который бы работал для любой функции. Но описан ли класс функций для которых оракул создать можно? Конкретный пример, можно лио создать оракул для функций, которые не используют оракул в своих вычислениях?vassabi
16.01.2019 01:51можете посмотреть на примитивно-рекурсивные функции.
Цитируя википедию: «В терминах императивного программирования — примитивно рекурсивные функции соответствуют программным блокам, в которых используется только арифметические операции, а также условный оператор и оператор арифметического цикла (оператор цикла, в котором число итераций известно на момент начала цикла).»
Olorin111
15.01.2019 15:52«Оракул существует, но ему нужен брат» — от создателей «Колеса Бесслера» и «Батарейки Карпена».
acerikfy
Насколько я понял ваш поток мыслей, вы не доказали, что S1 либо S2 существуют. Без этого все еще алгоритма, решающего проблему останова.
Даже если посмотреть на предолженных вами оракулов, мы можем сконструировать вычислимую функцию, которая будет аналогичной той, что рассматривал Тьюринг в своей работе, и мы все еще получим противоречие.