Vincent Guirardel, Le problème de l'arrêt d'une machine de Turing

Peut-on savoir à l'avance si un programme d'ordinateur va s'arrêter, ou s'il va boucler à l'infini ? Dans les années 30, Church et Turing ont démontré qu'il n'existait pas d'algorithme qui répond à cette question... avant même l'existence des ordinateurs.

IRMAR
URL de Vidéo distante
Niveau
étudiant
Mathematical field
computer science
Keywords
algorithme
impossibilité
problème de l'arrêt