indécidabilité

nom féminin

Définitions de indécidabilité


  • Propriété d'une formule indécidable.
  • Propriété d'une théorie dans laquelle il n'existe pas de procédé effectif permettant de décider, pour toute formule, si elle est ou non démontrable. (Une théorie assez puissante pour formaliser l'arithmétique est indécidable si elle est consistante ; le calcul des prédicats est indécidable.)