Liste de problèmes indécidables
From Wikipedia, the free encyclopedia
Cet article est une ébauche concernant les mathématiques.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
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é.
- 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 programmes 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).
- Déterminer si un λ-terme est normalisable, ou fortement normalisable.
Problèmes d'algèbre linéaire
- Le problème des matrices mortelles pour les matrices 3×3 et plus.
