endless_loop.md

Бесконечные циклы и проблема останова

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

Но в стандартах C и C++ зачем-то сказано, что валидная программа должна либо гарантированно завершаться, либо гарантированно производить обозреваемые эффекты: запрашивать ввод-вывод, взаимодействовать с volatile переменными и подобное. А иначе поведение программы неопределенное. Так что «правильные» компиляторы C++ настолько суровы, что способны решать алгоритмически неразрешимые задачи.

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

Занятный пример — таким образом можно «опровергнуть» великую теорему Ферма

#include <iostream>

int fermat () {
    const int MAX = 1000;
    int a=1,b=1,c=1;
    while (1) {
        if ( (a*a*a) == (b*b*b) + (c*c*c) ) return 1;
        a++;
        if (a>MAX) {
            a=1;
            b++;
        }
        if (b>MAX) {
            b=1;
            c++;
        }
        if (c>MAX) {
            c=1;
        }
    }
    return 0;
}

int main () {
    if (fermat()) {
        std::cout << "Fermat's Last Theorem has been disproved.\n";
    } else {
        std::cout << "Fermat's Last Theorem has not been disproved.\n";
    }
    return 0;
}

Компилятор увидел, что единственный выход из цикла — return 1. У цикла нет никаких видимых эффектов. Так что компилятор просто заменил его на return 1

Если же попытаться узнать, что за тройку «нашла» программа — цикл вернется.

В constexpr контексте — получим ошибку компиляции.

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

int fermat() {
    const int MAX = 1000;
    int a=1,b=1,c=1;
    while ((a*a*a) != ((b*b*b)+(c*c*c))) {
        a++;
        if (a>MAX) {
            a=1;
            b++;
        }
        if (b>MAX) {
            b=1;
            c++;
        }
        if (c>MAX) {
            c=1;
        }
    }
    return 1;
}

Даже если в цикле будут операции I/O, он все равно может исчезнуть, если компилятор увидит, что эти операции от цикла не зависят

int fermat () {
    const int MAX = 1000;
    int a=1,b=1,c=1;
    while (1) {
        if ( (a*a*a) == (b*b*b) + (c*c*c) ) {
            std::cout << "Found!\n";
            return 1;
        }
        a++;
        if (a>MAX) {
            a=1;
            b++;
        }
        if (b>MAX) {
            b=1;
            c++;
        }
        if (c>MAX) {
            c=1;
        }
    }
    return 0;
}

Так что предполагать, что программа в каких-то случаях должна зацикливаться, и строить под эти случаи тесты в C/C++ просто так нельзя. Отлаживаться принтами с наскоку тоже нельзя. И строить тесты, проверяющие, что программа не зацикливается, также может оказаться бесполезно.