Exercices corrigés — Calculabilité et décidabilité (OCaml (option informatique))

10 exercices avec corrigé rédigé, du plus simple au plus exigeant.

• Décidable ou non ?
• Un décideur
• Le piège du « il suffit d'exécuter »
• Semi-décider l'arrêt
• Syracuse, problème ouvert mais pas indécidable
• Comprendre une réduction
• La diagonale
• Une propriété sémantique indécidable
• Le castor affairé (busy beaver)
• Décidable, semi-décidable, ou ni l'un ni l'autre ?

Lire le cours de ce chapitre