DECIDABILITE
Publié le 22/02/2012
Extrait du document
Source: http://www.peiresc.org/DINER/Lexique.pdf
La décidabilité est une des propriétés des systèmes formels. Un système est décidable si et seulement si il existe un procédé effectif pour déterminer si une formule quelconque est ou n'est pas un théorème. La notion de procédé effectif est liée à la notion de récursivité. Seuls des systèmes assez pauvres sont décidables. Le théorème d'incomplétude de Gödel établit l'indécidabilité de systèmes assez riches.