Définition de indécidabilité | Babel Free

Définitions

État de ce qui n'est pas décidable.

Exemples

“Ensuite, en appliquant le lemme diagonal à des formules convenablement choisies, on déduit successivement le théorème d'indécidabilité de Church dans la sous-section 4.2, le théorème de Tarski sur la non-définissabilité de la vérité arithmétique dans la sous-section 4.3, puis le premier théorème d'incomplétude de Gödel dans la sous-section 4.4, et enfin le second théorème d'incomplétude de Gödel dans la sous-section 4.5, ici sous une forme non optimale puisqu'établi seulement seulement pour les théories au moins aussi fortes que la théorie de Zermelo, alors que l'arithmétique de Peano serait suffisante.”

Niveau CECR