DÉCIDABILITÉ

CHURCH ALONZO (1903-1995)

  • Écrit par 
  • Françoise ARMENGAUD
  •  • 611 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 « le plus fidèle des disciples de Frege ». Réputé « platonisant », il défend une conception délibérément réaliste de la propo […] Lire la suite☛ http://www.universalis.fr/encyclopedie/alonzo-church/#i_31221

FORMALISME

  • Écrit par 
  • Étienne BALIBAR, 
  • Pierre MACHEREY
  •  • 5 002 mots
  •  • 1 média

Dans le chapitre « La démonstration formalisée »  : […] 3. On définit un sous-ensemble de formules qu'on appelle les axiomes du système. Le plus souvent, on peut décider effectivement si une formule donnée est un axiome, et on parle alors de théorie axiomatique. Intuitivement, les axiomes représentent des propositions qui sont considérées comme vraies sans démonstration, mais cette référence est en toute rigueur inutile. 4. On définit une liste finie […] Lire la suite☛ http://www.universalis.fr/encyclopedie/formalisme/#i_31221

INFORMATIQUE - Principes

  • Écrit par 
  • Jacques HEBENSTREIT
  •  • 3 097 mots
  •  • 2 médias

Dans le chapitre « Algorithmes et décidabilité »  : […] Un algorithme est une suite finie de règles à appliquer dans un ordre déterminé à un nombre fini de données pour arriver, en un nombre fini d'étapes, à un certain résultat, et cela indépendamment des données ; par exemple, l'algorithme de l'addition permet de faire l'addition de deux nombres quelconques en partant des chiffres les plus à droite et en opérant de droite à gauche. Un algorithme étant […] Lire la suite☛ http://www.universalis.fr/encyclopedie/informatique-principes/#i_31221

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 qui ne sont pas démontrables et le système est dit cohérent ; au cas où ce système comporte l'opérateur de n […] Lire la suite☛ http://www.universalis.fr/encyclopedie/metalogique/#i_31221

MODÈLES THÉORIE DES

  • Écrit par 
  • Daniel ANDLER, 
  • Daniel LASCAR, 
  • Gabriel SABBAGH
  •  • 7 958 mots

Dans le chapitre « Théorie des modèles et algèbre traditionnelle »  : […] Il devrait être maintenant clair que les débuts de la théorie des modèles sont assez voisins de l'algèbre générale. Il n'est donc pas étonnant qu'il y ait eu de nombreuses applications de cette théorie à des problèmes purement algébriques. Il faut cependant dire que les premières applications « essentielles » de la théorie des modèles à l'algèbre datent de la fin des années cinquante. Jusque-là, l […] Lire la suite☛ http://www.universalis.fr/encyclopedie/theorie-des-modeles/#i_31221

RÉCURSIVITÉ, logique mathématique

  • Écrit par 
  • Kenneth Mc ALOON, 
  • Bernard JAULIN, 
  • Jean-Pierre RESSAYRE
  •  • 9 371 mots

Dans le chapitre « Indécidabilité et décidabilité »  : […] L'étude de l'indécidabilité des théories mathématiques relève de la théorie des fonctions récursives en deux sens : en premier lieu, car un résultat d'indécidabilité signifie qu'une certaine fonction, à savoir la fonction caractéristique de l'ensemble des théorèmes (modulo une bonne numération des formules du langage de la théorie), n'est pas récursive, et, en second lieu, car l'indécidabilité d'u […] Lire la suite☛ http://www.universalis.fr/encyclopedie/recursivite-logique-mathematique/#i_31221

ROBINSON JULIA (1919-1985)

  • Écrit par 
  • Gabriel SABBAGH
  •  • 1 026 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 académique contrariée par une réglementation qui interdisait à ladite université de recruter comme […] Lire la suite☛ http://www.universalis.fr/encyclopedie/julia-robinson/#i_31221

SKOLEM ALBERT THORALF (1887-1963)

  • Écrit par 
  • Gabriel SABBAGH
  •  • 438 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, en tout état de cause, un rang honorable parmi les mathématiciens de son époque, sont éclipsés par ses éclatantes contr […] Lire la suite☛ http://www.universalis.fr/encyclopedie/albert-thoralf-skolem/#i_31221

TARSKI ALFRED (1902-1983)

  • Écrit par 
  • Jan SEBESTIK
  •  • 1 076 mots

Dans le chapitre « De la « définissabilité » aux modèles et à la décision »  : […] Après le concept de vérité, Tarski a précisé un autre concept sémantique essentiel, celui de conséquence logique, qui avait été défini pour la première fois par Bolzano, en 1837, pour la langue usuelle. Pour Tarski, en effet, l'« énoncé X suit logiquement des énoncés de la classe K si et seulement si tout modèle de la classe K est aussi un modèle de l'énoncé X ». Tarski a apporté des renouvellemen […] Lire la suite☛ http://www.universalis.fr/encyclopedie/alfred-tarski/#i_31221

TURING ALAN MATHISON (1912-1954)

  • Écrit par 
  • B. Jack COPELAND
  •  • 1 552 mots
  •  • 1 média

Dans le chapitre « Jeunesse et études universitaires  »  : […] Alan Mathison Turing naît le 23 juin 1912 à Londres. Fils d'un fonctionnaire britannique de l'administration indienne, Turing commence à étudier les mathématiques au King's College de l'université de Cambridge en 1931. Après avoir obtenu son diplôme en 1934, il obtient une bourse d'enseignant chercheur au King's College en reconnaissance de ses travaux sur la théorie des probabilités. En 1936, l […] Lire la suite☛ http://www.universalis.fr/encyclopedie/alan-mathison-turing/#i_31221