ubbook/runtime/endless_loop.md

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

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

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

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

Занятный пример — таким образом можно [«опровергнуть» великую теорему Ферма](https://godbolt.org/z/nE7oWf)
```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` контексте — получим [ошибку компиляции](https://godbolt.org/z/98MYzd).

Может показаться, что проблема в том, что условие продолжения цикла не зависит от его тела.
Но и в [исправленной](https://godbolt.org/z/o1Gcqc) версии цикл исчезает
```C++
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, он все равно [может исчезнуть](https://godbolt.org/z/P8YxeT),
если компилятор увидит, что эти операции от цикла не зависят
```C++
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++ просто так нельзя. Отлаживаться принтами с наскоку тоже нельзя.
И строить тесты, проверяющие, что программа не зацикливается, также может оказаться бесполезно.

-----
В C++26 это безумие [исправили](https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2024/p2809r3.html) в отношении **тривиальных** бесконечных циклов: 

Так, например, теперь вот такие циклы
```С++
while (true) {}

for(;;) {}
```
обязаны, как ожидается, зацикливаться и исполнятся бесконечно.

Но стоит добавить в них хоть что-то, как поведение снова неопределено:
```C++
// этот цикл может быть заменен на std::unreachable -- поведение не определено!
while (true) {
    "a meaningless statement";
}
```