DÉCIDABILITÉ
CHURCH ALONZO (1903-1995)
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
FORMALISME
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
INFORMATIQUE - Principes
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
MÉTALOGIQUE
É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
MODÈLES THÉORIE DES
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
RÉCURSIVITÉ, logique mathématique
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
ROBINSON JULIA (1919-1985)
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
SKOLEM ALBERT THORALF (1887-1963)
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
TARSKI ALFRED (1902-1983)
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
TURING ALAN MATHISON (1912-1954)
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