5 minutes Lebesgue

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
20 September 2016
étudiant
étudiant
Mathematical field: 
computer science, logic
Keywords: 
algorithme, impossibilité, problème de l'arrêt
AttachmentSize
File 5min-guirardel.mp435.82 MB

Partners

Irmar LMJL ENS Rennes LMBA LAREMA

Affiliation

ANR CNRS Rennes 1 Rennes 2 Nantes INSA Rennes INRIA ENSRennes UBO UBS Angers UBL