DÉCIDABILITÉ

Articles

• CHURCH ALONZO (1903-1995)

  • Écrit par Françoise ARMENGAUD
  • 616 mots

  Mathématicien et logicien, philosophe et historien de la logique, Alonzo Church est né le 14 juin 1903 à Washington et mort le 11 août 1995 à Hudson (Ohio). Professeur de mathématiques à l'université de Princeton, directeur du Journal of Symbolic Logic, il est selon Kneale «...

• FORMALISME

  • Écrit par Étienne BALIBAR, Pierre MACHEREY
  • 5 001 mots
  • 1 média
  ...nécessairement possible de déterminer par un procédé mécanique si une formule quelconque donnée est un théorème. Lorsque c'est le cas, on parle de théorie « décidable » : c'est en somme un système formel tel qu'une machine convenablement construite puisse sélectionner tous les théorèmes (qu'on n'a donc pas...

• INFORMATIQUE - Principes

  • Écrit par Jacques HEBENSTREIT
  • 3 060 mots
  • 2 médias
  ...trancher la question. Malheureusement, et ce résultat est d'une extrême importance, on démontre qu'il est impossible de construire un tel algorithme ; ce problème est indécidable. En termes de programmation, cela revient à dire qu'il est impossible d'écrire un programme qui, prenant un autre programme...

• MÉTALOGIQUE

  • Écrit par Françoise ARMENGAUD
  • 422 mots

  Étude des propriétés des systèmes logiques. Une fois construit comme système, un formalisme peut lui-même devenir objet d'étude. Les propriétés les plus importantes des systèmes formels sont les suivantes : tout d'abord, dans l'ensemble des formules constructibles dans un système, il en est...

• MODÈLES THÉORIE DES

  • Écrit par Daniel ANDLER, Daniel LASCAR, Gabriel SABBAGH
  • 7 801 mots
  ...Le problème de la recherche d'invariants pour l'équivalence élémentaire est également lié à un des problèmes fondamentaux de la logique : celui de la décidabilité (cf. la partie Décidabilité du chapitre Les notions fondamentales : la logique du premier ordre, in logique mathématique). Encore qu'on...

• RÉCURSIVITÉ, logique mathématique

  • Écrit par Kenneth Mc ALOON, Bernard JAULIN, Jean-Pierre RESSAYRE
  • 8 914 mots
  ..., on va introduire les notions d'ensembles récursifs et récursivement énumérables. Un ensemble X ⊂ N^p est dit récursif (on dit aussi décidable) si sa fonction caractéristique est récursive. Intuitivement, cela signifie qu'il existe un algorithme permettant de décider si un élément quelconque...

• ROBINSON JULIA (1919-1985)

  • Écrit par Gabriel SABBAGH
  • 1 013 mots

  Née le 8 décembre 1919 à Saint. Louis, dans le Missouri, Julia Robinson fut une logicienne éminente et la mathématicienne américaine la plus connue du xx^e siècle. Épouse d'un mathématicien de grand talent, Raphael M. Robinson, professeur à l'université de Californie à Berkeley, elle vit sa carrière...

• SKOLEM ALBERT THORALF (1887-1963)

  • Écrit par Gabriel SABBAGH
  • 439 mots

  Logicien et mathématicien norvégien né à Sandsvaer et mort à Oslo. Ses travaux en algèbre (théorème de Skolem-Noether pour les algèbres associatives) et en théorie des nombres (introduction des méthodes p-adiques dans la théorie des équations diophantiennes), qui lui vaudraient,...

• TARSKI ALFRED (1902-1983)

  • Écrit par Jan SEBESTIK
  • 1 074 mots
  ...opérant sur des ensembles finis). 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...

• TURING ALAN MATHISON (1912-1954)

  • Écrit par B. Jack COPELAND
  • 1 561 mots
  • 1 média
  ...Hilbert, cherche une méthode fiable permettant de décider quels énoncés mathématiques sont prouvables ou non dans un système mathématique formel donné. En 1936, Turing et Church montrent, chacun de son côté, que ce problème n'a en général pas de solution, prouvant qu'aucun système arithmétique formel cohérent...