Здравствуйте, graniar, Вы писали:

g> ·>Ага. И т.к. k — константа, то алгоритмическая сложность ровно та же.
g> ·>O(f(N)) == O(f(N+k))
g> Это было в поддержку аргумента оппонента про то, что доказательство P=NP может не помочь решать NP-полные задачи.
Угу. И как выяснили — не может.

Здравствуйте, graniar, Вы писали:

g> ·>Ты просто неправильно понимаешь доказательство.
g> Ну ок, опустим пока непонятное колдунство. В процессе обсуждения выплыла интересная деталь:
g> В формулировке ничего не говорится про ограничение на размер начального состояния анализируемой машины.
Я не очень понимаю что за такой размер, на что он влияет и зачем о нём должно говориться.

g> Но оказывается, если задать верхнюю границу, сколь угодно большую, то проблема имеет тривиальное решение.
Не "задавать верхнюю границу", а ограничивать мощность вычислителя, сводя его на класс ниже чем МТ. Да, например, для Конечных Автоматов проблемы остановки нет. Но КА слишком слабые для решения большинства практических задач.

g> Вот это сильно вводит в заблуждение. Я, например, долгое время считал, что программа фиксированной начальной длины не разрешима в принципе.
Док-во сабжа использует нумерацию всех программ — однозначное сопоставление числа каждой программе. Можно, например, просто текст программ сортировать по алфавиту. И суть в том, что совершенно неважно как именно присваиваются номера. Совершенно неважно какой длины программа. Результат сабжа от этого не зависит.
Можно переписывать программы на разных языках — МТ, лямбда-функции, РАМ-машина, что угодно — тоже не важно. Результат тот же.

g> Допускаю, что среди множества доказательств других проблем, опирающихся на проблему останова, могут оказаться связанные с этим ошибки.
g> Это как с код-стайлом, чем ляпать побыстрее лишь бы работало, имеет смысл писать понятнее, чтоб при сопровождении у людей не возникало проблем.
Это я не понял.

Здравствуйте, ·, Вы писали:

·>Так он доказан, лет сто назад уж. Доказан как строгая математическая теорема.
Дык полно таких задач. Например гипотеза Коллатца.

Здравствуйте, Sinclair, Вы писали:

S>Ни в одном из этих случаев мы так и не получим доказательства теоремы Ферма.
S>Единственная надежда — на то, что мы вдруг получим опровержение теоремы, найдя контрпример, влезающий в ограничения реальной машины.

Ну вот простая задача которая может остановиться, очень не сразу.

a^3+b^3+c^3 = 42 где a,b,c целые числа

не тривиальное решение:

a=-80538738812075974
b=80435758145817515
c=12602123297335631

было затрачено 1,3 миллиона часов расчёта в глобальной вычислительной сети Charity Engine

немного спутал с другой задачей вот:

a/(b+c)+b/(a+c)=c/(a+b)

a=18800081
b=1481089
c=19214131

Здравствуйте, ·, Вы писали:

·>На практике он именно такой и будет, за исключением нескольких тривиальных случаев. Ты не сможешь на практике проверить 2^64 состояний на цикличность. Уже где-то на 2^40 время работы будет многие годы. В лучшем случае, статический анализатор будет находить какие-то известные паттерны по базе типичных багов, которую забили разработчики. И честно отвечать "не знаю", если ничего не смог найти. Т.е. это не алгоритм для решения сабжа, а просто алгоритм поиска по базе.
Алгоритм детектирования циклов ничего по базе не ищет.

·>Может где-то и существуют в математике, но не в контексте сабжа и МТ. Так что в оффтоп не уходи.
Именно в МТ они и существуют.

·>Т.е. они не похожи, а подклассы сложности МТ. Например, регекспы — это КА, и по определению завершается всегда (правда иногда могут захапать экспоненциально много памяти и обломить твой детектор циклов).
Вы опять путаете математический аппарат регекспов с их реализацией. Обломить детектор циклов на ограниченной машине невозможно.

·>Т.е. есть умалчиваемое тобою физическое ограничение на кол-во планок памяти.
Дело не в количестве планок памяти, а в ограничениях языка программирования.
Можно точно так же "починить" Машину Тьюринга, ограничив длину ленты некоторой константой.

·>Ровно так же невозможно дать ещё одну секундочку, если у тебя есть физическое ограничение на время, например, от батарейки комп работает. Ещё раз повторюсь — ограничение ресурсов, что по времени, что по памяти — эквивалентные подходы с тем же итогом.
В этом смысле — да, эквивалентные. Но неограниченное время на практике обеспечить проще, чем неограниченную память.

·>Ну во-первых, в современном мире такую программу ещё надо поискать. Во-вторых, а как узнать, что она не собирается? Вдруг вирус какой, который упорно скрывает свои сетевые действия.
Очень просто узнать — машина, на которой исполняется программа, лишена устройств ввода-вывода.

·>Что программа проверила для значений до 2^64, но не может выполнить алгоритм для значения 2^64+1 и _узнать_ результат работы.
Невозможно дать значение 2^64+1 программе, написанной на языке с 64-разрядными указателями.

·>Почему ты так решил-то, что в принципе?
Потому, что невозможно перебрать множество целых чисел.

·>Вот задачу четырёх красок решили перебором.
Ну так она и не была сформулирована в терминах целых чисел.

·>Если мы поперебирали чего-то — и таки нашли решение, то нам просто повезло. А если перебор не нашел решения, то мы ничего не знаем, и решение неизвестно. Никакие циклодетекторы нам не помогут. Т.е. твой циклодетектор (и любой другой алгоритм) будет давать не два ответа, как ты обещаешь, а три: "да", "нет", "хз".
Нет, ровно два. Математику не обманешь.

·>В смысле "вооброжаемое"? Вполне конкретное.
Воображаемое — в том смысле, что вы просто представляете себе "ну вот будут такие четыре числа". Как будет выглядеть запись этих четырёх чисел в реальной физической машине?

·>Либо четыре вполне конкретных конечных числа, либо "не существует таких чисел". Никакие бесконечности тут не нужны.
Конечно нужны. Вы же не знаете заранее, какого размера будут эти числа. Значит, под них нужно отводить неограниченную память. Вот вам и бесконечность.

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

while(true);

·>Твой анализатор только лишь детектит определённый паттерн поведения и обнаруживает цикл состояний и в _некоторых_ случаях может выдать ответ с меньшим расходом ресурсов, чем тупой полный прогон проги. Т.е. это просто алгоритм обнаружения циклов. Сабж он не решает.
Тупой полный прогон проги, в которой есть бесконечный цикл, не даст вообще ничего. А прогон детектора циклов даст совершенно точный ответ — потому что никаких других "паттернов поведения" у программы на такой машине быть не может.

Здравствуйте, Sinclair, Вы писали:

S> ·>На практике он именно такой и будет, за исключением нескольких тривиальных случаев. Ты не сможешь на практике проверить 2^64 состояний на цикличность. Уже где-то на 2^40 время работы будет многие годы. В лучшем случае, статический анализатор будет находить какие-то известные паттерны по базе типичных багов, которую забили разработчики. И честно отвечать "не знаю", если ничего не смог найти. Т.е. это не алгоритм для решения сабжа, а просто алгоритм поиска по базе.
S> Алгоритм детектирования циклов ничего по базе не ищет.
Алгоритм детектирования циклов это один из известных паттернов, которые статический анализатор использует для анализа кода в надежде обнаружить баг.

S> ·>Может где-то и существуют в математике, но не в контексте сабжа и МТ. Так что в оффтоп не уходи.
S> Именно в МТ они и существуют.
"Конкретная машина Тьюринга задаётся перечислением букв алфавита A, множеством состояний Q и набором правил перехода, по которым работает машина. "
Алфавит и множество состояний — конечны. Правил перехода будет Q*A штук. Т.е. конечно число.
Вполне поверю, что можно придумать вариации МТ с бесконечным числом состояний, но она будет эквивалентна классической МТ.

S> ·>Т.е. они не похожи, а подклассы сложности МТ. Например, регекспы — это КА, и по определению завершается всегда (правда иногда могут захапать экспоненциально много памяти и обломить твой детектор циклов).
S> Вы опять путаете математический аппарат регекспов с их реализацией. Обломить детектор циклов на ограниченной машине невозможно.
Детектор циклов будет требовать больше ресурсов, чем прогон самого регекспа. При этом известно, что он точно не содержит циклов и завершается. Т.е. облом полный.

S> ·>Т.е. есть умалчиваемое тобою физическое ограничение на кол-во планок памяти.
S> Дело не в количестве планок памяти, а в ограничениях языка программирования.
S> Можно точно так же "починить" Машину Тьюринга, ограничив длину ленты некоторой константой.
Ага, но тогда она не сможет выполнять некоторые алгоритмы.

S> ·>Ровно так же невозможно дать ещё одну секундочку, если у тебя есть физическое ограничение на время, например, от батарейки комп работает. Ещё раз повторюсь — ограничение ресурсов, что по времени, что по памяти — эквивалентные подходы с тем же итогом.
S> В этом смысле — да, эквивалентные. Но неограниченное время на практике обеспечить проще, чем неограниченную память.
Смотря какая практика. Часто дешевле купить больше памяти, чем заставлять юзера ждать.

S> ·>Ну во-первых, в современном мире такую программу ещё надо поискать. Во-вторых, а как узнать, что она не собирается? Вдруг вирус какой, который упорно скрывает свои сетевые действия.
S> Очень просто узнать — машина, на которой исполняется программа, лишена устройств ввода-вывода.
Это не даст ничего, т.к. программа на практике будет выполняться на других машинах. И этот анализаторский прогон так же бесполезен.

S> ·>Что программа проверила для значений до 2^64, но не может выполнить алгоритм для значения 2^64+1 и _узнать_ результат работы.
S> Невозможно дать значение 2^64+1 программе, написанной на языке с 64-разрядными указателями.
Заведи массив указателей. Попробуй на досуге подумать как на 32-битной машине могут работать файловые системы экзабайтных объёмов. А ещё про сегментную адресацию на 16-битных можно вспомнить.

S> ·>Почему ты так решил-то, что в принципе?
S> Потому, что невозможно перебрать множество целых чисел.
Как и невозможно перебрать все возможные карты для раскраски. Однако, это не всегда мешает.

S> ·>Вот задачу четырёх красок решили перебором.
S> Ну так она и не была сформулирована в терминах целых чисел.
Какая разница в каких терминах она сформулирована?!

S> ·>не два ответа, как ты обещаешь, а три: "да", "нет", "хз".
S> Нет, ровно два. Математику не обманешь.
Значит ты себя обманываешь.

S> ·>В смысле "вооброжаемое"? Вполне конкретное.
S> Воображаемое — в том смысле, что вы просто представляете себе "ну вот будут такие четыре числа". Как будет выглядеть запись этих четырёх чисел в реальной физической машине?
В виде ноликов и единичек — биты называется. Ты не забывай, что все эти виды памяти — регистры, оператива, внешняя, облачная — это всё инженерные заморочки, которые с т.з. МТ — всё одно, та же лента.

S> ·>Либо четыре вполне конкретных конечных числа, либо "не существует таких чисел". Никакие бесконечности тут не нужны.
S> Конечно нужны. Вы же не знаете заранее, какого размера будут эти числа. Значит, под них нужно отводить неограниченную память. Вот вам и бесконечность.
Если ты заранее знаешь, что именно _нужно_, то ответ на вопрос ты уже знаешь. В этом задача анализатора и заключается. Вот для теоремы ферма, как выяснилось — да, нужно. А для четырёх красок — не нужно, достаточно памяти для нескольких тысяч карт.

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

S> while(true);
S>

Остановится, когда электричество кончится, т.к. электричество — ограниченный ресурс.

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

Здравствуйте, ·, Вы писали:

·>Т.е. это не корректность доказательства мы обсуждаем, а корректность твоих убеждений.
Я, оказывается, финитист.

Здравствуйте, ·, Вы писали:
S>> Алгоритм детектирования циклов ничего по базе не ищет.
·>Алгоритм детектирования циклов это один из известных паттернов, которые статический анализатор использует для анализа кода в надежде обнаружить баг.
Описанный алгоритм — это динамический анализатор.

·>Вполне поверю, что можно придумать вариации МТ с бесконечным числом состояний, но она будет эквивалентна классической МТ.
Состояние МТ — это комбинация Q и состояния ленты. Лента — бесконечна.

·>Детектор циклов будет требовать больше ресурсов, чем прогон самого регекспа.
В константу раз.
·>При этом известно, что он точно не содержит циклов и завершается. Т.е. облом полный.
Это если ограничить машину только вычислением регекспов.

S>> Можно точно так же "починить" Машину Тьюринга, ограничив длину ленты некоторой константой.
·>Ага, но тогда она не сможет выполнять некоторые алгоритмы.
Ну и что? В реальности машин с бесконечной памятью не бывает, что означает недоступность для нас "некоторых алгоритмов". И ничего — индустрия жива и даже прибыльна.

S>> В этом смысле — да, эквивалентные. Но неограниченное время на практике обеспечить проще, чем неограниченную память.
·>Смотря какая практика. Часто дешевле купить больше памяти, чем заставлять юзера ждать.
Пока что мы всё ещё о математике, а не о прикладных решениях. Для юзера NP-полная задача малоотличима от невычислимой.

·>Это не даст ничего, т.к. программа на практике будет выполняться на других машинах. И этот анализаторский прогон так же бесполезен.
Мы всё ещё говорим о математике. Мне неважно, на каких машинах будет исполняться программа, если я статически проверил, что в ней нет обращения к IO.

S>> Невозможно дать значение 2^64+1 программе, написанной на языке с 64-разрядными указателями.
·> Заведи массив указателей. Попробуй на досуге подумать как на 32-битной машине могут работать файловые системы экзабайтных объёмов. А ещё про сегментную адресацию на 16-битных можно вспомнить.
Да хоть два массива указателей. 32-битная машина специально реализована так, чтобы иметь возможность эмулировать безлимитность памяти.
А если нас интересует решение проблемы останова, то у нас другая постановка задачи.

S>> Потому, что невозможно перебрать множество целых чисел.
·>Как и невозможно перебрать все возможные карты для раскраски. Однако, это не всегда мешает.
Ну так все карты и не нужно. Решение задачи четырёх красок свелось к набору доказательств для относительно небольшого множества вариантов локальной топологии.
Именно поэтому его и удалось получить. Если бы математики попробовали доказать эту теорему путём лобового перебора всех карт, то точно так же не получили бы никакого решения.
·>Какая разница в каких терминах она сформулирована?!
Большая. Если вы хотите решать перебором задачу, где нужно перебирать все целые числа, то вы обречены.

·>Значит ты себя обманываешь.


·>В виде ноликов и единичек — биты называется. Ты не забывай, что все эти виды памяти — регистры, оператива, внешняя, облачная — это всё инженерные заморочки, которые с т.з. МТ — всё одно, та же лента.
Ну так МТ построить-то невозможно. "Инженерные заморочки" — это как раз и есть "приземление" абстрактных математических концепций в реальный мир.
В реальном мире "числа" имеют вполне конечную разрядность.

·>Остановится, когда электричество кончится, т.к. электричество — ограниченный ресурс.
Нет конечно. Остановка — это выполнение команды HALT. Даже если выключить электричество, никакого HALT выполнено не будет.

·>Если детектор покажет отсутствие цикла на данном кол-ве памяти, но программа продолжает работать, то ответ "хз", т.к. прога может таки завершиться если дать ещё один байт.
Мы ходим по кругу. Программе, написанной в терминах ограниченной памяти, невозможно "дать ещё один байт".

Здравствуйте, Sinclair, Вы писали:

S> S>> Алгоритм детектирования циклов ничего по базе не ищет.
S> ·>Алгоритм детектирования циклов это один из известных паттернов, которые статический анализатор использует для анализа кода в надежде обнаружить баг.
S> Описанный алгоритм — это динамический анализатор.
Ок, пусть, не важно как он называется. В первую очередь это просто алгоритм поиска цикла в списке, ну да, он применён к состояниям некоего вычислителя. Важно то, что этот "анализатор" не имеет ничего общего с Анализатором, который используется в док-ве сабжа и никоим образом док-во не опровергает.

S> ·>Вполне поверю, что можно придумать вариации МТ с бесконечным числом состояний, но она будет эквивалентна классической МТ.
S> Состояние МТ — это комбинация Q и состояния ленты. Лента — бесконечна.
А что такое Q по-твоему?! В любом случае, это какая-то странная терминология, откуда ты её взял — неясно, она неправильная и вызывает путаницу. Я использую общепринятую:

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

И — самое важное!!! В определении МТ не используется "бесконечная лента". Нигде!
Там просто отсутствует какое либо ограничение на движение головки — каждое правило перехода содержит команду движения головки — влево или вправо. Всё. Ни в МТ, ни в сабже никакие бесконечности не используются.

S> ·>Детектор циклов будет требовать больше ресурсов, чем прогон самого регекспа.
S> В константу раз.
Угу, что и делает его бесполезным и даже вредным в данном случае, как минимум. Зачем тратить N*K ресурсов, если достаточно N.

S> ·>При этом известно, что он точно не содержит циклов и завершается. Т.е. облом полный.
S> Это если ограничить машину только вычислением регекспов.
Ну так эта твоя "реальная машина отключённая от сети" по сути и есть регексп, конечный автомат, точнее.

S> S>> Можно точно так же "починить" Машину Тьюринга, ограничив длину ленты некоторой константой.
S> ·>Ага, но тогда она не сможет выполнять некоторые алгоритмы.
S> Ну и что? В реальности машин с бесконечной памятью не бывает, что означает недоступность для нас "некоторых алгоритмов". И ничего — индустрия жива и даже прибыльна.
Они становятся доступны, если запрограммировать алгоритм по-другому. Впрочем, в любом случае сабж никак не запрещает существованию индустрии.

S> S>> В этом смысле — да, эквивалентные. Но неограниченное время на практике обеспечить проще, чем неограниченную память.
S> ·>Смотря какая практика. Часто дешевле купить больше памяти, чем заставлять юзера ждать.
S> Пока что мы всё ещё о математике, а не о прикладных решениях. Для юзера NP-полная задача малоотличима от невычислимой.
Под словом "пракика" я и понимал прикладные решения. А в математике всё равно — ограничение по времени или по памяти.

S> ·>Это не даст ничего, т.к. программа на практике будет выполняться на других машинах. И этот анализаторский прогон так же бесполезен.
S> Мы всё ещё говорим о математике. Мне неважно, на каких машинах будет исполняться программа, если я статически проверил, что в ней нет обращения к IO.
Если у неё ограничена память, то это конечный автомат с т.з. математики.

S> ·> Заведи массив указателей. Попробуй на досуге подумать как на 32-битной машине могут работать файловые системы экзабайтных объёмов. А ещё про сегментную адресацию на 16-битных можно вспомнить.
S> Да хоть два массива указателей. 32-битная машина специально реализована так, чтобы иметь возможность эмулировать безлимитность памяти.
Верно. Т.е. "Невозможно дать значение 2^64+1 программе, написанной на языке с 64-разрядными указателями" — ошибка.

S> А если нас интересует решение проблемы останова, то у нас другая постановка задачи.
Не понял. Решение проблемы останова — известно, т.к. есть док-во.

S> S>> Потому, что невозможно перебрать множество целых чисел.
S> ·>Как и невозможно перебрать все возможные карты для раскраски. Однако, это не всегда мешает.
S> Ну так все карты и не нужно. Решение задачи четырёх красок свелось к набору доказательств для относительно небольшого множества вариантов локальной топологии.
Это ты сейчас знаешь что свелось и все карты не нужно. А до того как это стало известным, кроме как перебора ничего не было.

S> Именно поэтому его и удалось получить. Если бы математики попробовали доказать эту теорему путём лобового перебора всех карт, то точно так же не получили бы никакого решения.
Ты не поверишь, но теорему Ферма тоже доказали без лобового перебора всех чисел.
Т.е. теперь точно известно, что алгоритм a^n+b^n=c^n — не останавливается. Т.е. теперь в базу можно забить правило "нашли такое выражение — точно знаем, что цикл бесконечный" и гонять на бесконечных числах не требуется.

S> ·>Какая разница в каких терминах она сформулирована?!
S> Большая. Если вы хотите решать перебором задачу, где нужно перебирать все целые числа, то вы обречены.
Дык сабж как раз о том, что неизвестно, нужно ли перебрать всё или не нужно!
Как выяснилось, что ни для теоремы ферма, ни для раскраски карт — не нужно.
Но ты можешь найти кучу задач для которых тупо неизвестно. Проблема Гольдбаха, например.

S> ·>В виде ноликов и единичек — биты называется. Ты не забывай, что все эти виды памяти — регистры, оператива, внешняя, облачная — это всё инженерные заморочки, которые с т.з. МТ — всё одно, та же лента.
S> Ну так МТ построить-то невозможно. "Инженерные заморочки" — это как раз и есть "приземление" абстрактных математических концепций в реальный мир.
S> В реальном мире "числа" имеют вполне конечную разрядность.
Но это не значит, что они ограничены. Что все числа, начиная с некоторого N, не выразимы на реальном компьютере.

S> ·>Остановится, когда электричество кончится, т.к. электричество — ограниченный ресурс.
S> Нет конечно. Остановка — это выполнение команды HALT. Даже если выключить электричество, никакого HALT выполнено не будет.
Наконец-то ты на верном пути. Именно, что выполнение команды HALT! Расскажи в какой момент анализируемая твоим "динамическим анализатором" МТ вида "Q0: записать один, сдвинуть головку вправо, перейти в Q0" выполнит halt?

S> ·>Если детектор покажет отсутствие цикла на данном кол-ве памяти, но программа продолжает работать, то ответ "хз", т.к. прога может таки завершиться если дать ещё один байт.
S> Мы ходим по кругу. Программе, написанной в терминах ограниченной памяти, невозможно "дать ещё один байт".
Так и в ограниченной по времени программе невозможно дать ещё одну секунду.
Ещё раз повторю. Это эквивалентные ограничения.
Смотри. У тебя есть такой код: while(true)print(1);. И типа твой циклодетектор что-то там найдёт. Если у тебя есть ограничение по памяти, то ты можешь просто слегка (алгоримтически тривиально) модифицировать этот код в такой while(true){allocateOneByte();print(1);}} и без всякого циклодетектора понять, что код "зациклился".

Здравствуйте, ·, Вы писали:

·>Ок, пусть, не важно как он называется. В первую очередь это просто алгоритм поиска цикла в списке, ну да, он применён к состояниям некоего вычислителя. Важно то, что этот "анализатор" не имеет ничего общего с Анализатором, который используется в док-ве сабжа и никоим образом док-во не опровергает.
Он и не должен ничего опровергать. Это другой алгоритм, который применяется к другой машине.

·>

·>Конкретная машина Тьюринга задаётся перечислением букв алфавита A, множеством состояний Q и набором правил перехода, по которым работает машина.

·>И — самое важное!!! В определении МТ не используется "бесконечная лента". Нигде!
Эмм, кто-то из нас невнимательно читает.

В состав машины Тьюринга входит неограниченная в обе стороны лента

Как только мы ограничиваем ленту, существование Анализатора перестаёт быть опровергнутым.

S>> В константу раз.
·>Угу, что и делает его бесполезным и даже вредным в данном случае, как минимум. Зачем тратить N*K ресурсов, если достаточно N.
Эмм, вы сейчас предположили, что существует некий алгоритм, который проверяет произвольную программу для ограниченной машины Тьюринга на предмет соответствия её некоему регулярному выражению, причём за N ресурсов. Я правильно понял?

·>Ну так эта твоя "реальная машина отключённая от сети" по сути и есть регексп, конечный автомат, точнее.
А то. У вас есть более эффективный алгоритм, который обнаруживает циклы в конечном автомате?

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

·>Под словом "пракика" я и понимал прикладные решения. А в математике всё равно — ограничение по времени или по памяти.
Ок.
·>Если у неё ограничена память, то это конечный автомат с т.з. математики.
Угу.
·>Верно. Т.е. "Невозможно дать значение 2^64+1 программе, написанной на языке с 64-разрядными указателями" — ошибка.
Нет, не ошибка. "Эмуляция" в данном случае эквивалентна некоему оракулу. То есть мы не даём машине бесконечную память, мы просто переносим проблему реализации бесконечности куда-то ещё.

·>Не понял. Решение проблемы останова — известно, т.к. есть док-во.

— Мы сами знаем, что она не имеет решения, — сказал Хунта, немедленно ощетинившись. — Мы хотим знать, как ее решать.

(С) АБС.

·>Это ты сейчас знаешь что свелось и все карты не нужно. А до того как это стало известным, кроме как перебора ничего не было.
Это просто означает, что "решение" при помощи полного перебора вообще решением не является.

·>Ты не поверишь, но теорему Ферма тоже доказали без лобового перебора всех чисел.
Отчего ж не поверю — поверю
·>Т.е. теперь точно известно, что алгоритм a^n+b^n=c^n — не останавливается. Т.е. теперь в базу можно забить правило "нашли такое выражение — точно знаем, что цикл бесконечный" и гонять на бесконечных числах не требуется.
"Забить в базу" не так легко, как кажется.
1. выражение "алгоритм a^n+b^n=c^n" не имеет смысла — тут нет алгоритма. Это всего лишь некоторая формула. Если вы под "алгоритмом" имеете в виду пошаговое вычисление выражения сравнения aⁿ+bⁿ с сⁿ, где a, b, c — положительные целые, а n — целое, большее 2х, то да — мы можем подставить в результат false без честного вычисления. После чего можно продолжить свёртку программы — в частности, в ветвлении на основе этого результата мы можем целиком выбросить одну из веток, что, потенциально, позволит нам сделать ещё какие-то выводы.
2. алгоритм вычисления этой формулы может быть запрограммирован по-разному. Простого "побитового" сравнения кода программы недостаточно — нужно доказать, что некое вычисление эквивалентно этой формуле. Если я не ошибаюсь, то это — частный случай теоремы Райса. Так что упс.

·>Но ты можешь найти кучу задач для которых тупо неизвестно. Проблема Гольдбаха, например.
А ещё я могу найти кучу функций, которые являются невычислимыми. Несмотря на то, что однозначность решения легко доказать.

·>Но это не значит, что они ограничены. Что все числа, начиная с некоторого N, не выразимы на реальном компьютере.
Для любого реального компьютера существует некоторое N, начиная с которого числа становятся невыразимыми.

·>Наконец-то ты на верном пути. Именно, что выполнение команды HALT! Расскажи в какой момент анализируемая твоим "динамическим анализатором" МТ вида "Q0: записать один, сдвинуть головку вправо, перейти в Q0" выполнит halt?
Ни в какой. Эта МТ не останавливается.
А если мы запустим такую программу на МТ c ограниченной лентой, то HALT будет выполнен автоматически в момент сдвинуть головку вправо, когда головка упрётся в край ленты.

·>Ещё раз повторю. Это эквивалентные ограничения.
·>Смотри. У тебя есть такой код: while(true)print(1);. И типа твой циклодетектор что-то там найдёт. Если у тебя есть ограничение по памяти, то ты можешь просто слегка (алгоримтически тривиально) модифицировать этот код в такой while(true){allocateOneByte();print(1);}} и без всякого циклодетектора понять, что код "зациклился".
Проблема — в том, что применение подобной манипуляции к коду, который до неё не зацикливался, сделает его "зацикливающимся". Какой смысл в таком "детекторе"?

Здравствуйте, Sinclair, Вы писали:

S>Он и не должен ничего опровергать. Это другой алгоритм, который применяется к другой машине.
Верно. И выдаёт результат не относящийся к сабжу.

S>·>И — самое важное!!! В определении МТ не используется "бесконечная лента". Нигде!
S>Эмм, кто-то из нас невнимательно читает.
S>

S>В состав машины Тьюринга входит неограниченная в обе стороны лента

Это не _определение_ МТ. Открой мат-формализацию МТ и ткни пальцем где там ∞.

S>Как только мы ограничиваем ленту, существование Анализатора перестаёт быть опровергнутым.
И перестаёт быть МТ и формализацией алгоритма.

S>·>Угу, что и делает его бесполезным и даже вредным в данном случае, как минимум. Зачем тратить N*K ресурсов, если достаточно N.
S>Эмм, вы сейчас предположили, что существует некий алгоритм, который проверяет произвольную программу для ограниченной машины Тьюринга на предмет соответствия её некоему регулярному выражению, причём за N ресурсов. Я правильно понял?
Нет. Я сказал, что проще тупо запустить регулярку и подождать когда она закончится, чем запускать её под твоим циклоанализатором который просто интерпретирует эту же регулярку дважды и не даёт никакого полезного результата.

S>·>Ну так эта твоя "реальная машина отключённая от сети" по сути и есть регексп, конечный автомат, точнее.
S>А то. У вас есть более эффективный алгоритм, который обнаруживает циклы в конечном автомате?
Зацикливаться конечный автомат не может. Он всегда завершает свою работу.

S>·>Верно. Т.е. "Невозможно дать значение 2^64+1 программе, написанной на языке с 64-разрядными указателями" — ошибка.
S>Нет, не ошибка. "Эмуляция" в данном случае эквивалентна некоему оракулу. То есть мы не даём машине бесконечную память, мы просто переносим проблему реализации бесконечности куда-то ещё.
Это ты что-то сочиняешь. Оракл это вполне определённая конструкция в ТА: https://en.wikipedia.org/wiki/Oracle_machine
Машине Тьюринга не надо давать бесконечную память (что бы это ни значило) — посмотри на сам формализм МТ. Надо просто выполнять движение головки вправо-влево.

S>·>Это ты сейчас знаешь что свелось и все карты не нужно. А до того как это стало известным, кроме как перебора ничего не было.
S>Это просто означает, что "решение" при помощи полного перебора вообще решением не является.
Для некоторых задач — является. Начали перебирать и таки нашли решение.

S>·>Т.е. теперь точно известно, что алгоритм a^n+b^n=c^n — не останавливается. Т.е. теперь в базу можно забить правило "нашли такое выражение — точно знаем, что цикл бесконечный" и гонять на бесконечных числах не требуется.
S>"Забить в базу" не так легко, как кажется.
Потому что сабж.

S>1. выражение "алгоритм a^n+b^n=c^n" не имеет смысла — тут нет алгоритма. Это всего лишь некоторая формула. Если вы под "алгоритмом" имеете в виду пошаговое вычисление выражения сравнения aⁿ+bⁿ с сⁿ, где a, b, c — положительные целые, а n — целое, большее 2х, то да — мы можем подставить в результат false без честного вычисления. После чего можно продолжить свёртку программы — в частности, в ветвлении на основе этого результата мы можем целиком выбросить одну из веток, что, потенциально, позволит нам сделать ещё какие-то выводы.
Я имею в виду программу for(a,b,c,n in 2..){if(a^n+b^n=c^n) print(1);} — напечатает ли эта программа "1"? Поможет ли твой циклодетектор ответить на этот вопрос?

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

S>·>Но это не значит, что они ограничены. Что все числа, начиная с некоторого N, не выразимы на реальном компьютере.
S>Для любого реального компьютера существует некоторое N, начиная с которого числа становятся невыразимыми.
Так назови его, если сможешь. Вон некоторые до Graham's number досчитали. Ты почему-то считаешь, что числа непременно надо поразрядно представлять. Можно и символьные выражения использовать. Число записанное как "2^1000" — занимает всего 6 байт.
А достаточно в коде появится int64 счётчику и твой циклодетектор станет абсолютно бесполезен на практике. Что и происходит в большинстве реальных случаев, твой анализатор будет отвечать "цикл не найден" почти всегда. Вот это уже подлянка Райса.

S>·>Наконец-то ты на верном пути. Именно, что выполнение команды HALT! Расскажи в какой момент анализируемая твоим "динамическим анализатором" МТ вида "Q0: записать один, сдвинуть головку вправо, перейти в Q0" выполнит halt?
S>Ни в какой. Эта МТ не останавливается.
S>А если мы запустим такую программу на МТ c ограниченной лентой, то HALT будет выполнен автоматически в момент сдвинуть головку вправо, когда головка упрётся в край ленты.
Только это уже другая программа будет. Т.е. вместо исходной задачи f(n) ты неявно анализируешь f(n), n<N, но почему-то заявляешь, что результат анализа даёт информацию об исходной задаче.

S>·>Ещё раз повторю. Это эквивалентные ограничения.
S>·>Смотри. У тебя есть такой код: while(true)print(1);. И типа твой циклодетектор что-то там найдёт. Если у тебя есть ограничение по памяти, то ты можешь просто слегка (алгоримтически тривиально) модифицировать этот код в такой while(true){allocateOneByte();print(1);}} и без всякого циклодетектора понять, что код "зациклился".
S>Проблема — в том, что применение подобной манипуляции к коду, который до неё не зацикливался, сделает его "зацикливающимся".
Не понял с чего это вдруг. В худшем случае, просто будет требовать в константу раз больше памяти.

S>Какой смысл в таком "детекторе"?
Ровно такой же, какой в твоём циклодетекторе.