Liste de problèmes indécidables
En calculabilité, un problème indécidable est un problème de décision qui ne peut être résolu par aucun algorithme. Cette notion ne doit pas être confondue avec celle d'énoncé logique indécidable ; la différence est développée dans l'article Décidabilité.
Problèmes en logique
- Le problème de la décision (aussi appelé Entscheidungsproblem).
- La vérification des types et l'inférence de types dans le système F[1].
- La validité sur les modèles finis en logique du premier ordre, par le théorème de Trakhtenbrot.
Problèmes portant sur les modèles de calcul
- Le problème de l'arrêt.
- Plus généralement, toute propriété non-triviale des machines de Turing qui ne dépend que de leur comportement, par le théorème de Rice.
- Déterminer si une machine de Turing est un castor affairé.
- L'universalité d'un automate à pile non-déterministe (déterminer s'il accepte tous les mots ou non).
Problèmes d'algèbre linéaire
- Le problème des matrices mortelles pour les matrices 3×3 et plus.
Problèmes sur les groupes
- Le problème du mot.
- Le problème de conjugaison (en).
- Le problème de l'isomorphisme (en).
Problèmes sur les mots et les grammaires
- Le problème de correspondance de Post.
- Déterminer si une grammaire non contextuelle engendre tous les mots, ou si elle est ambiguë, ou si elle est équivalente à une autre grammaire non contextuelle.
Divers
- Le calcul de la complexité de Kolmogorov.
- Le dixième problème de Hilbert.
- Déterminer si un λ-terme est normalisable, ou fortement normalisable.
Notes
- J. B. Wells, « Typability and type checking in the second-order lambda-calculus are equivalent and undecidable », Comput. Sci. Dept., Boston Univ., , p. 176–185 (CiteSeerx 10.1.1.31.3590)
Portail des mathématiques
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons – Attribution – Partage à l’identique. Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.