Décidabilité

"décidabilité" dans l'encyclopédie

• SKOLEM ALBERT THORALF (1887-1963)

  • Écrit par Gabriel SABBAGH
  • 2 411 mots

  Parmi ses premiers travaux, il faut signaler ses recherches de logique algébrique sur les treillis, qui eurent une descendance abondante et auxquelles il était très attaché, et surtout son invention, en 1919 (soit vingt à trente ans avant les travaux de Tarski sur la décidabilité), de la méthode d'élimination des quantificateurs, qu'il applique pour établir la décidabilité de plusieurs théories algébriques.

• ROBINSON JULIA (1919-1985)

  • Écrit par Gabriel SABBAGH
  • 5 566 mots

  Le sujet est toujours vivant, comme des travaux de Cherlin et Denef l'ont montré, et peut-être étroitement lié au problème de la décidabilité pour les équations diophantiennes homogènes. Le problème de la décidabilité pour les équations diophantiennes tout court, le célèbre dixième problème de Hilbert, fut au cœur des préoccupations de Julia Robinson à partir de la fin des années cinquante.

• PROPOSITIONNEL CALCUL

  • Écrit par Françoise ARMENGAUD
  • 1 503 mots

  Elle présente les propriétés de non-contradiction, de décidabilité et de complétude. Historiquement, les stoïciens sont à l'origine de l'étude des lois qui régissent les rapports des propositions entre elles. Le conditionnel matériel remonte à Philon de Mégare. Ces lois étaient connues des logiciens du Moyen Âge, mais c'est à la fin du xixe siècle que leur étude fut reprise et renouvelée.

• CHURCH ALONZO (1903-1995)

  • Écrit par Françoise ARMENGAUD
  • 3 381 mots

  Mais Church est surtout connu pour ses travaux sur la décidabilité dans les systèmes formels. Le symbolisme arithmétique nous permet de formuler des propositions dont on ne peut déterminer la valeur de vérité par aucune technique connue de calcul ou de raisonnement. Ainsi la conjecture de Goldbach, certaines propositions élémentaires de l'arithmétique n'ont jusqu'ici reçu aucune preuve.

• TARSKI ALFRED (1902-1983)

  • Écrit par Jan SEBESTIK
  • 5 908 mots

  Dans plusieurs travaux, Tarski a étudié la complétude des théories et le problème de la décision ; il a établi la décidabilité et l'indécidabilité de certaines théories mathématiques (en particulier, il a montré que l'algèbre et la géométrie élémentaires sont des théories décidables). Tarski a toujours accepté sans restriction, comme base de son travail logico-mathématique, la théorie des ensembles et il n'hésitait pas à recourir à des théories très fortes – ce qui lui a donné une liberté que s'interdisaient aussi bien Brouwer et les intuitionnistes que l'école de la métamathématique finitiste (Hilbert).