Здравствуйте, Sinclair, Вы писали:
S>В общем, NP-complete решение не интересно совсем.
Оно либо NP-complete, либо неразрешимо. Просто потому-что любую NP-полную задачу можно решить простым перебором с размером начального состояния O(n). Впрочем наверное и вообще ограничением по памяти тоже O(n).
Коммерчески может и неинтересно, а академически — еще как. Это все-таки более обширный класс задач. И если окажется, что они все эквивалентны NP — это очень круто.
Да и даже принципиальная разрешимость — тоже круто. Там же вроде много всего завязано на неразрешимости, надо будет все пересматривать.
Здравствуйте, Sinclair, Вы писали:
S> ·>Сабж не для минимальных известных примеров, а для общего случая. На вход подаётся произвольный код и для него надо определить сабж. S> Непонятно, почему вы противопоставляете общему случаю "минимальные известные примеры". S> Непонятно, как именно на практике вы собрались "подать на вход произвольный код".
На практике он именно такой и будет, за исключением нескольких тривиальных случаев. Ты не сможешь на практике проверить 2^64 состояний на цикличность. Уже где-то на 2^40 время работы будет многие годы. В лучшем случае, статический анализатор будет находить какие-то известные паттерны по базе типичных багов, которую забили разработчики. И честно отвечать "не знаю", если ничего не смог найти. Т.е. это не алгоритм для решения сабжа, а просто алгоритм поиска по базе.
S> В МТ это возможно — но это математика, там "существуют" такие штуки, как программы бесконечной длины.
Может где-то и существуют в математике, но не в контексте сабжа и МТ. Так что в оффтоп не уходи.
S> ·>Есть множество задач, которые алгоритмически эквивалентны проблеме остановки. Так вот, твоя задача "укладывается ли код в конечное число состояний" — эквивалентна сабжу. S> Я такую задачу не ставил. Я говорю о машинах, которые "похожи" на Машину Тьюринга примерно также, как регистры процессора — на целые числа. S> То есть ещё до того, как мы начали рассматривать какой-либо код, мы уже знаем, что пространство состояний — конечно.
Т.е. они не похожи, а подклассы сложности МТ. Например, регекспы — это КА, и по определению завершается всегда (правда иногда могут захапать экспоненциально много памяти и обломить твой детектор циклов). Да, это полезно, но полезность довольно ограниченная.
S> ·>Бинго! Ровно то же с твоим ограничением по памяти. Надо было просто дать ещё один байтик, и программа бы успешно остановилась. S> Невозможно "дать ещё один байтик" программе, в которой адресация памяти сделана при помощи 32х-разрядных указателей.
Т.е. есть умалчиваемое тобою физическое ограничение на кол-во планок памяти. Ровно так же невозможно дать ещё одну секундочку, если у тебя есть физическое ограничение на время, например, от батарейки комп работает. Ещё раз повторюсь — ограничение ресурсов, что по времени, что по памяти — эквивалентные подходы с тем же итогом.
S> ·>Именно! Ты ошибся утверждая, что "достаточно проверить её на "машине" с памятью размером 264". Нет. Не достаточно даже для x86. S> Достаточно, если программа не собирается общаться по сети.
Ну во-первых, в современном мире такую программу ещё надо поискать. Во-вторых, а как узнать, что она не собирается? Вдруг вирус какой, который упорно скрывает свои сетевые действия.
S> ·>Ты игнорируешь третью альтернативу "не влезло в твоё произвольное ограничение по памяти". S> Что значит "не влезло"? Как вы себе это представляете?
Что программа проверила для значений до 2^64, но не может выполнить алгоритм для значения 2^64+1 и _узнать_ результат работы.
S> ·>Ты исподтишка подменяешь исходную задачу и вместо решения для данной задачи "a^n+b^n==c^n" ты выдаёшь решение для "a^n+b^n==c^n, n<2^64". Но это не даёт ничего для решения данной задачи. S> Не исподтишка, а вполне открыто. Мне кажется, что от вашего внимания ускользает важный факт — на реальной машине эту задачу перебором решить невозможно. В принципе.
Почему ты так решил-то, что в принципе? Вот задачу четырёх красок решили перебором. Если мы поперебирали чего-то — и таки нашли решение, то нам просто повезло. А если перебор не нашел решения, то мы ничего не знаем, и решение неизвестно. Никакие циклодетекторы нам не помогут. Т.е. твой циклодетектор (и любой другой алгоритм) будет давать не два ответа, как ты обещаешь, а три: "да", "нет", "хз".
S> А решаемость этой задачи на воображаемой машине сама по себе не очень интересна — потому, что решение-то тоже воображаемое.
В смысле "вооброжаемое"? Вполне конкретное. Либо четыре вполне конкретных конечных числа, либо "не существует таких чисел". Никакие бесконечности тут не нужны. Требуется выдать результат в виде "да, есть такие 4 числа", "нет таких чисел". Очень конкретно, ничего воображать не надо.
S> S>> Можно сделать вывод о том, что я плохо объяснил вам принцип работы детектора циклов. S> ·>Да я знаю это, алгоритм черепахи и зайца называется или вроде того. S> Но почему-то вам кажется, что я предлагаю анализировать программы для МТ, а не программы для ограниченных машин.
Не для ограниченных машин в принципе (каждая машина может иметь разные ограничения), а для данной конкретной машины. Притом ответ уже заранее известен — на данном компе любой алгоритм остановится, т.к. кол-во ресурсов ограничено. Твой анализатор только лишь детектит определённый паттерн поведения и обнаруживает цикл состояний и в _некоторых_ случаях может выдать ответ с меньшим расходом ресурсов, чем тупой полный прогон проги. Т.е. это просто алгоритм обнаружения циклов. Сабж он не решает.
Здравствуйте, ·, Вы писали:
g>> Сабж то как раз и требуется доказать или опровергнуть. ·>Так он доказан, лет сто назад уж. Доказан как строгая математическая теорема.
Так собственно топик про то, что доказан не убедительно и предлагается найти более убедительное доказательство без парадоксов с бесконечностями.
Собственно я даже не понял, причем тут вообще бесконечности, но предложил предположительно-эквивалентную формулировку без них.
Здравствуйте, Sinclair, Вы писали:
S>Поздравляю, вы напоролись на контр-интуитивное поведение бесконечностей. S>Все доказательства проблемы останова неявно содержат в себе предположение о том, что как программа, так и её состояние, никак не ограничены по размеру.
Так, стоп. А причем здесь вообще бесконечности?
Если программа конечного размера и она завершается, она завершается спустя конечное время.
Для заданного начального размера программ существует такое число M, что все программы, если они завершаются, то завершаются за меньшее число шагов.
Соответственно, анализатор, который тупо выполняет ее M шагов и является корректным анализатором.
Другой вопрос, как узнать это число M, но оно существует, а значит и существует соответствующая программа-анализатор.
Здравствуйте, graniar, Вы писали:
g> g>> Сабж то как раз и требуется доказать или опровергнуть.
g> ·>Так он доказан, лет сто назад уж. Доказан как строгая математическая теорема. g> Так собственно топик про то, что доказан не убедительно и предлагается найти более убедительное доказательство без парадоксов с бесконечностями.
В доказательстве сабжа никаких парадоксов с бесконечностями нет. На всякий случай приведу само доказательство:
Допустим, Анализатор существует. Напишем алгоритм Диагонализатор, который принимает на вход число N, передает пару аргументов (N,N) Анализатору и возвращает результат его работы. Другими словами, Диагонализатор останавливается в том и только том случае, если не останавливается алгоритм с номером N, получив на вход число N. Пусть K — это порядковый номер Диагонализатора в множестве S. Запустим Диагонализатор, передав ему это число K. Диагонализатор остановится в том и только том случае, если алгоритм с номером K (то есть, он сам) не останавливается, получив на вход число K (какое мы ему и передали). Из этого противоречия следует, что наше предположение неверно: Анализатора не существует, что и требовалось доказать.
g> Собственно я даже не понял, причем тут вообще бесконечности, но предложил предположительно-эквивалентную формулировку без них.
Я тоже не понял где в сабже бесконечности. И никто тут так и не рассказал.
Здравствуйте, cppguard, Вы писали:
c> G>Реальных архитектур, имеешь в виду с ограничением по используемой памяти? В стиле, как Sinclair выше привел, или нечто более практичное? c> А на деле, если доказать, что P = NP, то никоим образом полиномиальный алгоритм факторизации простых чисел не возникнет сам собой, его ещё нужно будет придумать.
Доказать P=NP это собственно найти простой механический способ свести алгоритм NP к виду P. Так что придумывать ничего не нужно будет, в худшем случае это будет инженерной задачей как это сделать поэффективнее.
Здравствуйте, ·, Вы писали:
·>Я тоже не понял где в сабже бесконечности. И никто тут так и не рассказал.
Это меня Sinclair запутал.
А anonymouse2, как оказалось сразу суть проблемы уловил. Вот вам и авторитетность. Как говорится, иногда "устами младенца глаголет истина".
Вобщем, как в сообщении выше написал, для заданного размера входящей программы, есть анализатор, который тупо ждет необходимое число шагов.
А в формулировке задачи (взял в этот раз с англоязычного для надежности) ничего про начальный размер программы не говорится:
The overall goal is to show that there is no total computable function that decides whether an arbitrary program i halts on arbitrary input x; that is, the following function h (for "halts") is not computable
Соответственно, какое бы большое число M мы не взяли, есть достаточно большая программа, которая потребует больше шагов для завершения.
То есть, как сказал anonymouse2,
проанализировать любую программу и предсказать, зависнет она или нет, нельзя. Просто потому что "любая" программа может быть бесконечной.
Здравствуйте, graniar, Вы писали:
g> ·>Я тоже не понял где в сабже бесконечности. И никто тут так и не рассказал. g> Это меня Sinclair запутал.
Да он сам запутался, похоже.
g> А anonymouse2, как оказалось сразу суть проблемы уловил. Вот вам и авторитетность. Как говорится, иногда "устами младенца глаголет истина".
А я так и не понял что за проблема у которой надо улавливать суть.
g> Соответственно, какое бы большое число M мы не взяли, есть достаточно большая программа, которая потребует больше шагов для завершения.
Не то, что "большая программа". А вообще неизвестно какая, практически любая. И маленькие программы могут требовать оооооооочень много шагов. Функцию Аккермана погляди — всего ~3 строчки кода.
g> проанализировать любую программу и предсказать, зависнет она или нет, нельзя. Просто потому что "любая" программа может быть бесконечной.
Это не очень корректное высказывание. Нет бесконечного натурального числа. Так и нет бесконечной программы. Всё тут конечное.
Множество всех программ|чисел — бесконечно.
Здравствуйте, ·, Вы писали:
·>А я так и не понял что за проблема у которой надо улавливать суть.
Проблема в некорректной формулировке сабжа.
А если добавить условие ограниченности размера начального состояния анализируемой программы, проблема остановки разрешима самым тривиальным способом.
Ну и заново открывает поле для незавершенных исследований более эффективных способов, которые были прекращены после публикации некорректного доказательства.
Здравствуйте, graniar, Вы писали:
g> ·>А я так и не понял что за проблема у которой надо улавливать суть. g> Проблема в некорректной формулировке сабжа. g> А если добавить условие ограниченности размера начального состояния анализируемой программы, проблема остановки разрешима самым тривиальным способом.
Похрен на начальное состояние. Любой алгоритм с любым начальным состоянием тривиально сводится к алгоритму с начальным состоянием нулевого размера.
"Разрешимость" получается только если у нас есть заданное ограничение ресурсов для исполнителя алгоритмов. В этом случае можно тупо перечислить все возможные программы влезающие в заданное ограничение и составить базу данных ответов "да-нет" для каждой программы из списка. По сути эти существующие на сегодня статические анализаторы и делают.
g> Ну и заново открывает поле для незавершенных исследований более эффективных способов, которые были прекращены после публикации некорректного доказательства.
Какой публикации какого некорректного доказательства? Я вроде уже привёл тебе корректное доказательство. Зачем ты смотришь на некорректные?
Здравствуйте, ·, Вы писали:
g>> А если добавить условие ограниченности размера начального состояния анализируемой программы, проблема остановки разрешима самым тривиальным способом. ·>Похрен на начальное состояние. Любой алгоритм с любым начальным состоянием тривиально сводится к алгоритму с начальным состоянием нулевого размера.
Не уверен, что распарсил. Может ты имел ввиду, промежуточное состояние? Потому-что начальное состояние может быть забито рэндомом.
И по-любому, сама программа тоже занимает место. Так-что начальное состояние нулевого размера — это тривиальная нулевая МТ, останавливающаяся после 0 ходов.
·>Какой публикации какого некорректного доказательства? Я вроде уже привёл тебе корректное доказательство. Зачем ты смотришь на некорректные?
Вот именно его некорректности и посвящен данный топик.
Здравствуйте, ·, Вы писали:
·>Доказать P=NP это собственно найти простой механический способ свести алгоритм NP к виду P. Так что придумывать ничего не нужно будет, в худшем случае это будет инженерной задачей как это сделать поэффективнее.
Не обязательно. Может какими-то извилистыми путями получится доказать наличие полиномиального алгоритма, но окажется, что поиск самого алгоритма тоже NP-полная задача более высокой сложности. И что метод математической индукции там не помогает и алгоритм для N элементов не годится для N+1.
Здравствуйте, graniar, Вы писали:
g> ·>Доказать P=NP это собственно найти простой механический способ свести алгоритм NP к виду P. Так что придумывать ничего не нужно будет, в худшем случае это будет инженерной задачей как это сделать поэффективнее. g> Не обязательно. Может какими-то извилистыми путями получится доказать наличие полиномиального алгоритма, но окажется, что поиск самого алгоритма тоже NP-полная задача более высокой сложности.
Все NP-полные задачи — это задачи одного класса сложности. По определению.
Здравствуйте, graniar, Вы писали:
g> ·>Похрен на начальное состояние. Любой алгоритм с любым начальным состоянием тривиально сводится к алгоритму с начальным состоянием нулевого размера. g> Не уверен, что распарсил. Может ты имел ввиду, промежуточное состояние? Потому-что начальное состояние может быть забито рэндомом. g> И по-любому, сама программа тоже занимает место. Так-что начальное состояние нулевого размера — это тривиальная нулевая МТ, останавливающаяся после 0 ходов.
Я значит не понял что за начальное состояние. Но это не важно, т.к. состояние — это только модель конкретной формализации алгоритма в виде МТ. Можно взять другую модель, лямбда-исчисление, или диофантовы уравнения — в них никаких состояний нет вообще, но ничего не изменится, результат сабжа — тот же.
g> ·>Какой публикации какого некорректного доказательства? Я вроде уже привёл тебе корректное доказательство. Зачем ты смотришь на некорректные? g> Вот именно его некорректности и посвящен данный топик.
Но ты так и не привёл его, поэтому неясно корректность чего ты хочешь обсуждать и зачем.
Прочитай корректное доказательство, есть и в вики, и в куче книжек.
Здравствуйте, ·, Вы писали:
g>> Не обязательно. Может какими-то извилистыми путями получится доказать наличие полиномиального алгоритма, но окажется, что поиск самого алгоритма тоже NP-полная задача более высокой сложности. ·>Все NP-полные задачи — это задачи одного класса сложности. По определению.
Я не про класс. Например: сложность нахождения алгоритма для проверки гамильтонова цикла на графе из N точек окажется эквивалентна сложности проверки гамильтонова цикла на графе из N+k точек.
Здравствуйте, graniar, Вы писали:
g> ·>Но ты так и не привёл его, поэтому неясно корректность чего ты хочешь обсуждать и зачем. g> Привел ссылку на статью в вики и что конкретно мне не нравится. https://rsdn.org/forum/education/8546713
Т.е. это не корректность доказательства мы обсуждаем, а корректность твоих убеждений.
Ты просто неправильно понимаешь доказательство.
"Сам процесс анализа запускается на большей машине, которая включает и программу-анализатор и анализируемую машину." — это ты сам придумал в процессе приземления. В доказательстве это ничего такого не требуется. Оно доказывает в общем случае — неважно какой бы ни был вероятный анализатор — простой, сложный, большой, маленький — он невозможен никакой вообще.
Здравствуйте, graniar, Вы писали:
g> ·>Все NP-полные задачи — это задачи одного класса сложности. По определению. g> Я не про класс. Например: сложность нахождения алгоритма для проверки гамильтонова цикла на графе из N точек окажется эквивалентна сложности проверки гамильтонова цикла на графе из N+k точек.
Ага. И т.к. k — константа, то алгоритмическая сложность ровно та же.
O(f(N)) == O(f(N+k))
Здравствуйте, ·, Вы писали:
g>> Я не про класс. Например: сложность нахождения алгоритма для проверки гамильтонова цикла на графе из N точек окажется эквивалентна сложности проверки гамильтонова цикла на графе из N+k точек. ·>Ага. И т.к. k — константа, то алгоритмическая сложность ровно та же. ·>O(f(N)) == O(f(N+k))
Это было в поддержку аргумента оппонента про то, что доказательство P=NP может не помочь решать NP-полные задачи.
Здравствуйте, ·, Вы писали:
·>Ты просто неправильно понимаешь доказательство.
Ну ок, опустим пока непонятное колдунство. В процессе обсуждения выплыла интересная деталь:
В формулировке ничего не говорится про ограничение на размер начального состояния анализируемой машины.
Но оказывается, если задать верхнюю границу, сколь угодно большую, то проблема имеет тривиальное решение.
Вот это сильно вводит в заблуждение. Я, например, долгое время считал, что программа фиксированной начальной длины не разрешима в принципе.
Допускаю, что среди множества доказательств других проблем, опирающихся на проблему останова, могут оказаться связанные с этим ошибки.
Это как с код-стайлом, чем ляпать побыстрее лишь бы работало, имеет смысл писать понятнее, чтоб при сопровождении у людей не возникало проблем.
И вообще, не могу представить, какая может быть польза от такого принципиального отсутствия ограничения на начальный размер, и соответственно польза от этого доказательства.
