Problème de l'arrêt

Imagine que tu aies un programme informatique chargé de trouver le plus grand nombre premier. En théorie, le programme continuera à fonctionner indéfiniment car il n'existe pas de "plus grand" nombre premier définitif. Si un autre programme pouvait affirmer de manière définitive qu'il fonctionnera effectivement à l'infini, il aurait résolu le problème de l'arrêt.

Considérons une machine de Turing simple qui commence dans un état \N( q_0 \N) et se déplace vers la droite si elle rencontre le symbole '0', en le remplaçant par '1', et passe à l'état \N( q_1 \N). Dans l'état \N( q_1 \N), il se déplace vers la droite s'il rencontre le symbole '1', le remplace par '0' et retourne à l'état \N( q_0 \N). Si l'entrée initiale sur la bande est une chaîne continue de "0", cette machine de Turing ne s'arrêtera jamais, car elle a toujours une action disponible à effectuer, ce qui la place dans une boucle infinie.

Considérons un simple script Python qui compte à partir de 1. Ce script, lorsqu'il est exécuté, commence à 1 et incrémente le compte d'une unité à chaque fois, en imprimant le compte actuel. Il continuera théoriquement pour toujours, à moins qu'il ne soit arrêté manuellement.

Python count = 1 while True : print(count)count+=1

En ce qui concerne le problème de l'arrêt, si nous assignons un programme pour déterminer si ce script s'arrête ou non, le programme assigné échouera inévitablement. Le script n'a pas de condition qui mène à l'arrêt, mais sans exécuter le script, notre programme ne peut pas le déterminer. Dans un autre exemple, imagine une fonction récursive en C++ qui s'appelle continuellement elle-même :

C++ void recursive (){recursive();}

C'est un exemple classique de fonction qui s'exécute indéfiniment, provoquant une erreur de débordement de pile. Encore une fois, sans exécuter ce code, un programme peut-il déterminer s'il s'arrête ou s'exécute indéfiniment ? Le problème de l'arrêt suppose qu'il n'existe aucun programme capable de résoudre ce problème pour toutes les entrées possibles et imaginables.

Enfin, examinons un problème dans le domaine de l'intelligence artificielle, et plus précisément de l'apprentissage automatique. Les algorithmes d'apprentissage automatique utilisent souvent des méthodes itératives pour atteindre une solution optimale pour un problème donné. Ce processus itératif peut impliquer un critère de terminaison pour arrêter les itérations. Cependant, il peut arriver que ces critères ne soient pas respectés et que l'algorithme fonctionne indéfiniment. Une fois de plus, serait-il possible de faire en sorte qu'un programme prédise cela avec une précision totale ?

Par exemple, un programme pourrait utiliser des techniques d'analyse statique pour vérifier si une boucle fonctionne avec un compteur qui s'incrémente ou se décrémente constamment vers une condition de terminaison. Si c'est le cas, il peut s'assurer que le programme finira par s'arrêter. D'autres règles heuristiques pourraient identifier des constructions ou des comportements de programmation communs garantissant un arrêt éventuel.

Cependant, ces solutions sont toutes "incomplètes" : elles peuvent vérifier qu'un programme s'arrête lorsque leurs critères sont remplis, mais aucun ensemble de règles ne peut couvrir tous les programmes possibles - soit elles manqueront certains programmes qui s'arrêtent (incomplétude), soit elles jugeront incorrectement certains programmes qui ne s'arrêtent pas comme s'ils s'arrêtaient (inexactitude).

La recherche en IA a également tenté d'appliquer des techniques d'apprentissage automatique au problème de l'arrêt, en formant des modèles pour prédire si certains types de code s'arrêteront. Cependant, ces modèles seraient encore une fois incomplets et imparfaits, car la complexité du problème de l'arrêt dépasse de loin les capacités des algorithmes d'IA actuels.