✦ COGNITIA · Cours interactif

Algorithmes : puissance, limites et performance

Comprendre ce qu’un ordinateur peut résoudre, mesurer l’efficacité des algorithmes et repousser les limites du calcul.

Chapitre 5 / 12

Décidabilité et indécidabilité

Ce qu’aucun programme général ne peut résoudre

Un langage est décidable s’il existe une machine qui s’arrête sur toute entrée et décide correctement son appartenance.

💡 À retenir : Le problème de l’arrêt est un exemple fondamental d’indécidabilité.