Привет!

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

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

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

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

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

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

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

Цитата(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.