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é.