Привет!

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

В сллучае рекурсивных циклов нужно предусмотреть есть ли там точка выхода, в случае итерационного цикла да нельзя ИМХО потому что проверка усовия выхода из цикла занимает не меньше шагов чем сам цикл

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

пишем такую программу: на вход подается текст исследуемой программы, если она не зацикливается - выводим на экран плюсик и выполняем иссл.программу, если да - не выводим

а потом запускаем ее, а на вход подаем свой же текст

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

СТОП! Поменял свое мнение, такую программку написать можно! Ведь наш мозг может заметить такой баг, значит и машина сможет, может и придется всякие нейронные сети писать, но задача теоретически решаема

Цитата(Vex @ 11.4.2005, 18:15)

Ведь наш мозг может заметить такой баг

Не уверен. Если сложность проверки условия превосходит возможности человеческого мозга, то как тогда действовать?

Цитата(maxim1000 @ 11.4.2005, 07:48)

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

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

А теперь давайте ваши опровержения. Подаем на вход программы А ее саму, т.е. А(А), так? Значит самой программе А нужна еще одна программа, которую надо проверить (в противном случае она выведет что-то типа "опущен необходимиый параметр" ), значит запускаем так: А(А(Б)). Итак, А(Б) не имеет бесконечных циклов и выведет имеет ли бесконечные циклы программа Б. Нет никакой разницы что даст нам А(Б) - ибо все равно это будет сделано за конечное время. А уж А(А(Б)) тем более вернет "да".

Если будете особо настойчивы я даже напишу как сделать программу А.
Добавлено @ 15:33

Цитата(neutrino @ 12.4.2005, 14:28)

Причем программа А выявляет бесконечные циклы без (!) запуска исследуемых программ

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

Пока не рассматриваем рекурсию. Хотя я уверен, что и с ней разберусь.

Цитата(neutrino @ 12.4.2005, 15:28)

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

Напиши, пожалуйста, потому что я не вижу таких способов определния наличия бесконечных циклов, которые сами бы не выполняли этот цикл.
А если Б имеет бесконечный цикл? Тогда А(Б) тоже имеет бесконечный цикл и А(А(Б)) имеет опять-таки бесконечный цикл => мы не получим результата.

Смотрите, может я и ошибаюсь:
1) запоминаем значения всех переменных (которые учавствуют в цикле), в массиве ВА в определенном порядке.
2) выполняем одну итерацию цикла
3) записываем в массив ВА2 значения тех же переменных в том же порядке
4) если ВА = ВА2, то цикл бесконечен - выходим из программы с ответом "да".
5) Гоуту шаг 2
6) цикл конечен - выходим из программы с ответом "нет".

Добавлено @ 16:13
Забыл добавить: из-за того, что память ограничена, конечный цикл может идти 2^(размер памяти), что безусловно конечно.

Но таких программ на самом деле нет. Хотя можно и побаловаться и написать такую программу.

neutrino
Мне кажется - не пройдет.
1. Даже простейший случай не учитывается - если переменная будет попеременно на каждом шаге циклически меняться - 2, 4, 2, 4...
2. Проверка цикла потребует чтолько же шагов, сколько и сама программа. То есть вместо программы-тестировщика мы можем с тем же успехом выполнить сам исходный код.
3. Возможно, мы на этом этапе еще не знаем исходных чисел цикла. Например, они зависят от ввода пользователя. Проверять все?

Задача поставлена некорректно.

Любая программа манипулирует некоторыми данными. Т.е. есть исходные данные.

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

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

А вот с динамическими данными неограниченного динамического размера ничего не получится. И нахождение в программе какого-нить цикла типа do while true есть всего лишь частный случай.

Цитата

запоминаем значения всех переменных (которые учавствуют в цикле), в массиве ВА в определенном порядке

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

Вот только давайте в крайности не впадать.

Я просто разрабатываю проект для разработки алгоритмов. И хотелось бы туда запихать такую фичу. Вот мне уже много народу сказало, что нефига у меня не получится. А я с ними несогласен!

Теперь по порядку.

Цитата(Lamer @ 12.4.2005, 15:17)

Мне кажется - не пройдет.

Когда кажется креститься надо, а когда крестишься - еще больше кажется

Цитата(Lamer @ 12.4.2005, 15:17)

1. Даже простейший случай не учитывается - если переменная будет попеременно на каждом шаге циклически меняться - 2, 4, 2, 4...

Опа, я алгоритм той проги неправильно немного написал. Извините. Первый набор (массив) значений переменных надо брать из первой итерации цикла или: если существуют 2 идентичных набора значений переменных, учавствующих в цикле, то такой цикл бесконечен.

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

Цитата(Lamer @ 12.4.2005, 15:17)

2. Проверка цикла потребует чтолько же шагов, сколько и сама программа. То есть вместо программы-тестировщика мы можем с тем же успехом выполнить сам исходный код.

Неверное заключение. Вот смотри, тривиальный случай:

Код

while (true);

Этот бесконечный цикл обнаружится после второй итерации. В любом случае программа обнаружит конечный цикл максимум (!) за количество итераций самого цикла и это только в том случае, если в цикле до его завершения не будет ни одной пары одинаковых наборов (массивов) значений переменных этого цикла. Может быть другая более худшая ситуация: нет памяти для размещения наборов переменных. Но такая ситуация в наше время ИМХО невозможна. Может только в каких-то крайних случаях.

Кроме того я могу подумать над более хитрым решением задачи о конечных циклах. Может чего и найду.

Цитата(Lamer @ 12.4.2005, 15:17)

3. Возможно, мы на этом этапе еще не знаем исходных чисел цикла. Например, они зависят от ввода пользователя. Проверять все?

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

Код

int a=1, b=1000; while (a<b) cin>>b;

После ввода первого числа, пользователь пошел пить кофе. Споткнулся, упал, ударился головой, его повезли на скорой, а она попала в аврию (не дай Б-г). А теперь внимание вопрос: сколько времени-выполнения потребуется алгоритму считывающему числа? Это мне напоминает: у меня 2 яблака и 3 груши, какого размера у соседа экран монитора и каков разлет осколков от его мыши, если бы он кинул свою клавиатуру в форточку, версия которой 95? Для моей проги это вообще неактуально. Есть еще более хитрый цикл:

Код

repeat ChkDate = CurrentDate; until ChkDate < Date("31/12/3000");

Допустим сегодня 12/4/2005.


Добавлено @ 19:03

Цитата(Akina @ 12.4.2005, 15:35)

Задача поставлена некорректно.

Почему?

Цитата(Akina @ 12.4.2005, 15:35)

А вот с динамическими данными неограниченного динамического размера ничего не получится.

"Пример в студию!" © Vit
Добавлено @ 19:05

Цитата(maxim1000 @ 12.4.2005, 16:49)

согласен

Ну хоть кто-то со мной согласен И не просто кто-то а сам великий математик-зеленая лягушка-Максим8!

Спасибо!

neutrino
Твой алгоритм, кстати, Америку не открывает
Это самый обычный способ поиска зацикливаний. Но применим ли он для программ -- это интересный вопрос
Добавлено @ 19:23
Вот забавный случай:

Код

for(unsigned i = 1; i != 0; i++);

Для того, чтобы определить, что он конечен, нужно 2^32 шагов.

Код

for(unsigned i = 1; i !=0; i++) {    if (i == 0xFFFFFFFEu) i = 1; }

А определение того, что этот бесконечен тоже потребует около 2^32 шагов.

Т.е. при конечных объёмах памяти это довольно сомнительное мероприятие

Цитата

Твой алгоритм, кстати, Америку не открывает

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

Цитата

тоже потребует около 2^32 шагов.

2^32-1, если быть точнее.

Цитата

Т.е. при конечных объёмах памяти это довольно сомнительное мероприятие

Может быть я что-нибудь найду и для таких случаев.


Добавлено @ 20:40

Цитата(neutrino @ 12.4.2005, 19:35)

Может быть я что-нибудь найду и для таких случаев.

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

neutrino
То есть, ты имел в виду, что надо сохранять в новый массив значения переменных при каждой итерации? Тогда согласен, но расход памяти будет немеряный... Да и сличение массивов тоже будет время отнимать...
Насчет второго пункта - я имел в виду такую ситуацию:

Код

cin>>b; while (a!=b) {b--;}

Как ты будешь определять конечность такого алгоритма? Ведь он конечен, только если юзер введет b >= a.

Lamer George
Ну, как уже сказано, зависящие от пользователя циклы проверять нафик не надо

Цитата(neutrino @ 12.4.2005, 21:35)

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

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

Цитата(neutrino @ 12.4.2005, 21:35)

Может быть я что-нибудь найду и для таких случаев.

Кстати можно вычислять что-то вроде CRC или хэш-функции от текущего набора данных. Уменьшит расход памяти. Хотя и увеличит время.

Цитата(Lamer @ 12.4.2005, 19:45)

Как ты будешь определять конечность такого алгоритма? Ведь он конечен, только если юзер введет b >= a.

По скольку все переменные ограничены опр. кол-вом битов, то цикл будет конечен в любом случае. Если будет ошибка Overflow Error - это значит цикл дошел до минимального отрицательного числа (зависит от кол-ва бит в переменной). Потом все пойдет по кругу и попадуться 2 одинаковых значения переменной b. В любом случае любое изменение значений переменных до цикла выполнится программой А. А каким образом именно изменится это значение неважно.
Добавлено @ 21:57

Цитата

Ну, как уже сказано, зависящие от пользователя циклы проверять нафик не надо

Что за надсмешки!? Что за морды-смайлы!?

Нет ну правда, разве имеет смысл определение время выполнения алгоритма с циклом в теле которого ввод данных пользователем?
Добавлено @ 22:03

Цитата

А вот это уже лучше. Есть даже подозрение, что для целочисленных циклов это вполне реально.

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

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

Еще одна проблемка: цикл в цикле.

Цитата

И не просто кто-то а сам великий математик-зеленая лягушка-Максим8!

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

Цитата

Например искать корреляцию данных

Цитата

А вот это уже лучше

вот вам пример

Код

unsigned int ZhutkoeTransform(unsigned int x) {   //тут происходит очень сложное преобразование, которое является перестановкой } ... unsigned int c; for(c=0;c<0xffffff;c++)   if(ZhutkoeTransform(c)==0)     break;

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

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

Это сообщение отредактировал(а) maxim1000 - 12.4.2005, 22:17

maxim1000
Нда...

Если бы функция была непрерывной... И найти бы две точки, где она разного знака... Мечты...

А вот с таким чёрным ящиком хрен чего скажешь.

ЗЫ: При внимательном рассмотрении твоего примера видна, что цикл конечен из-за условия c<0xffffff

Цитата

ЗЫ: При внимательном рассмотрении твоего примера видна, что цикл конечен из-за условия c<0xffffff

ладно-ладно, поймал
заменим break на while(true) и будем считать, что мы не знаем, возвращает ли когда-нибудь функция 0

Цитата(neutrino @ 12.4.2005, 19:59)

"Пример в студию!" © Vit

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

Цитата

for(unsigned i = 1; i != 0; i++);

а если float? double? hyperlong?

Максим, можно даже проще:
0) п = 2
1) пока тру
2) п = искать следующее простое число
3) конец пока


Добавлено @ 23:29
Как говорится: "сосем ноги!"

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

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

Задача о нахождении уязвимостей в программе - таких, как переполнение буфера и т.п.

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

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

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

То, что до сих пор идет война на вирусном фронте, говорит скорее за то, что задача нерешаема.

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

Это сообщение отредактировал(а) Chingachguk - 24.4.2005, 23:24