DÉCIDABILITÉ

Ce sujet est traité dans les articles suivants :

1.  CHURCH ALONZO (1903-1995)

Écrit par : Françoise ARMENGAUD

… *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 »,… Lire la suite

2.  FORMALISME

Écrit par : Étienne BALIBAR, Pierre MACHEREY

Dans le chapitre "La démonstration formalisée"  : … 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 besoin de « rechercher »). Cette notion est importante dans les applications techniques de la… Lire la suite

3.  INFORMATIQUE - Principes

Écrit par : Jacques HEBENSTREIT

Dans le chapitre "Algorithmes et décidabilité"  : … 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 comme donnée, permettra de savoir si ce programme fournira des résultats au bout d'un temps fini… Lire la suite

4.  LOGIQUE MATHÉMATIQUE

Écrit par : Daniel ANDLER, Roger MARTIN

Dans le chapitre "Effectivité, décidabilité"  : … *La notion de méthode effective de calcul, ou encore d'algorithme, accompagne les mathématiques depuis les origines. Soit (Pi)i∈I une famille de problèmes formulés en termes mathématiques, telle que, pour chaque i de I, le problème Pi admette une réponse Ri… Lire la suite

5.  MÉTALOGIQUE

Écrit par : Françoise ARMENGAUD

… *É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… Lire la suite

6.  MODÈLES THÉORIE DES

Écrit par : Daniel ANDLER, Daniel LASCAR, Gabriel SABBAGH

Dans le chapitre "Théorie des modèles et mathématiques"  : … é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 ne connaisse pas de théorème général, il est facile, dans… Lire la suite

7.  RÉCURSIVITÉ, logique mathématique

Écrit par : Kenneth Mc ALOON, Bernard JAULIN, Jean-Pierre RESSAYRE

Dans le chapitre "Définition logique"  : … 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 de N^p appartient ou non à X. Ainsi, les ensembles finis, l'ensemble des… Lire la suite

8.  ROBINSON JULIA (1919-1985)

Écrit par : Gabriel SABBAGH

… 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. En collaboration avec Martin Davis et Hilary Putnam, qui… Lire la suite

9.  SKOLEM ALBERT THORALF (1887-1963)

Écrit par : Gabriel SABBAGH

… *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… Lire la suite

10.  TARSKI ALFRED (1902-1983)

Écrit par : Jan SEBESTIK

Dans le chapitre "De la « définissabilité » aux modèles et à la décision"  : … é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-… Lire la suite

11.  TURING ALAN MATHISON (1912-1954)

Écrit par : B. Jack COPELAND

Dans le chapitre "Jeunesse et études universitaires "  : … 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 n'est décidable. Ce résultat et bien d'autres, notamment les théorèmes d'incomplétude du… Lire la suite