Re: Кажется, дошло
От: Alexey F  
Дата: 28.02.09 00:49
Оценка:
Здравствуйте, GhostCoders, Вы писали:

Из вики:

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

(кстати, в конце статьи ссылка на On computable numbers, with an application to the Entscheidungsproblem).

Для любых входных данных, точно же!
Если зафиксировать все данные, с которыми работает программа (включая данные, получаемые, скажем, от ГСЧ и от каждой внешней функции), то тогда алгоритмическое определение зависнет/не зависнет не является неразрешимой задачей в большинстве случаев.
Придумалось такое исключение из вышеприведённой фразы (хотя, подумав, всё больше прихожу к выводу, что вычисление дробной части числа "пи" здесь можно рассматривать как входные данные... Ай, 3 ночи, голова совсем не работает ):
"Если где-либо в дробной части числа "пи" встречается последовательность цифр 84327411834783744390087539249 — завершить цикл". Здесь само вычисление того, зациклится программа или нет, может занять время, стремящееся к бесконечности .

GhostCoders, как Ваш метод отреагирует на вышеприведённый алгоритм?

Однако к большинству приведённых в ветке примеров можно создать статический анализатор, извещающий о зацикливании. Т.е. — простой инструмент, предупреждающий о простых логических ошибках.
Только вот нужно ли? Если снять ограничение на фиксированность входных данных и использовать эти данные в условиях циклов/условиях выходов из рекурсии, то единственное, что мы можем сказать — так это то, что на таких-то наборах входных данных программа зацикливается. А сколько будет элементов в этом наборе? 2? 32? 4096? Бесконечность?
Для этого кода, например:
int i = 2;
while ( i % 2 == 0 || i <= 10000 ) {
    std::cin >> i;
}

"Для i равного 0, 2, 4, 6, ..., 10000 программа зацикливается!"? Смысл такого сообщения? От сообщения вида: "Для i % 2 != 0 && i > 10000 программа зацикливается!" — тоже радости мало...

Другой пример:
MSG msg;
while ( GetMessage ( &msg, 0, 0, 0 ) ) {
    TranslateMessage ( &msg );
    DispatchMessage ( &msg );
}

Этот цикл — это цикл обработки сообщений в Windows и пользы от сообщения анализатора "Если GetMessage никогда не вернёт нуля, то, естественно, программа зациклится" будет нулевая.

Или если программа работает в интерактивном режиме и принимает ввод от пользователя, пока он не наберёт "exit" или "logoff".
Или... [ещё 1024 примера вырезано для экономии места].

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

GC>Может быть создаст юнит-тесты для текстирования этой функции при таких входных условиях.

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

P.S. На часах 3:47, поэтому я извиняюсь, если допустил орфографические ошибки или слова дважды начал писать.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.