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

    Или общий алгоритм по проблеме останова может существовать.
    Но, как всегда, есть нюансы.
    Если интересно прошу под кат.

    Введение


    В 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){
    }
    }


    Оба оракула вернут ноль что будет означать что алгоритм зависнет.

    В конце выполненных алгоритмов мы можем взять и соотнести данные тем самым получив ответ.
    Но есть еще один нюанс, все входные данные должны быть конечными. Ресурсы машины, также должны быть конечными. Если хоть что-то будет бесконечным, то гарантировать анализ оракулами за конечное время нельзя.

    Заключение


    Так как Алан Тьюринг доказал, что общего алгоритма быть не может, значит с большой долей вероятности в нашей теории кроется ошибка. Поэтому всех неравнодушных прошу в комментарии помочь найти такую ситуацию, которая бы смогла помочь решить текущую задачку.
    Share post
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 174

      +3
      Насколько я понял ваш поток мыслей, вы не доказали, что S1 либо S2 существуют. Без этого все еще алгоритма, решающего проблему останова.
      Даже если посмотреть на предолженных вами оракулов, мы можем сконструировать вычислимую функцию, которая будет аналогичной той, что рассматривал Тьюринг в своей работе, и мы все еще получим противоречие.
        +2
        Мелкие замечания
        1. Оракул — это черный ящик, а не обычный алгоритм или машина Тьюринга, который может делать что-то магическое. Например, мы не можем доказать что алгоритм не может вычислять X, т.к. это сложно, но можем доказать, что он не может вычислять X даже с оракулом.
        2. В английской википедии доказательство написано гораздо яснее. Доказательство Тьюринга тоже более понятное.
        3.
        Ресурсы машины, также должны быть конечными

        У машины Тьюринга бесконечная память, а у вас машина с конечной памятью, т.е. вроде как гораздо более слабая, способна решать проблему останова. А если у нее не хватит ленты для ввода? Как-то это подозрительно.
        4. «S1 возвращает 0 или 1 но что значат эти 0 или 1 неизвестно, об этом знает только второй оракул.» Мы можем узнать, что означают 1 и 0 после нескольких попыток от второго оракула. Почему они не могут быть одним алгоритмом? Зачем их два?
        5.
        Два оракула нужны для того, чтобы алгоритм получив данные от одного оракула не смог узнать о своём будущем

        Как алгоритм узнает будущее?
        По-моему у вас есть оракул, который отвечает может ли остановится алгоритм или нет. Это, конечно, может быть, но смысла в таком не очень много.

          +1

          "Размазывание" вычисления значения функции останова по "братьям", "сестрам" и прочим родственникам ничем не поможет.


          В вашем конкретном случае достаточно взять, например, две следующие программы, которые вообще игнорируют второго оракула и обращаются только к первому:


          If (оракул(N)==0){
            While(true){}
          }

          If (оракул(N)==1){
            While(true){}
          }

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


          Или же просто убрать это бессмысленное размазывание вот так:


          If (оракул1(N) xor оракул2(N) == 1){
            While(true){}
          }

          И получить ситуацию, полностью аналогичную ситуации с одним оракулом.

            +3

            Три ограничения нужны не для того, чтобы найти или потерять оракула.
            Это просто теорема Гёделя о неполноте в приложении к вычислительной технике.
            Чтобы не борзели от всемогущества.

              0
              Почему у Тюринга оракул останавливается и возвращает 1, если алгоритм N не останавливается? Почему не наоборот? Он сам это как-то обосновывает?
                +3

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


                Оракул и не должен зависать. Он должен говорить, останавливается ли программа, поданная ему на вход. Но если такой оракул существует, то становится возможным написать следующий код:


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

                Такой код противоречит сам себе. Если оракул говорит, что функция f останавливается, то условие if (halts(f)) будет истинным, следовательно — управление перейдет к строке с бесконечным циклом и функция не завершится. Получили противоречие. Если оракул говорит, что функция не завершится, то условие if (halts(f)) будет ложным и функция завершится сразу. Снова противоречие. Таким образом, исходное предположение (о том, что существует оракул, определяющий, завершается ли произвольный алгоритм за конечное время) было ложным.

                  +1
                  То есть доказательство ложности предположения основано на том, что выбранный язык программирования позволяет написать бессмысленный код?
                    +3

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

                      0
                      func f() {
                        while(true) {
                          if (halts(f)) {
                            return 'Завершится.'
                          }
                        }
                      }
                      


                      ?
                        +1

                        И? Что вы этим хотели сказать?


                        Что для этого кода противоречий нет? Да, их нет (любой ответ оракула будет правильным и непротиворечивым). Для многих алгоритмов решение проблемы останова вообще тривиально, как, например для "print('Hello world')" или "while(true) {}" и еще многих других. Но возможность создания оракула, который будет правильно работать для некоторых алгоритмов никак не доказывает существование решения для общего случая.

                          +1
                          Да, но возможность создания оракула, который будет не правильно работать для некоторых алгоритмов никак не доказывает не существование решения для общего случая.
                            +1

                            Так мы и не создаем "оракула, который будет не правильно работать для некоторых алгоритмов". Мы описали алгоритм, для которого ни один оракул не сможет дать корректный ответ.


                            Оракул в примере — это функция halts, а не f. Мы ее не создаем, а просто предполагаем ее существование (в виде черного ящика). Если она существует, то она должна корректно работать в том числе и для функции f из моего примера. Но она не может корректно работать для функции f. Из этого следует, что наше исходное предположение о существовании такой функции halts — ложно. Эта функция (оракул) не может существовать.

                              0
                              Оракул в примере — это функция halts, а не f.

                              Правильно. При этом и вас, и у меня она абсолютно одинаково говорит, остановится программа или нет.
                              При этом у вас вызывающая оракула функция начинает выполнять бесконечный цикл, а у меня набоборот — прекращает. Ни то, ни другое не доказывает ни возможность, ни невозможность реализации оракула.
                                0
                                она абсолютно одинаково говорит, остановится программа или нет

                                Уточните, пожалуйста, в примере Dim0v выше halts(f) должен вернуть true или false? Представьте себе абсолютно правильный оракул. Какой ответ на ваш взгляд он должен выдать, если у него спросить про f?

                                  0
                                  Вообще-то я пришёл сюда с близким вопросом: на основании чего сформулированы требования к оракулу? Вместо ответа я получил бессмысленный код, не реализующий никакого алгоритма. Это было настолько неожиданно, что я растерялся. Может быть фигню сморозил. Уж извините тогда.
                                  А что должен вернуть оракул? Ну давайте так — самозванцев нам не надо, ораклом буду я. Пусть я получил код и данные. Возможны 4 варианта:
                                  1. Я смотрю и ничего не понимаю — язык не знакомый. Я возвращаю «не понимаю» и перехожу к другим делам.
                                  2. Язык знакомый, я вижу, что выполнение программы никогда не закончится. Я так честно и говорю: «нет». И перехожу к другим делам.
                                  3. Вижу, что закончится —> «да». И перехожу к другим делам.
                                  4. Вижу противоречие. За это, как за шуллерство — канделябрами. И перехожу к другим делам.
                                  Я хотел узнать, почему из четырёх возможных действий выбрано только второе. Я не собираюсь опровергать теорему. Я и без математики знаю, что природа не алгоритмична.
                                    0
                                    Вообще-то я пришёл сюда с близким вопросом: на основании чего сформулированы требования к оракулу?

                                    Я вам ответил. Оракул должен определять, завершится ли выполнение алгоритма за конечное время. Всё. Сформулированы такие требования на основании описания задачи.


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

                                    Не "вместо", а "вместе" с ответом. И не "бессмысленный код, не реализующий никакого алгоритма", а код, демонстрирующий невозможность существования такого оракула. Любой код реализует какой-то алгоритм. А вопросы про "осмысленность" и "бессмысленность" алгоритмов — это к философам.


                                    Возможны 4 варианта:

                                    Нет. Код либо работает конечное время, либо бесконечное. Других вариантов нет. И оракул, если он существует, должен давать правильный ответ


                                    почему из четырёх возможных действий выбрано только второе.

                                    Покажите, пожалуйста, где именно кто-то кроме вас производит выбор из ваших 4 действий и где именно кто-то выбирает именно второе из них?

                                      0

                                      Да никто не выбрал второе. Наоборот, второй ответ не подходит. Потому что если оракул ответит нет, то программа из-за этого завершится. И независимый свидетель скажет — ваш оракул ошибся, видите? Он сказал "нет, не завершится", а программа завершилась.


                                      А считать, что машина Тьюринга "мошенничает", это как-то странно.


                                      Судя по вашему ответу, вы считаете, что оракул должен выдавать один из трёх ответов (вариант "это не код" отметаем, он не интересен).


                                      1. Да, завершится.
                                      2. Нет, не завершится.
                                      3. Мошеннический код, ответ не возможен.

                                      Так вот, теорема о том, возможен ли оракул с двумя видами ответов? "Завершится/не завершится". Ведь логика подсказывает, что даже "мошеннический" код либо завершится когда-нибудь, либо не завершится никогда, не так ли? Разве может быть третий вариант?


                                      Но вы и сами видите — нет, такой оракул невозможен. Возможен только оракул с тремя вариантами ответов. Да, нет, "идите отсюда". А с двумя — невозможен. Это не хорошо, не плохо, просто так есть.

                                        0
                                        язык программирования позволяет написать бессмысленный код?

                                        Язык знакомый

                                        язык не знакомый


                                        Что вы к языку привязались то? Задача не про языки, а про алгоритмы.
                                        Тьюринг-полный там язык, который позволяет написать любую ахинею в рамках доступной архитектуры. Asm, brainfuck, basic, хоть js, суть задачи от этого не меняется.

                                        А суть приводимых вам алгоритмов в том, что для доказательства невозможности написать алгоритм разбирающий любую программу, достаточно привести хотябы один пример программы, для которой написание такого алгоритма невозможно.
                                          –1
                                          Никаких алгоритмов мне не приводили. Мне привели код, который рализует (якобы) алгоритм, который не может существовать.
                                            +2
                                            Вы гуманитарий? Это какая-то неспособность к абстрактному мышлению.
                                              –1
                                              func f() {
                                                if (halts(f)) {
                                                  while(true) {}
                                                }
                                              }

                                              Может быть господин минусёр просветит меня — какой алгоритм реализует код, который даже откомпилировать нельзя (функция halts не определена)?
                                                +1

                                                Так ведь этот код пишется исходя из предположения, что функция halts уже реализована. И возникшее противоречие говорит нам о том, что предположение о существовании halts было неверным.
                                                (минусовал не я, просто решил ответить)

                                                  –1
                                                  Правильно. Но это не значит, что не существует алгоритм, который она вроде бы реализует. Тут возможны два варианта — или он действительно не существует, или не возможна эта конкретная реализация. Мы-то знаем, что второе ­— следствие первого, но из совсем другого источника и доказывается несуществование алгоритма совсем по-другому — непосредственно для алгоритма, без каких-либо попыток реализации в коде.
                                                  Реализация алгоритма в коде всегда конкретна. На конкретном языке, для конкретной операционной системы, процессора, … Теория алгоритмов этим всем не интересуется.
                                                  Короче, эти ускоренные/упрощённые методы доказательства годятся только для запудривания мозгов пятиклассницам.
                                                    +1
                                                    или не возможна эта конкретная реализация

                                                    Какая конкретная реализация? Ее где-то видите только вы. Никто ее в этой ветке не рассматривал.


                                                    доказывается несуществование алгоритма совсем по-другому — непосредственно для алгоритма, без каких-либо попыток реализации в коде.

                                                    Да. Именно поэтому никто из приводящих классическое доказательство этой проблемы от противного и не рассматривал никакие конкретные реализации функции оракула в коде. Я даже больше скажу. Алгоритмы оракула тоже не рассматривались. Рассматривалась только возможность или невозможность существования такого алгоритма.


                                                    Какие-то детали реализации здесь рассматривали только люди, не согласные по каким-то причинам с доказательством Тьюринга. То вводили какие-то контексты (все равно не помогающие вернуть правильный ответ), то требовали чтобы основная функция была реализована с помощью двух независимых вспомогательных функций (что тоже ничем не помогало в решении поставленной проблемы), то еще что-то.


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

                                                    В том то и дело, что значит. Потому что см. предыдущие 2 пункта.


                                                    эти ускоренные/упрощённые методы доказательства годятся только для запудривания мозгов пятиклассницам.

                                                    Вот как.


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


                                                    П.С.

                                                    Я тоже вас не минусовал. Минусовать (как и плюсовать, впрочем) никого мне карма не позволяет.

                                                      –1
                                                      Какая конкретная реализация? Ее где-то видите только вы.

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

                                                      Этот «один из самых распространенных видов математического доказательства» не предполагает нарушение закона тождества. Вы предполагаете существование функции, а вывод делаете об алгоритме. Подмена понятия.
                                                      Да, функция не существует, вы это доказали, спасибо. Алгоритм тоже не существует, но доказали это не вы и совсем по-другому.
                                                        0
                                                        Вы лжёте. Это именно вы здесь написали, что любая фунуция реализует алгоритм.

                                                        У вас какая-то каша в голове, честное слово. Я написал


                                                        Любой код реализует какой-то алгоритм

                                                        Да, это так. Любой компилируемый код и любой псевдокод, каким бы бессмысленным он кому-то не казался, реализует какой-то алгоритм (каким бы бессмысленным он тоже не казался).


                                                        Где в этих словах конкретная реализация алгоритма оракула (функции halts)?


                                                        Вы предполагаете существование функции, а вывод делаете об алгоритме. Подмена понятия.

                                                        Какой смысл вы вкладываете в слово "функция"?


                                                        Любой алгоритм предполагает наличие набора (возможно пустого) входных, выходных данных и набора неких операций, определяющих поведение алгоритма (получение выходных данных из входных).


                                                        Для функции halts предполагается наличие ровно этих вещей и никаких других.


                                                        Да, функция не существует, вы это доказали, спасибо

                                                        Не я, а Тьюринг. Я лишь привел его доказательство. Не за что.


                                                        Алгоритм тоже не существует, но доказали это не вы

                                                        Да, не я. Тьюринг. А чем алгоритм halts отличается от функции halts — одному вам известно.


                                                        и совсем по-другому.

                                                        Да нет, точно так же, как и я. Только он еще строго формализовал понятие алгоритма, придумав для этого машину Тьюринга. Но на высоком уровне доказательство — ровно такое же доказательство от противного, как и у меня.

                                                  +1
                                                  Алгори́тм (лат. al­go­rithmi — от арабского имени математика Аль-Хорезми[1]) — конечная совокупность точно заданных правил решения произвольного класса задач или набор инструкций, описывающих порядок действий исполнителя для решения некоторой задачи.

                                                  Компилируемость не является определяющим свойством алгоритма.
                                                  Конкретный код реализует алгоритм выполнения функцией бесконечного цикла, для некоего «оракула» который определит данную функцию как выполняемую за конечный промежуток времени.
                                                  Алгоритм != программа != псевдокод.
                                                  Пресловутое 'нанести->смыть->повторить' на шампунях тоже алгоритм, хотя не одно из действий не прописано в существующих языках программирования.
                                          +1
                                          Это не вызывающая оракула функция, это функция которая подается оракулу. Суть в том, что оракул — это тоже программа. И да, в данном примере ему предлагают проверить самого себя.
                                          И вам объясняют, что если оракул допустить, что оракул существует, то в данном примере получается логическое противоречие. Значит, его не существует. Это называется доказательство от противного. То что вы можете подобрать непротиворечивый пример, никто и не спорит. Заканчивайте тупить.
                                            +1
                                            При этом у вас вызывающая оракула функция начинает выполнять бесконечный цикл, а у меня набоборот — прекращает.

                                            Да. И еще в моем случае при этом возникает логическое противоречие, а в вашем — нет.


                                            Ни то, ни другое не доказывает ни возможность, ни невозможность реализации оракула.

                                            Ваш пример — да, ничего не доказывает. Мой доказывает невозможность существования (не реализации) оракула.


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


                                            Почитайте о том, как работает доказательство от противного.

                                          +2

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


                                          Представьте себе человека, который делает оракула. А второй проверяет, работает ли оракул. Так вот, второй всегда сможет написать такую программу, что бы оракул первого выдал неверный результат. То есть первый никогда не сможет сделать достаточно хорошего оракула.
                                          Именно это и называется "не существует решения для общего случая".

                                    +1

                                    Бессмысленный для вас? Я бы хотел посмотреть на Тьюринг-полный язык, который НЕ позволил бы написать бессмысленный код.


                                    Это особенность всех доказательств (и в математике тоже) — они рассматривают не "смысл", а целостность. В данном случае рассматривается, существует или не существует такая "бессмысленная" программа. Она существует, из нее следует, что оракул невозможен.

                                    0
                                    очевидно, что в Х еще входит и контекст вызова функции. Т.е. если вы вызовете
                                    halts(f) то это не то же самое, что вы вызовете f() который внутри себя вызовет halts(f).
                                    А если передавать контекст, то у вас она вернет 1 (т.е. halts(f,()) это 1 ), потому что изнутри f она вернет 0 (т.е. halts(f,(f)) это 0 ), и все будет корректно.
                                      0
                                      очевидно, что в Х еще входит и контекст вызова функции

                                      В Х входят только входные данные проверяемой функции. Если функция как-то использует контекст своего вызова, то да, он входит в Х. В данном случае функция f работает абсолютно одинаково, независимо от того, в каком контексте она вызвана. Так что для нее контекст вызова в Х не входит. Значение функции-оракула по определению также не должно зависеть от контекста вызова. Оно зависит только от проверяемого алгоритма, его входных данных и ни от чего больше.


                                      Понятно, что можно описать (да что там, даже реализовать) поведение halts так, чтобы в данном конкретном примере она возвращала что-то непротиворечивое (своей внутренней логике). Но это будет не функция-оракул, а что-то другое.


                                      Кстати,


                                      А если передавать контекст, то у вас она вернет 1 (т.е. halts(f,()) это 1 ), потому что изнутри f она вернет 0 (т.е. halts(f,(f)) это 0 ), и все будет корректно.

                                      А почему не наоборот?

                                        +1
                                        Но это будет не функция-оракул, а что-то другое.

                                        в смысле не оракул-функция? Она не будет вычислять «остановится ли функция f» для пустого контекста (т.е. для математика)?

                                        А почему не наоборот?

                                        потому что эта функция зациклится же.
                                        можно и наоборот (0 снаружи, 1 внутри) — заметьте, от этого истинность результата не поменяется.
                                          0
                                          Она не будет вычислять «остановится ли функция f» для пустого контекста (т.е. для математика)?

                                          Повторюсь. Поведение функции f не зависит от контекста. Контекст не входит в Х. Поведение оракул-функции тоже не зависит от контекста. Для одних и тех-же данных она должна давать один и тот-же правильный ответ.


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

                                            0
                                            Поведение оракул-функции тоже не зависит от контекста. Для одних и тех-же данных она должна давать один и тот-же правильный ответ.
                                            Мой строгий оракул для одного и того же контекста будет выдавать один и тот же ответ.
                                            Но правильным его можно будет назвать только для случая, когда когда он вызван снаружи относительно функции (т.е. с пустым контекстом).
                                            Когда же он вызван внутри анализируемой функции, он не будет ни правильным, ни неправильным — он может возвращать как и совпадающий, так и не совпадающий с правильным ответом результат (потому что он будет не ответом, а частью решения, и т.о. нацеленным на правильность ответа).
                                              0
                                              Но правильным его можно будет назвать только для случая, когда когда он вызван снаружи относительно функции (т.е. с пустым контекстом).
                                              Когда же он вызван внутри анализируемой функции… он может возвращать как и совпадающий, так и не совпадающий с правильным ответом результат

                                              То есть он не будет корректным оракулом в общем случае. Ч.т.д.


                                              Не говоря уже о том, что у вашего оракула может не быть возможности определить, "снаружи" он вызван или "изнутри".
                                              Анализируемая функция может быть сконструирована так, что внутри нее ваш оракул будет вызван точно таким же образом, каким предусмотрен его вызов снаружи. С таким-же "контекстом", если хотите.

                                                –1
                                                вы придумываете функции, чтобы «сломать» оракул, а я придумываю оракул, который нельзя поломать при правильном использовании.
                                                В принципе, можно не требовать «передавать контекст» внутрь оракула явно, просто дайте ему доступ к состояниям той машины, на которой его вычисляют — он сможет тогда получить доступ к контексту сам.
                                                  +1
                                                  я придумываю оракул, который нельзя поломать при правильном использовании.

                                                  Нет "неправильного" использования. Вызов оракула должен давать ответ на вопрос, завершится ли переданный ему алгоритм. Всегда. Без исключений и оговорок. Кроме непосредственно алгоритма (в виде строки, если хотите) и его входных данных, доступа у оракула ни к чему нет. Ваш оракул не сможет определить, вызвали ли его "изнутри" или "извне".


                                                  дайте ему доступ к состояниям той машины, на которой его вычисляют

                                                  Пожалуйста. Вот состояние машины, на которой его запускают. Выполняется вот этот код.


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

                                                  Текущая инструкция обозначена с помощью >. Какой результат вернет ваш оракул в данном вызове?

                                                    0
                                                    Нет «неправильного» использования.

                                                    Среда выполнения алгоритма тоже является частью алгоритма. Для примера: вы можете сделать функцию W, которая будет эмулировать машину тьюринга и на ней запустить оракула O, который будет смотреть на f(), в которой будет вызываться O и т.д. ad infinitum. Но если вы будете вычислять значения O(W), то для правильной работы оракул должен знать: он внутри W или снаружи W.

                                                    Когда-то в математике нельзя было записать длину диагонали квадрата. Или такое число, чтобы оно давало отрицательные числа при умножении самого на себя, так что когда-то это были такие функции «с оговорками». А теперь все пишут квадратные корни, числа пи, мнимые единицы и прочая и прочая.
                                                    Может, если добавить что-то в аксиомы, и будет оракул «в общем виде», а пока — так.
                                                      0
                                                      Но если вы будете вычислять значения O(W), то для правильной работы оракул должен знать: он внутри W или снаружи W.

                                                      Пусть знает. В моем примере выше оракул знает, в какой среде он запущен. Какое значение он вернет в месте своего вызова? Такое место одно. Оракул вызывается один раз и должен вернуть ровно одно значение. Какое?


                                                      а пока — так.

                                                      То есть, если отбросить философствования об истории математики, то мы снова возвращаемся к тому, что оракул в общем виде все таки существовать не может.


                                                      Может, если добавить что-то в аксиомы

                                                      Что? И в какие аксиомы?

                                                        0
                                                        для halts — я в другой ветке написал.

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

                                                        где в данном случае ctx = (f, 0), и при таких значениях своих входных параметров он вернет 0.

                                                        UPD: в те аксиомы, на основании которых у вас вычисления происходят. Есть же аксиомы стереометрии, аксиоматика теории множеств или вещественных чисел и т.д.
                                                        А вот знал бы что (в короткой форме, без выводимых из других аксиом частей) — то писал бы не на хабр.
                                                          0
                                                          у вас неправильный пример.
                                                          Должен быть
                                                          if (O(f, ctx)) {

                                                          Ок.


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

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

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

                                                            два верных результата, плюс функция f счастливо завершается.
                                                              0
                                                              O(f, ctx) = 1 при 0 при ctx = (f, 0)

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


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

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


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

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

                                                                0
                                                                там небольшая опечатка, правильно так:
                                                                O(f, ctx) = 1 при ctx = () и
                                                                O(f, ctx) = 0 при ctx = (f, 0)

                                                                и т.д.

                                                                если вы хотите в символьных выражениях, тогда можно в частном случае развернуть в такой код:

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

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


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


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

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

                                                                    0
                                                                    ответ оракула вам будет равен 1, как и полагается при вызове O(f, ()).
                                                                    Если вы вызывали O(f, (f, 0)), то он вернет правильный, но непригодный для вас ответ.
                                                                      +1

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

                                                                        –2

                                                                        я не запрещаю называть вам белое синим, а шляпу — женой (и наоборот).

                                                                        Но мне все-таки любопытно: почему вы решили, что он не работает?
                                                                          +1
                                                                          Потому что возвращает 'непригодный' (aka 'невалидный') результат?
                                                                            –1
                                                                            а вы ей передали на вход валидный результат?
                                                                            (и чтобы не отвечать вопросом на вопрос, а то это все-таки дурной тон).
                                                                            Я перечислил варианты результатов функции от входных параметров. Оба — валидные, но каждый — на смоем месте вызова. Уверен, что вы не ошиблись с передачей параметров и получили корректный ответ.
                                                                              0

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


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

                                                                                PS: Возможно, это и есть та новая аксиома, которой не хватает для непротиворечивых оракулов… надо думать.
                                                                                  0
                                                                                  просто передайте ему ctx.

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

                                                                                    0
                                                                                    ответ: вычисленное на основании переданных параметров.
                                                                                    А если вы все параметры внутри предавали правильно, то и оракул от функции+пустой ctx вернет свой вердикт — зациклится она или нет.
                                                                                      0
                                                                                      А если вы все параметры внутри предавали правильно,

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

                                                                                        0
                                                                                        оракул будет работать для всех функций, кроме тех, где его вызовут с неверными параметрами.

                                                                                        Сделайте функцию, которая будет работать от положительных чисел, я вам туда передам отрицательное и все вместе будем ходить вокруг да около: «правильная или неправильная» и т.д.
                                                                                          0

                                                                                          Ответ моей функции в таком случае будет неправильным. Как и неправильный ответ вашего оракула. А значит моя функция не работает в общем случае. Как и ваш оракул.

                                                                                            0
                                                                                            в общем случае контекстов (всяких, в том числе некорректных) — она не работает.
                                                                                            Но если контекст относительно f будет корректный, тогда она сработает для данного f.
                                                                                +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.
                                                                                И в данном случае и возникает противоречие.
                                                                              +1

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


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

                                                                                –1
                                                                                оракула вызвала функция внутри себя от определенных параметров, она получила свой результат.
                                                                                если вызвать оракул извне, то оракул получит другие значения на вход и вернет другой (а возможно и такой же) результат.
                                                                                  +1
                                                                                  Давайте я тут переспрошу — «оракул» валидирует эти значения? Если нет, то что нас обязывает заранее передавать туда правильный ответ? Не вижу ни одной причины для этого.
                                                                                  Сейчас же ваш аргумент сводится к простому «скажите оракулу сами, останавливаетесь вы или нет».
                                                                                    –1
                                                                                    т.к. вы отказались от переменной ctx, я вам назвал конкретные значения.
                                                                                    Теперь вам не нравится что конкретные значения — конкретные… Тогда передавайте контекст и будет вам общий случай.
                                                                                      +1
                                                                                      Я пытаюсь понять, что представляет собой контекст. Вот прям конкретно — это какое-то число или какая-то функция?
                                                                                        –1
                                                                                        вот сейчас попробую «прям конкретно» сформулировать (хотя и не смогу претендовать на корректность, но мы же для этого и спорим тут не так ли — чтобы уточнить формулировки ):
                                                                                        это функция, которая возвращает (функция, в которой был вызван оракул + параметры фунцкции + место в функции из которого вызван оракул + значения внутренние переменные к даному времени + итерация вызова если в цикле), вот как-то так.
                                                                                          +1

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


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

                                                                                          f


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

                                                                                          ()


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

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


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

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


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

                                                                                          не в цикле.


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

                                                                                            –1
                                                                                            ответ оракула — с этими параметрами мне нужно вернуть значение противоположное оракулу с пустым контекстом, по соглашению — у него должно быть 1 (если возможны оба варианта), так что я возвращаю 0. конец.
                                                                                              +1
                                                                                              я возвращаю 0. конец.

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

                                                                                                –1
                                                                                                почему неправильным?
                                                                                                Он не тот же самый, что для пустого контекста — это да.
                                                                                                  +1
                                                                                                  Да, господи.
                                                                                                  f();
                                                                                                  func f() {
                                                                                                    if (O(f, ())) {
                                                                                                      while (true) {}
                                                                                                    }
                                                                                                  }
                                                                                                  

                                                                                                  Этот код зависнет при выполнении или нет?
                                                                                                  Мы вызвали f с пустым контекстом.
                                                                                                  Если код зависает, значит оракул сказал что f с пустым контекстом не зависнет = соврал.
                                                                                                  Если код не зависает, значит оракул сказал что f с пустым контекстом зависнет = опять соврал.
                                                                                                  В чём проблема-то? Откуда у вас там наблюдатели и контексты? Это программирование, а не квантовая физика, в конце концов. Тут есть два варианта 0 либо 1.
                                                                                                  А у вас оракул пытается маскироваться под квант, и возвращать разное значение в зависимости от того смотрю я на него или нет.
                                                                                                  Просто подумайте, зависнет ли тупо запущенный кусок кода и почему.
                                                                                                    –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);}
                                                                                                    не так ли?

                                                                                                    Если вы вставите внутрь своей функции некорректный вызов моей функции — то это не опровергает и не доказывает ничего (нк, кроме того что мы друг друга так и не поняли ...)
                                                                                                      +1
                                                                                                      К чему столько текста? Приведённый кусок кода из 6 строчек зависнет или нет?
                                                                                                        –1
                                                                                                        чтобы вы поняли, что вы мне предлагаете находить производную от функции:
                                                                                                        f(x) = x +*-xх

                                                                                                        «Все значки правильные? да, правильные. Так найдите производную! Что, не получается? Значит у вас противоречие!»
                                                                                                        и так по кругу… эх!
                                                                                                        Лучше буду тратить свое время на комментарий ibessonov про диагонализацию и стеки — так оно гораздо более продуктивно будет использоваться…
                                                                                                          +1
                                                                                                          Какие к чёрту производные?
                                                                                                          Программа либо может выполниться за конечное время либо не может. Нет никакого третьего состояния. Если программа сразу падает с ошибкой — она выполняется за конечное время. Если в программе цикл без проверок и выходов — она зависает. Если в коде jmp start; без условий то код зависнет.
                                                                                                          Программа абсолютно валидна с точки зрения логики и синтаксиса.
                                                                                                          В чём проблема определить завершится она или нет? Какие, к чёрту, производные?
                                                                                                            –1
                                                                                                            все символы правильные, вычислите мне производную по х:
                                                                                                            f(x) = x +*-xх

                                                                                                            а может найдете логарифм от -1 в вещественных числах? А как насчет последнего цифры в десятичной записи числа пи?

                                                                                                            Соревноваться в «кто задаст больше некорректных вопросов» — извините, без меня.

                                                                                                            Программа, которую вы написали — невалидна с точки зрения постановки задачи, ее результат ничего не доказывает и не опровергает.
                                                                                                              +2
                                                                                                              В 1936 году Алан Тьюринг доказал, что нет общего алгоритма, анализирующего другие алгоритмы и указывающий, будет зависать программа или нет.

                                                                                                              Чем она, блин, не валидна? Она не является алгоритмом?
                                                                                                              То что можно построить оракул который разбирает некоторые типы алгоритмов, никак не доказывает возможность построения оракула для всех алгоритмов и, в принципе, к исходной задаче никакого отношения не имеет.

                                                                                                              С таким подходом можно элементарно показать что существует оракул определяющий выполнимость любой задачи длинной не более одной команды. И что? Толку от такого оракула?

                                                                                                              Давайте назовём алгоритм приведённый в доказательстве Тьюринга, невалидным и разведём балаболию на 140 комментариев. Нет в условии задачи никакого понятия 'валидности'. Алгоритма анализирующиего другие алгоритмы не существует, а ваш пример не подходит под характеристики, т.к. из множества всех алгоритмов он требует исключить подмножество 'невалидных' характеристики и размер которых не известен. К чему весь трёп?
                                                                                                                –1
                                                                                                                К чему весь трёп?

                                                                                                                золотые слова.
                                                                                                                спасибо за внимание, хорошего вам дня.
                                                                            +1
                                                                            Это как? Мне подходит, например, любой правильный ответ, я не брезгливый.
                                                                              –1
                                                                              это так, что есть разница — вычисляется ли оракул рекурсивно или нет.
                                                                              Я предлагал либо дать доступ к контексту, либо вот — явно передавать контекст внутрь.
                                                                              Я тоже не брезгливый, мне все равно — передают внутрь функций верные или неверные значения.
                                                                              Просто я удивляюсь тому, что кто-то передает на вход мусор и удивляется, что на выходе — тоже мусор…
                                                                                +1
                                                                                вычисляется ли оракул рекурсивно или нет.

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


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

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

                                                                                  –1
                                                                                  если вы хотите узнать — есть зациклится ли f — то вы передаете ей "()", если вы хотите вызвать его внутри f, то передаете (это в данном случае. Если f — другая, то и значения второго параметра будут другими) "(f, 0)"
                                                                                    0
                                                                                    если вы хотите вызвать его внутри f

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

                                                                                      0
                                                                                      если вы внутри f вызвали его с параметрами (), то вызов его вне функции f с параметрами () будет возвращать 0.
                                                                                        0

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

                                                                                          0
                                                                                          а внутри функции он может не давать тех же ответов, что и снаружи функции — я об этом с самого начала писал.
                                                      +1

                                                      Внутри функции f — не ваш оракул. Там текст, полностью совпадающий с текстом вашего оракула. Если вам так проще, то скажу, что это не тот же самый объект, а другой. И этот объект должен по тексту решать — завершится программа или нет.


                                                      То есть вы должны не эту прогу починить, а оракул. Что бы он для любой проги смог дать ответ. Но к сожалению, невозможно. Любой оракул будет иногда ошибаться. Для общего случая он невозможен.

                                                        0
                                                        вы сейчас описали свои желания? хорошо, учтем.
                                                        Текст оракула, не текст оракула, моя функция или нет — если в нее передавать заданные параметры, то она вычисляет правильный ответ.
                                                          +1
                                                          если в нее передавать заданные параметры, то она вычисляет правильный ответ.

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


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

                                                            –2
                                                            вычисляет-вычисляет
                                                            habr.com/ru/post/436090/#comment_19622020

                                                            PS: извините, что передразниваю, но реально — по существу есть возражения?
                                                              +1

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

                                                                0
                                                                когда видно отступы — тогда я вижу, кому я отвечал, а кто — мне.
                                                                А когда ветка длинная — то я уже начинаю теряться, кто кому и что отвечал.

                                                                по существу, мы с вами так и топчемся на месте, но передать смысл своей идеи мне вам пока не удаётся, увы…
                                                                И все идёт к тому, что так и не получится.
                                                0

                                                Что значит, передать контекст? Вы имеете ввиду, что у функции должно быть два параметра? Или она должна обращаться к глобальным переменным? Ради чего? Задача не в том, что бы написать корректную функцию. Наоборот, задача в том, что бы написать НЕ корректную (но без ошибок), что бы оракул дал неверный ответ.


                                                Зачем? Что бы показать, что оракул сломан. И никто не сможет сделать работоспособный оракул, такой, что бы для любой программы смог дать ответ. Всегда можно написать программу такую, что оракул ошибётся.


                                                То есть рабочий оракул невозможен. Об этом и теорема.

                                                  0
                                                  Если ваша задача придумать такой оракул, который сломается — да пожалуйста. Можете сразу объявить, что вы придумали оракул 0, который выдает всегда 0 и поэтому можно написать правильную функцию, на которой он не работает.
                                                  Если ваша задача доказать, что «никто не сможет сделать работоспособный оракул, такой, что бы для любой программы смог дать ответ», то пока что с этим есть небольшая заминка.

                                                  Что значит, передать контекст? Вы имеете ввиду, что у функции должно быть два параметра? Или она должна обращаться к глобальным переменным? Ради чего?
                                                  а вот это уже хорошие вопросы.
                                                  1) передать значения, по которым оракул мог бы определить — вызван ли он из анализируемой функции и из какого места (+ с какими параметрами).
                                                  2) не у функции, а у оракула — да, два параметра
                                                  3) глобальные переменные или нет — это уже детали реализации.
                                                  4) Для того чтобы дать правильный ответ — зациклится ли некая функция f или нет.
                                                    +1
                                                    передать значения, по которым оракул мог бы определить — вызван ли он из анализируемой функции и из какого места (+ с какими параметрами).

                                                    глобальные переменные или нет — это уже детали реализации.

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


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

                                                      Извиняюсь, что вклиниваюсь в дискуссию, но всё-же внесу дополнение:


                                                      func f(g) {
                                                        if (halts(g, g)) {
                                                          while(true) {}
                                                        }
                                                      }
                                                      
                                                      f(f); //?

                                                      Всё-таки существование такой f, которая внутри ссылается на саму себя, совсем не очевидно.

                                                        0
                                                        для оракула это не так важно, ваш вариант будет иметь тот же результат.
                                                          0
                                                          Я, к сожалению, не очень внимательно прочитал все комментарии. Вы говорили о какого-то рода контексте, передаваемом в «оракул» O, правильно? Можно более подробно об этом?
                                                          В классическом доказательстве предполагается существование функции `halts(f, input)`, возвращающей 1, если `f` останавливается на входе `input` и 0 в противном случае. Какие параметры стоит добавить?
                                                            0
                                                            1) передать значения, по которым оракул мог бы определить — вызван ли он из анализируемой функции и из какого места (+ с какими параметрами).

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


                                                            P.S. давайте не будем тут больше употреблять термин "оракул", он к делу ну вообще не относится.

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

                                                              ОК. оракул выкидываем. «Ффункция» (чтобы не путать с О-нотацией), подходит?
                                                                0
                                                                Давайте просто говорить о функции `halts`, чтобы не было неясностей.
                                                                Какого рода параметры ей надо добавить? Давайте как-то зафиксируем, что они собой представляют, иначе предметного разговора не выйдет. Вы будете понимать под ними одно, а я — совершенно другое.
                                                                  0
                                                                  надо как-то зафиксироваться, а то тут просто спам пошел в ветках.
                                                                  Я в одном месте halts(f) уже переиспользовал, чтобы он был немного слабее, чем теоретический оракул, а как сильный оракул была функция О(f, ctx).

                                                                  … давайте вообще от halts уйдем к stops? чтобы не путаться и никого больше не путать.

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

                                                                  И моя (признаю — это профессиональная деформация) мысль состоит в том, что если у меня нереентерабельная функция, то я не страдаю от экзистенциального ужаса, а запоминаю контекст, и такие вызовы делаю отложенными, после чего все отлично работает (ибо нет рекурсии).
                                                                  Поэтому мне стало странно, что математики так не умеют, я предложил «свой вариант», и дальше понесся угар и чад — и я в общем не ожидал такого спама в ветках, если честно…
                                                                    0

                                                                    Пытаюсь понять, что такое "нереентерабельная" функция)
                                                                    Смотрите, в чистом виде stops(f, input) невозможна — это факт, доказаный давным давно, и оспаривать его нет вообще никакого смысла. Главное сейчас — прояснить, почему добавление "контекста" не сделает задачу разрешимой. Давайте поймём, что за контекст передаётся.


                                                                    Вариант 1 — помимо функции будет передано то, использует ли она внутри себя stops или нет. Информация может быть ложной, поэтому полагаться на неё без валидации нельзя, верно же? stops всегда должна отвечать корректно, независимо от контекста. Но — подобная валидация сама по себе алгоритмически невозможна.


                                                                    Вариант 2 — даже не знаю, какие у вас были предложения? Я, как и писал ранее, не до конца понял всю идею с контекстом.


                                                                    EDIT: прочитал комментарий в другой ветке. Вы предполагаете, что информация, в каком месте кода f находится вызов stops и полный стэк вызовов с состоянием всех переменных вам помогут, так?
                                                                    Ответ — не помогут. Невозможно доказать, что параметр функции stops(f, *) встречается в стэке вызовов, так как не существует алгоритма проверки эквивалентности функций, например.

                                                                      0
                                                                      нереентерабельная функция НРФ — которая не умеет работать с вызовами себя самой (или функцией, которая вызывает внутри себя НРФ и т.д.).

                                                                      почему не поможет? Если там будет передаваться место в функции, то вот простой алгоритм:
                                                                      1) мы принимаем контекст и функцию,
                                                                      2) если контекст пустой — передаем функцию оракулу, получаем свой ответ.
                                                                      3) если непустой — в переданной функции заменяем это место на 0 или 1, получаем две новых функции — передаем сами себе с пустым контекстом на вычисление. Если у вас конечная длина программы, то рано или поздно все такие места будут заменены на константы, и можно будет вычислить конкретные значения (да, это долго и неэффективно, но зато детерминированно).
                                                                        +1

                                                                        То есть, подытожим:
                                                                        когда вы вызываете stops(f, input, ()), вы подразумеваете, что если f внутри использует stops, то она передаёт внутрь валидную информацию о том, как именно, т.е. f грубо говоря создаёт копию себя, f0(i), в контексте которой i — это то, на что стоит заменить результат вызова stops(f, input). Давайте для простоты считать, что хотя-бы input всегда пустой, иначе с ума сойдём.


                                                                        Во-первых, не слишком ли сильное требование для функции f?
                                                                        Во-вторых, ну получили мы какую-то версию f0, у которой внутри гарантированно нет явного "вызова" stops. Ну как-бы и что с того? Стало проще доказать, что какой-то алгоритм остановится/не остановится? Я бы не сказал.
                                                                        EDIT:


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

                                                                        Запускать программу, которая может выполняться бесконечно долго — плохая затея.

                                                                          0

                                                                          Продолжу мысль в этой ветке. Итак, есть функция


                                                                          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
                                                                            он не запускает f, он запускает оракула, который пробует оба варианта — с 0 и с 1. Если там внутри нет оракулов, то оракул сможет вычислить результат (по определению оракула).
                                                                            Если там еще есть оракулы — тогда повторяем замену еще раз (т.е. удваиваем количество вариантов. но это не страшно т.к. у функции конечная длина).
                                                                            При этом не нужно считать все дерево — как только какой-то вариант дает ответ «остановится» — значит берем его (при этом каждый из оракулов сможет повторить эти действия, а свой ответ, т.е. индекс своего 0 или 1 — взять из своего контекста)
                                                                              0
                                                                              по определению оракула

                                                                              Просил же перестать употреблять этот термин, вы ведь даже не знаете, что такое "оракул" (edit: я понимаю, что это начал делать автор статьи, тем самым вводя читателей в заблуждение). stops — это просто какая-то функция, существование которой мы предполагаем. Абсолютно детерменированная.


                                                                              Вот пробуются оба варианта, с 0 и с 1, это равносильно анализу функции f0, разве нет?


                                                                              Пожалуйста, укажите на конкретное место в моих рассуждениях, которое кажется вам неверным. Либо распишите всю свою цепочку рассуждений для приведённой мною функции так же подробно, как это сделал я, спасибо!

                                                                                0
                                                                                не за что, всегда пожалуйста. Я тут пока брал перерыв на подумать, и я думаю, что у меня должен получиться наглядный пример идеи:
                                                                                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: И напоследок — по идее так можно будет преобразовать (т.е. чтобы вместо рекурсии был вызов внешней функции) любые вычислимые машиной тьюринга функции (например чтобы каждый шаг был внутри такой обертки). Это будет огромное, но конечно число для перебора.
                                                                                (хмм… чем-то похоже на пошаговый дебаг программы)
                                                                                  0
                                                                                  чтобы вместо рекурсии был вызов внешней функции

                                                                                  Извините, я не понимаю, где вы нашли рекурсию.


                                                                                  А теперь по делу:


                                                                                  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) и то, что с этим потом делать. Тщательно всё это проанализировать и уже потом делать выводы. Сейчас же в ваших рассуждениях слишком много несостыковок и их слишком сложно понять из-за отсутствия внятно введённых понятий.

                                                                        0
                                                                        так как не существует алгоритма проверки эквивалентности функций
                                                                        Кстати, а его принципиальная несуществуемость доказана? Как с этим бинарным оракулом.
                                                                          0

                                                                          Ну смотрите, допустим есть функция, которая доказывала бы эквивалентность. Тогда строим следующие 2 функции:


                                                                          f1() {
                                                                              f(input)
                                                                              return 1
                                                                          }
                                                                          f2() {
                                                                              return 1
                                                                          }

                                                                          Если можно доказать их эквивалентность в общем случае, то f останавливается на входе input, т.е. разрешима проблема остановки! А это не может быть правдой.

                                                                            0
                                                                            Мне бы более развёрнутую формулировку — например, что за функция здесь подразумевается под f (и почему останавливается) и откуда берётся input. А то под этим постом столько f переопределено, что у меня глаза разбегаются. На первый взгляд, f1 и f2 эквивалентны, только если f внутри переливает из пустого в порожнее (по крайней мере, при заданном input, если это константа).

                                                                            Так-то функция определения эквивалентности может помочь оракулу только установить факт того, что поток исполнения анализируемой функции зависит от обращения к самому оракулу (или его эквиваленту), но не избежать противоречия с if (halts(...)) loop_forever(). Разве что исключение выбросить…

                                                                            P. S. Ну и в целом для кругозора интересно, что принято считать относительно существования алгоритма определения эквивалентности функций.
                                                                              0
                                                                              В моём примере f — это какая-то произвольная функция, а input — какой-то её вход. Ведь проблема остановки — по произвольной функции и её входу определить, завершится ли она или нет.

                                                                              f1 и f2 эквивалентны тогда и только тогда, когда f(input) отрабатывает за конечно время (не зависает). Это и влечёт за собой разрешимость проблемы остановки при условии, что эквивалентность функций алгоритмически разрешима.

                                                                              Формулировку последнего предложения, если честно, не понял. Вопрос в том, как понимать «существование алгоритма» или в чём-то другом?
                                                                                0
                                                                                Суть последнего предложения, как и первого моего комментария в этой ветке, такова: доказана ли невозможность существования алгоритма, определяющего эквивалентность двух функций в смысле отображения множества входных значений на множество выходных, и побочных эффектов.

                                                                                Насколько я понял, проблема, стоящая перед «продвинутым» оракулом (вне контекста оригинальной задачи с бинарным оракулом) в том, чтобы определить, что влияющий на поток исполнения анализируемой функции вызов — это вызов этого же (или эквивалентного) оракула с той же функцией в качестве аргумента. Отсюда любопытство, возможен ли такой «продвинутый» оракул, или с вычислением эквивалентности функций тоже есть какое-то противоречие. Сугубо навскидку мне кажется, что возможно. С другой стороны, максимум, что он может — выкинуть исключение о невозможности принять решение. Так что только исключить функции, содержащие влияющий на поток вызов оракула, из множества допустимых значений на входе этого оракула.
                                                                                  0
                                                                                  доказана ли невозможность существования алгоритма, определяющего эквивалентность двух функций в смысле отображения множества входных значений на множество выходных, и побочных эффектов.

                                                                                  увы, вот тут пишут, что если такая функция существует, то из нее можно будет построить оракул
                                                                                    0
                                                                                    доказана ли невозможность существования алгоритма, определяющего эквивалентность двух функций в смысле отображения множества входных значений на множество выходных, и побочных эффектов.

                                                                                    Да, доказана. Например, в моём комментарии, доказательство там банальное.


                                                                                    P.S. в общем случае "побочные эффекты" это просто часть выходного значения, никакого специального отношения к себе они не требуют. Все функции в наших рассуждениях всегда чистые.

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

                                                                                      У нас на курсе матлогики и нормальные алгоритмы Маркова и машины Поста с Тьюрингом были, все эти вещи еще и на курсе дискретной математики переразобраны и т.д. Пролог (до эрланга руки не дошли, сорри), хаскель, лисп — все понятно и про побочные эффекты с чистыми функциями тоже.
                                                                                      Но у меня с самого начала и до сих пор удивляет, что хотя разница между «прочитать код» и «выполнить код» есть — ее использование нигде я не встретил.
                                                                                      Меня самого заинтересовало то, что на практике-то у меня кроме побочных эффектов, есть еще и «контекст выполнения» алгоритма, а в теории — нет…

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

                                                                                        Давайте уточним — в доказательстве для машин Тьюринга рекурсии нет. Вот точно нет, в принципе как явления (edit: естественно, имеется ввиду рекурсия как вызов подпрограммы. Нигде не требудется явно вызов halts внутри halts или что-то подобное). Если не верите или хотите, чтобы я подробнее расписал, то скажите)


                                                                                        удивляет, что хотя разница между «прочитать код» и «выполнить код» есть — ее использование нигде я не встретил

                                                                                        Ну как же, функция halts принимает как параметр, условно говоря, "программный код", но она его не выполняет, а именно анализирует.


                                                                                        на практике-то у меня кроме побочных эффектов, есть еще и «контекст выполнения» алгоритма, а в теории — нет

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

                                                                                        0
                                                                                        Перечитал, осмыслил. Печалька.
                                                                                        С другой стороны, возможно, максимально полная частичная функция эквивалентности (область определения не включает функции, вызывающие логическое противоречие) может быть весьма общим решением?
                                                                                        push reality;
                                                                                        call logical_contradiction;
                                                                                          0
                                                                                          максимально полная частичная функция эквивалентности
                                                                                          … может быть весьма общим решением?

                                                                                          Весьма размытые понятия. Ясное дело, что в частных случаях или для определённых классов функций можно доказывать эквивалентность, но в общем случае — нет.


                                                                                          "Функции, вызывающее противоречие" — это инструмент доказательства от противного. В реальности же все рассматриваемые алгоритмы всегда детерминированы. Соответственно, противоречий в них никаких нет.

                                                                                            0
                                                                                            В реальности же все рассматриваемые алгоритмы всегда детерминированы. Соответственно, противоречий в них никаких нет.
                                                                                            Что ж, слава оракулу для практического общего случая х)

                                                                                            По идее, этот «практичный оракул» O должен отказаться от анализа «неправильной» функции F, соответствующей условиям:
                                                                                            — граф потока управления F содержит подграф O', эквивалентный графу потока управления O;
                                                                                            — поток управления F уходит в бесконечный цикл в зависимости от инвертированного значения на выходе O'.

                                                                                            Но тут у меня проблемы с осознанием как минимум того, как, собственно, может происходить это определение эквивалентности кусков алгоритма. Особенно почему-то пугает возможная рекурсия.

                                                                                            Задача останова — штука любопытная, я аж на диване подпрыгнул, но т. к. не обладаю компетенцией для сколь-нибудь глубокого анализа, тут я, наверное, и сойду ).
                                                            0
                                                            в этом коде он внутри функции f вернет 0
                                                              +1

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

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

                                                                как сделать такую функцию — есть множество вариантов.

                                                                Меня лично больше всего огорчает, что математики придумали пример «для опровержения».
                                                                Для меня он звучит так что: «давайте сделаем такую операцию, чтобы если ее применить к числу — то результат умноженный сам на себя будет равен первоначальному числу». А потом сразу же «но если ему подать на вход число -1, то мы не сможем получить -1, потому что число умноженное само на себя — всегда положительное. Так что нет такой операции, ЧТД».
                                                                Со стороны это кажется смешным…
                                                                  +1
                                                                  снаружи функции он вернет 1.
                                                                  внутри он вернет 0.

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


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

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

                                                                    0
                                                                    Не никакого снаружи и внутри. Вызов ровно один.
                                                                    возможно в математике такого пока нет. Может и есть, но я не разобрался.

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

                                                                      Вы молодец, что умеете работать со стеком вызовов. Но сейчас речь об одной конкретной программе. Не о математике. В этой одной конкретной программе есть только один вызов оракула. С одним контекстом. С одним стеком вызовов. Других вызовов оракула нет. И в этом единственном вызове оракул возвращает неправильное значение.

                                                                    0

                                                                    Оракул на вход принимает текст. Если оракулу, который запущен в песочнице, передать текст такой программы, что он выдаст? Если я верно вас понял, это то, что вы называете "снаружи". И он выдаст 1.


                                                                    Что ж, в таком случае мы берём нашу программу и запускаем halts в песочнице, так, что бы он не смог узнать, что его результат будет использовать другая программа (песочница возможна, думаю тут сомнений нет). Она принимает 1 и зацикливается. Видите проблему?


                                                                    Вы полагаете, что оракулу нужен контекст. Но нет никакой проблемы написать функцию f, которая будет создавать чистый контекст, как будто оракул запущен "снаружи". Дело в том, что для такой программы (которая подделывает контекст) оракул тоже должен выдавать верный ответ, иначе это не универсальный ответ. А как он выдаст верный, если контекст подделан? Только анализируя текст программы. А когда он его анализирует (просто текст), он не знает, изнутри он запущен или снаружи (мы же контекст подделали с помощью нашей программы f). Значит и изнутри и снаружи он должен выдать один и тот же ответ.

                                                                      0
                                                                      Вопрос про «подделку» контекста очень хороший. Конечно, если он неявный и доступен только для чтения, то такой проблемы можно избежать, но это заслуживает отдельного внимания, да.

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

                                                                      Нашел более простую проблему в вашем оракуле. Он снаружи вернёт 1, так?


                                                                      Берём ваш оракул и немного подправим. Он снаружи для этой программы будет возвращать 0, а изнутри — 1. Будете ли вы считать такой оракул тоже верным? Если нет, то почему?

                                                                        0
                                                                        Он тоже верный, но для детерминированности лучше задать, что он вернет снаружи «зацикливается», только если функция действительно зацикливается, при любых значениях оракула внутри функции (и в случае когда их там нет).

                                                                        Так что простой ответ: конечно можно подправлять. Просто интерпретация значений 0 и 1 поменяется (т.е. 0 — это будет остановится, 1 — зациклится).
                                                                          0
                                                                          Просто интерпретация значений 0 и 1 поменяется

                                                                          Не уходите от вопроса. Мой оракул выдает 1, если программа остановится, и выдает 0, если не остановится. Для программы f "снаружи" он выдает ноль.


                                                                          Мой оракул верный? Не что "лучше для детерминированности", а верный или нет. Для всех остальных программ он выдает точно такой же ответ, как и ваш.


                                                                          Если вы считаете ваш оракул (который выдает снаружи 1) правильным оракулом, а мой — неправильным, то почему?

                                                                            0
                                                                            хм, в принципе, если поменять базовую установку (т.е. по умолчанию стремиться к зацикливанию, а не к останову), то в принципе возможен и ваш вариант.
                                                                            Заранее облегчу (или утяжелю, может у вас не та задумка, о которой я предполагаю:) ) вам будущий вопрос:
                                                                            оракул(оракул, «снаружи») = 1 (т.е. остановится).
                                                                0
                                                                пока что с этим есть небольшая заминка

                                                                Нет, с этим заминки нет. Доказательство 100% верное. Даже если в моих объяснениях что-то не так, вы всегда можете прочитать более формальное доказательство. Заминка только рассказать вам на пальцах, почему оно верное.


                                                                Для того чтобы дать правильный ответ — зациклится ли некая функция f или нет.

                                                                Хорошо. Так функция f зациклится или нет?

                                                                  0
                                                                  доказательство несуществования оригинального оракула я и не оспариваю. Он был сконструирован, чтобы несуществовать — и это несуществование легко доказывается.

                                                                  У меня заминка с оракулом, у которого нет доказательства несуществования, и который сконструирован так, чтобы опровержение оригинального оракула на нем не работало. И теперь я пытаюсь доказать для себя его наличие (или доказать отсутствие, это тоже будет хорошо).

                                                                  Так функция f зациклится или нет?
                                                                  Это уже к оракулу. Пусть лучше компьютер считает числа, а не люди.
                                                                    0

                                                                    Уход от темы. Оракул не существует просто потому, что не существует ответа. Компьютер будет "считать числа" или человек — не важно. Нельзя сконструировать программу, которая сможет дать ответ на вопрос, если ответ не существует в принципе. Если хотите углубиться в тему — прочитайте про парадоксы. Про брадобрея, который брил всех, кто не брился сам, как самый простой пример.

                                                                      0
                                                                      теория считает цифры?
                                                                      может быть брадобреи, множества или матлогика считает цифры?
                                                                      или парадоксы считают цифры?

                                                                      нет, цифры считают люди, при помощи своих инструментов, и для решения своих практических задач — придумывают новые множества, законы логики, множества, парадоксы и т.д.
                                                                      Корень из двух, пи, логарифмы, комплексные числа — это все исторические примеры, когда реальные задачи «не помещались» в старых теориях.

                                                                      Так что я никоим образом не покушаюсь на классическую машину тьюринга и проблему останова в ней.
                                                                      У меня совершенно другая задача, которую можно по разному сформулировать, можно остановиться на такой постановке: какая должна быть модификация машины тьюринга, в которой такой оракул можно было бы получить (т.е. доказать его непротиворечивость)?
                                                                        0
                                                                        какая должна быть модификация машины тьюринга, в которой такой оракул можно было бы получить

                                                                        Для этого понятие алгоритма нужно сужать, а не расширять. К слову — расширить его никто ни разу не смог, см. тезис Чёрча.

                                                                          0
                                                                          теория считает цифры?

                                                                          Вы сначала вводите в разговор цифры, а когда я говорю, что это не существенно, кидаете вот такие возражения. Я их, честно говоря, совсем не понял.


                                                                          Если вы хотите модифицировать не оракул, а машину Тьюринга — ноль проблем. Конечно возможны и другие машины с другими правилами. Другое дело, что в формальных науках интересны строго формальные системы (что очевидно), а не описательные. Но пожалуйста, если вам интересно. В конце-концов и Тюнинг и фон-Нейман эти системы просто придумали и никакого запрета придумывать другие — не существует.


                                                                          А разговор о проблеме останова для классической машины Тьюринга, думаю, завершён.

                                                              –1
                                                              Здравствуйте. Давайте я попробую объяснить на вашем примере.
                                                              func f() {
                                                              if (halts(f)) {
                                                              while(true) {
                                                              }
                                                              }
                                                              }

                                                              Предположим halts(f)вернул true, что это true означает, вам не известно до тех пор, пока алгоритм работает.
                                                              Предположим halts(f)вернул false, что это false означает, вам не известно до тех пор, пока алгоритм работает.
                                                              Если внутри вашего алгоритма дать значение будущего до того, как ваш алгоритм завершится, алгоритм попытается его опровергнуть.
                                                              Поэтому первый оракул вернёт ответ, который для алгоритма не будет иметь значение до тех пор, пока его (ответ) не соотнести с другим значением.
                                                              Например halts(f) вернул true. Алгоритм завис. Другой оракул дал обозначение этому true как бесконечное выполнение.
                                                              Например halts(f) вернул false. Алгоритм завершился. Другой оракул дал обозначение этому false как конечное выполнение алгоритма.
                                                              Причём оракул не всегда возвращает один и тот же результат. Но его ответы не будут противоречить реальности.
                                                              По сути, я пытался скрыть от алгоритма будущее, которое запрашивал от оракула алгоритм.
                                                                0

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


                                                                func f() {
                                                                  if (halts(f) xor should_invert_halts(f)) {
                                                                    while(true) {}
                                                                  }
                                                                }
                                                                  +1
                                                                  пожалуйста, можете вводить и кузена.
                                                                  Но если halts будет получать свой контекст, то можно будет сделать такого оракула, который будет корректно отвечать на вопрос «остановится ли этот алгоритм» для внешнего наблюдателя.
                                                                    0
                                                                    отвечать на вопрос «остановится ли этот алгоритм» для внешнего наблюдателя.

                                                                    Ваш вариант отвечает не на этот вопрос. А на вопрос "«остановится ли этот алгоритм» при неправильном ответе на вопрос «остановится ли этот алгоритм» для внутреннего наблюдателя".

                                                                      0
                                                                      это уже ваша внутренняя функция, что хотите, то и делайте. Я не запрещаю вам даже от рандома логику работы запитывать.
                                                                      а моя функция — она сконструирована, чтобы корректно отвечать на вопросы «зациклится ли ваша функция».
                                                                        0
                                                                        а моя функция — она сконструирована, чтобы корректно отвечать на вопросы «зациклится ли ваша функция».

                                                                        И она с этой задачей в общем случае не справляется. By design. Справляется только с некоторыми оговорками, о чем вы сами написали в ветке чуть выше.


                                                                        С оговорками и "func halts(f, X) {return true;}" — оракул.

                                                                          0
                                                                          моя оговорка состоит только в правильности передачи ей параметров.
                                                                          Если вы передаете ей неправильные параметры, то и работать она будет неправильно.
                                                                            0
                                                                            Если вы передаете ей неправильные параметры, то и работать она будет неправильно.

                                                                            Я из функции f спрашиваю у оракула, завершится ли функция f. Входных данных у этой функции нет. Он должен вернуть правильный ответ на мой вопрос. Какой ответ он вернет? Какие из моих параметров неправильны?

                                                                              –1
                                                                              он вернет правильный ответ для вас.
                                                                              Для функции f он будет возвращать различные числа (но не случайные, а такие, чтобы вызов оракула от f для вас вернул правильный ответ), которые могут как совпадать так и не совпадать с правильным ответом.
                                                                                +1
                                                                                он вернет правильный ответ для вас.

                                                                                Для кого "нас"? Есть только один вызов оракула — изнутри функции f. Вот я и спрашиваю, какое значение он вернет. Конкретное значение. Без абстрактных "правильное", "строгое" и т.д.

                                                                                  0
                                                                                  ОК.
                                                                                  уговорили. Вот вам оракул попроще.
                                                                                  Оракул halts
                                                                                  1) принимает один параметр: функцию.
                                                                                  2) возвращает:
                                                                                  0, если функция зациклится
                                                                                  1, если функция не зациклится
                                                                                  -1, если в функции используется halts( т.е. halts(halts) == -1)

                                                                                  С передачей контекста вычисления — можно было бы сделать и получше оракул, но раз вам оракул O не нравится — вот, можно halts.
                                                                                    0
                                                                                    -1, если в функции используется halts( т.е. halts(halts) == -1)

                                                                                    Алгоритм работает либо конечное время, либо бесконечное. Третьего варианта быть не может. Если ваш "оракул" для каких-то случаев выдает третий вариант "не знаю", то это значит, что мы в очередной раз вернулись к тому, что ваш "оракул" — не оракул в общем случае и потому ничего не опровергает.

                                                                                      0
                                                                                      Алгоритм работает либо конечное время, либо бесконечное. Третьего варианта быть не может.
                                                                                      не всякий алгоритм, а только построенный по определенным правилам. Также по этим правилам вы можете построить противоречивый оракул.
                                                                                      Однако, если вы можете также построить непротиворечивые оракулы, которые:
                                                                                      Оракул О попросит у вас передавать ему контекст.
                                                                                      или
                                                                                      оракул халт, который откажется вычислять самого себя. Если второй оракул для вас не оракул, тогда ОК, я не гордый — вычеркиваем.
                                                                                        0

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

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

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


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


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

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

                                                                                          0

                                                                                          Он и не планирует опровергать. Он предложил вам другой оракул "да/нет/не знаю". Такой оракул потенциально возможен. Конечно, с исходной теоремой он ничего общего не имеет, но рассмотреть такой измененный оракул ничего не запрещает (если кому-то интересно)

                                                                                            0

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

                                                                                              0
                                                                                              другой оракул — слабее оргинального, согласен.
                                                                                              Я его давал в иллюстративных целях.

                                                                                              Перефразируя автора данной заметки — он «друг оракула», и защищает его от рекурсии :)
                                                                                                0
                                                                                                Насколько я помню оригинальное доказательство не включает в себя рекурсию.
                                                                                                  0
                                                                                                  не просто включает, а именно на ней и строится.
                                                                                                  Оригинальное доказательство разве что использует для этого диагонализацию, но суть та же самая.
                                                                                                    0
                                                                                                    использует для этого диагонализацию,

                                                                                                    Я это имел в виду
                                                                        –1
                                                                        В том то всё и дело что доступ к второму оракулу вы не имеете. Одновременно к двум оракулам доступ имеет только наблюдатель. Одновременно вызвать двух оракулов в одном алгоритме нельзя. Выше vassabi всё верно расписал про контексты.
                                                                          –1
                                                                          можно хоть три моих оракула вызывать, хоть рекурсивно — он спокойно с этим сможет разобраться (главное, чтобы их можно было хотя бы перенумеровать относительно мест вызовов).
                                                                            +1
                                                                            доступ к второму оракулу вы не имеете

                                                                            Почему? Если функция второго оракула должна быть невычислимой на машине Тьюринга, то вы только подтверждаете, что задача неразрешима. Если вычислима, то что мне мешает эту функцию реализовать?

                                                                        0
                                                                        А у меня такой вопрос.

                                                                        Понятно что невозможно создать оракул который бы работал для любой функции. Но описан ли класс функций для которых оракул создать можно? Конкретный пример, можно лио создать оракул для функций, которые не используют оракул в своих вычислениях?
                                                                          0
                                                                          можете посмотреть на примитивно-рекурсивные функции.
                                                                          Цитируя википедию: «В терминах императивного программирования — примитивно рекурсивные функции соответствуют программным блокам, в которых используется только арифметические операции, а также условный оператор и оператор арифметического цикла (оператор цикла, в котором число итераций известно на момент начала цикла).»
                                                                      0
                                                                      «Оракул существует, но ему нужен брат» — от создателей «Колеса Бесслера» и «Батарейки Карпена».
                                                                        0
                                                                        Пока читал, возникла такая идея, искомый оракул может выдавать только 2 ответа (завершится/не завершится), но нигде не прописано, что у оракула нет права зависнуть. Таким образом, наш общий алгоритм просто должен зависать, если встретит в тексте программы вызов самого себя, выполняя при этом формальные требования к оракулу.
                                                                        Что думаете по этому поводу?
                                                                          0
                                                                          так ведь по определению оракула — он должен на себе выдавать либо 0 либо 1. Если он на самом себе зависает — то значит определение не работает.
                                                                          Вот вам пример на пальцах: «треугольник — это фигура с тремя углами» — по определению. Строим треугольник, крутим-вертим его и тут внезапно у нашей фигуры четыре угла, т.е. — она неудовлетворяет своему же определению.
                                                                            0
                                                                            плохая аналогия, так как зависание это не результат, в то время как 4-ый угол это такой же угол, как и предыдущие 3.
                                                                              0

                                                                              Да, в вашем случае мы скорее крутим треугольник и внезапно обнаруживаем, чтот одна из его сторон — не отрезок, а дуга окружности. Да, такой "треугольник" позволит обойти какие-то ограничения "обычного" треугольника (например, сумму углов в 180 градусов). Но только этот "треугольник с дугой" — не треугольник. И к исходной задаче про трегольник (какая бы она ни была) имеет такое же отношение, как и зависающий оракул к исходной проблеме останова.

                                                                            0
                                                                            Мы не можем заранее знать, существование вызова функции оракула в программе. Поэтому не можем знать, он завис при выполнении анализа, или просто долго выполняет анализ. По сути, мы вернулись обратно к вопросу: «Будет ли алгоритм выполняться за конечное время или зависнет».
                                                                              0

                                                                              Зависание — это будет точно такой же ответ "не знаю", как и возврат -1. Немного более хитро сформулированный, да. Но сути это не меняет.
                                                                              Любой алгоритм либо завершается за конечное время, либо не завершается. Третьего варианта нет. Оракул должен давать ответ, к какому из этих двух вариантов относится переданный ему алгоритм. Если он этот ответ не дает (не важно из-за чего: из-за возврата "третьего" значения, из-за зависания или из-за уничтожения вселенной), то этот оракул не работает. Во всяком случае в рамках исходной задачи. Для какой-то другой задачи, где для оракула ответ "не знаю" является допустимым — да, зависание прекрасный способ сообщить о незнании.

                                                                            Only users with full accounts can post comments. Log in, please.