Les boucles infinie insoluble ?

Aujourd'hui je fais une réaction un peu tardive sur un article de Korben à propos d'un étudiant qui aurait réussi à concevoir un programme permettant de sortir d'une boucle infinie.

Malheureusement pour lui, un tel programme ne peux pas exister.


Je m'explique. La théorie de l'étudiant est que si le programme revient toujours au même état mémoire dans une boucle, alors il considère que cette boucle est infinie, ce qui est tout à fait faux.

Il y a le cas où les variables du programme continue d'évoluer dans la boucle infinie. Le programme ne repasse alors jamais deux fois dans l'état mémoire alors que la boucle ne se termine jamais.

Voici un petit exemple de boucle en C très simple qui ne repasse jamais pas le même état mémoire :

int i;
for (i = 0; i > -1; i++)
{ }

La boucle ne revient jamais au même état mémoire (une variable évolue constamment) et donc ne serait jamais qualifié de boucle infinie par un programme analysant la mémoire. Pourtant le programme ne sortira théoriquement jamais de sa boucle.

NB : En réalité cette dernière boucle a bien une fin. Quelqu'un serait-il capable de dire pourquoi ? :p

Il existe le cas aussi tout à fait contraire. Une boucle qui attends l'appui d'une touche (donc un événement externe) est une boucle dont l'état mémoire n'évolue pas alors qu'elle a bien une fin !

Il y a aussi bien évidemment le fameux paradox de la boucle infinie :

Etiquette Debut
Si c'est une boucle infinie alors fin
Sinon, retourner à Debut

Si ce n'est pas une boucle infinie, alors on retourne au début et on rentre alors dans une boucle infinie (paradoxe !), et si c'est une boucle infinie, on quitte le programme (et donc ce n'est pas une boucle infinie, paradoxe !).