Recherchez sur tout Techno-Science.net
       
Techno-Science.net : Suivez l'actualité des sciences et des technologies, découvrez, commentez
Catégories
Techniques
Sciences
Encore plus...
Techno-Science.net
Partenaires
Organismes
 CEA
 ESA
Sites Web
Photo Mystérieuse

Que représente
cette image ?
 A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | +
Décidabilité et indécidabilité

En logique mathématique, le terme décidabilité recouvre deux concepts liés : la décidabilité logique et la décidabilité algorithmique.

L'indécidabilité est la négation de la décidabilité. Dans les deux cas il s'agit de formaliser l'idée qu'on ne peut pas toujours conclure lorsque l'on se pose une question, même si celle-ci est sous forme logique (La logique (du grec logikê, dérivé de logos (λόγος), terme inventé par Xénocrate signifiant à la fois raison, langage, et raisonnement) est dans une première approche...).

Décidabilité, indécidabilité (En logique mathématique, le terme décidabilité recouvre deux concepts liés : la décidabilité logique et la décidabilité algorithmique.) d'un énoncé dans un système logique

Une proposition (on dit aussi énoncé) est dite décidable (En logique mathématique, le terme décidabilité recouvre deux concepts liés : la décidabilité logique et la décidabilité algorithmique.) dans une théorie (Le mot théorie vient du mot grec theorein, qui signifie « contempler, observer, examiner ». Dans le langage courant, une théorie est une idée ou une connaissance spéculative, souvent basée sur...) axiomatique, si on peut la démontrer ou démontrer sa négation dans le cadre de cette théorie. Un énoncé mathématique (Les mathématiques constituent un domaine de connaissances abstraites construites à l'aide de raisonnements logiques sur des concepts tels que les nombres, les figures, les structures et les transformations. Les...) est donc indécidable dans une théorie s'il est impossible de le déduire, ou de déduire sa négation, à partir des axiomes. Pour distinguer cette notion d'indécidabilité de la notion d'indécidabilité algorithmique (L'algorithmique est l’ensemble des règles et des techniques qui sont impliquées dans la définition et la conception d'algorithmes, c'est à dire de processus systématiques de...) (voir ci-dessous), on dit aussi que l'énoncé est indépendant du système d'axiomes.

En termes plus concrets, cela veut dire qu'on demande au système de fournir une conclusion sans lui avoir fourni (Les Foúrnoi Korséon (Grec: Φούρνοι Κορσέων) appelés plus communément...) suffisamment d'hypothèses. Ainsi, l'âge du capitaine d'un bateau (Un bateau est une construction humaine capable de flotter sur l'eau et de s'y déplacer, dirigé ou non par ses occupants. Il répond aux besoins du transport maritime ou fluvial, et permet diverses activités telles que...) est indécidable en fonction du tonnage et de la vitesse (On distingue :) du navire (Un navire est un bateau destiné à la navigation maritime, c'est-à-dire prévu pour naviguer au-delà de la limite où cessent de s'appliquer les règlements techniques de sécurité de...).

En logique classique, d'après le théorème (Un théorème est une proposition qui peut être mathématiquement démontrée, c'est-à-dire une assertion qui peut être établie comme vraie au travers d'un raisonnement logique construit à partir...) de complétude (On parle de complétude en mathématiques dans des sens très différents. On dit d'un objet mathématiques qu'il est complet pour exprimer que rien ne peut lui être ajouté, en...), une proposition est indécidable dans une théorie s'il existe des modèles de la théorie où la proposition est fausse et des modèles où elle est vraie. On utilise souvent des modèles, pour montrer qu'un énoncé est indépendant d'un système d'axiomes (dans ce cadre on préfère employer indépendant qu'indécidable). La propriété utilisée dans ce cas n'est pas le théorème de complétude mais sa réciproque, très immédiate, appelée parfois fidélité. Probablement est-ce là d'ailleurs la première apparition de la notion de modèle, avec la construction au XIXème siècle (Un siècle est maintenant une période de cent années. Le mot vient du latin saeculum, i, qui signifiait race, génération. Il a ensuite indiqué la durée d'une génération humaine et faisait 33 ans 4 mois (d'où peut être l'âge du...) de modèles des géométries non classiques, ne vérifiant pas l'axiome (Le mot axiome vient du grec αξιωμα (axioma), qui signifie "qui est considéré comme digne ou convenable" ou "qui est considéré comme évident en soi". Pour certains...) des parallèles. Si l'on admet le fait assez intuitif que la géométrie euclidienne (La géométrie euclidienne commence avec les Éléments d'Euclide, qui est à la fois une somme des connaissances géométriques de l'époque et une tentative de formalisation mathématique de ces connaissances. Les notions de...) est cohérente — la négation de l'axiome des parallèles ne se déduit pas des autres axiomes — l'axiome des parallèles est bien alors indépendant des autres axiomes de la géométrie (La géométrie est la partie des mathématiques qui étudie les figures de l'espace de dimension 3 (géométrie euclidienne) et, depuis le...), ou encore indécidable dans le système formé des axiomes restant.

Une théorie mathématique pour laquelle tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) énoncé est décidable est dite complète, sinon elle est dite incomplète. Beaucoup de théories mathématiques sont naturellement incomplètes, parce qu'il y a évidemment des énoncés qui ne sont pas déterminés par les axiomes (théorie des groupes, des anneaux, ...) . Certaines théories, comme la théorie des corps algébriquement clos, celle des corps réels clos, ou encore l'arithmétique de Presburger (L'arithmétique de Presburger est une théorie du premier ordre, dans le langage de l'arithmétique de Peano sans la multiplication, c’est-à-dire avec seulement...) sont complètes. Le théorème d'incomplétude (On parle de complétude en mathématiques dans des sens très différents. On dit d'un objet mathématiques qu'il est complet pour exprimer que rien ne peut lui être ajouté, en...) de Gödel nous garantit que toute théorie axiomatique cohérente, et suffisamment puissante pour représenter l'arithmétique (L'arithmétique est une branche des mathématiques qui comprend la partie de la théorie des nombres qui utilise des méthodes de la géométrie algébrique et de la théorie des groupes. On l'appelle plus généralement la « science des...) de Peano (l'arithmétique usuelle), est incomplète, pourvu qu'elle soit axiomatisée de façon que l'on puisse décider au sens (SENS (Strategies for Engineered Negligible Senescence) est un projet scientifique qui a pour but l'extension radicale de l'espérance de vie humaine. Par une évolution progressive allant du ralentissement du vieillissement,...) algorithmique (voir ci-dessous) si un énoncé est ou non un axiome. Cette dernière hypothèse qui semble un peu compliquée à énoncer est très naturelle et vérifiée par les théories axiomatiques usuelles en mathématiques.

Décidabilité, indécidabilité d'un problème de décision (En logique mathématique, on appelle problème de la décision le fait de déterminer de façon mécanique, par un algorithme, si un énoncé est un théorème de la logique égalitaire du premier ordre,...)

Définition (Une définition est un discours qui dit ce qu'est une chose ou ce que signifie un nom. D'où la division entre les définitions réelles et les définitions nominales.)

Un problème de décision est dit décidable s'il existe un algorithme, une procédure mécanique (Dans le langage courant, la mécanique est le domaine des machines, moteurs, véhicules, organes (engrenages, poulies, courroies, vilebrequins, arbres de...) qui termine en un nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) fini d'étapes, qui le décide, c'est-à-dire qui réponde par oui ou par non à la question posée par le problème. S'il n'existe pas de tels algorithmes, le problème est dit indécidable. Par exemple, le problème de l'arrêt est indécidable. On peut formaliser la notion de fonction calculable (Une fonction calculable (ou fonction récursive) est une fonction semi-calculable (ou fonction partielle récursive) qui est aussi totale, c'est-à-dire définie pour toute entrée (en tout point). Ce sont les fonctions calculées par une machine de...) par algorithme, ou par procédure mécanique de diverses façons, comme par exemple en utilisant les machines de Turing. Toutes les méthodes utilisées se sont révélées équivalentes dès qu'elles étaient suffisamment générales, ce qui constitue un argument pour la thèse (Une thèse (du nom grec thesis, se traduisant par « action de poser ») est l'affirmation ou la prise de position d'un locuteur, à...) de Church : les fonctions calculables par une procédure mécanique sont bien celles qui sont calculées selon l'un de ces modèles de calcul. La thèse de Church est indispensable pour interpréter de la façon attendue une preuve d'indécidabilité.

En cas d'ambiguïté possible, on peut parler d’indécidabilité algorithmique, pour distinguer cette notion de l’indécidabilité logique exposée dans le paragraphe précédent (ou parfois de décidabilité au sens de Turing pour la décidabilité algorithmique, et de décidabilité au sens de Gödel pour la décidabilité logique).

Dire qu'un problème est indécidable ne veut pas dire que les questions posées sont insolubles mais seulement qu'il n'existe pas de méthode unique et bien définie, applicable d'une façon mécanique, pour répondre à toutes les questions, en nombre infini (Le mot « infini » (-e, -s ; du latin finitus, « limité »), est un adjectif servant à qualifier quelque chose qui...), rassemblées dans un même problème.

Ensembles décidables et indécidables

Un sous-ensemble (En mathématiques, un ensemble A est un sous-ensemble ou une partie d’un ensemble B, ou encore B est sur-ensemble de A, si tout élément du sous-ensemble A est aussi élément du sur-ensemble B. Il peut par contre y avoir des éléments de B...) des entiers naturels est dit décidable, quand le problème de l'appartenance d'un entier quelconque à cet ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une...) est décidable, indécidable sinon. On généralise directement aux n-uplets d'entiers. On dit aussi d'un ensemble décidable qu'il est récursif. Le complémentaire d'un ensemble décidable est décidable. On montre en théorie de la calculabilité (La théorie de la calculabilité (appelée aussi parfois théorie de la récursion) est une branche de la logique mathématique et de l'informatique théorique. Alors que la notion intuitive de...) qu'un ensemble récursivement énumérable (Intuitivement un ensemble est récursivement énumérable s'il existe un procédé mécanique (en gros qui peut être réalisé par un ordinateur) qui liste ses éléments. On dirait aussi...) dont le complémentaire est récursivement énumérable est récursif (c'est-à-dire décidable).

On généralise ces notions aux langages formels, par des codages " à la Gödel ". Il est possible aussi de les définir directement. Dans le cas des théories logiques (closes, donc par déduction), on parle alors de théorie décidable, ou de théorie indécidable. Ces notions ne doivent pas être confondues avec celles de théorie complète et théorie incomplète vues au paragraphe précédent. Quand on parle d'une théorie décidable ou indécidable, il s'agit forcément de décidabilité algorithmique et jamais de décidabilité logique. A contrario, quand on parle d'énoncé ou de proposition décidable ou indécidable, c'est forcément de décidabilité logique qu'il s'agit.

Exemples d'ensembles et de problèmes décidables

Tous les sous-ensembles finis des entiers sont décidables (il suffit de tester l'égalité à chacun des entiers de l'ensemble). On peut construire un algorithme pour décider si un entier naturel est pair ou non (on fait la division (La division est une loi de composition qui à deux nombres associe le produit du premier par l'inverse du second. Si un nombre est non nul, la fonction...) par deux, si le reste est zéro (Le chiffre zéro (de l’italien zero, dérivé de l’arabe sifr, d’abord transcrit zefiro en italien) est un symbole marquant une position vide...), le nombre est pair, si le reste est un, il ne l'est pas), donc l'ensemble des entiers naturels pairs est décidable ; il en est de même de l'ensemble des nombres premiers. Notons qu'un ensemble peut être théoriquement décidable sans qu'en pratique la décision puisse être faite, parce que celle-ci nécessiterait trop de temps (Le temps est un concept développé par l'être humain pour appréhender le changement dans le monde.) (plus que l'âge de l'univers) ou trop de ressources (plus que les atomes (Un atome (du grec ατομος, atomos, « que l'on ne peut diviser ») est la plus petite partie d'un corps simple pouvant se...) de l'univers). L'objet (De manière générale, le mot objet (du latin objectum, 1361) désigne une entité définie dans un espace à trois dimensions, qui a une fonction précise, et qui peut être désigné par une étiquette verbale. Il est défini par...) de la théorie de la complexité (La théorie de la complexité s'intéresse à l'étude formelle de la difficulté des problèmes en informatique. Elle se distingue de la théorie de la calculabilité qui s'attache à savoir si un problème peut être résolu par un...) est d'étudier les problèmes de décision en prenant en compte ressource et temps de calcul.

Le problème de savoir si une proposition est vraie dans l'arithmétique de Presburger, c'est-à-dire dans la théorie des nombres entiers naturels avec l'addition (L'addition est une opération élémentaire, permettant notamment de décrire la réunion de quantités ou l'adjonction de grandeurs extensives de même nature, comme les longueurs, les aires, ou les...) mais sans la multiplication (La multiplication est l'une des quatre opérations de l'arithmétique élémentaire avec l'addition, la soustraction et la division .), est décidable.

Exemples de problèmes indécidables

  • Le problème de l'arrêt. Dans ce cas, les questions portent sur tous les programmes informatiques (dans un langage suffisamment puissant, tel que tous ceux qui sont utilisés en pratique) et sur tous les états initiaux possibles de la mémoire (D'une manière générale, la mémoire est le stockage de l'information. C'est aussi le souvenir d'une information.) (définis par une quantité (La quantité est un terme générique de la métrologie (compte, montant) ; un scalaire, vecteur, nombre d’objets ou d’une autre manière de dénommer la valeur d’une collection ou un groupe de choses.) finie d'information). Il s'agit de savoir si oui ou non un ordinateur (Un ordinateur est une machine dotée d'une unité de traitement lui permettant d'exécuter des programmes enregistrés. C'est un ensemble de circuits électroniques permettant de manipuler des...) s'arrêtera lorqu'il exécute un programme à partir de l'état initial de la mémoire. L'indécidabilité du problème de l'arrêt a été prouvée par Alan Turing.
  • Plus généralement le théorème de Rice (En théorie de la calculabilité, le théorème de Rice dit que toute propriété non triviale (c.-à-d. qui n'est pas toujours vraie ou toujours fausse) sur la...) énonce que toute question sur les programmes informatiques qui ne dépend que du résultat du calcul (terminer ou non, valeur calculée etc.) est indécidable ou triviale (ici, " trivial " s'entend par : la réponse est toujours oui ou toujours non).
  • La question de savoir si oui ou non un énoncé de la logique du premier ordre est universellement valide (démontrable dans toute théorie), dépend de la signature du langage choisie (les symboles d'opération ou de relation ...). Ce problème, parfois appelé problème de la décision (En logique mathématique, on appelle problème de la décision le fait de déterminer de façon mécanique, par un algorithme, si un énoncé est un théorème de la logique égalitaire du premier ordre, c’est-à-dire s'il se dérive...), est indécidable pour le langage de l'arithmétique, et plus généralement pour n'importe quel langage égalitaire du premier ordre qui contient au moins un symbole de relation binaire (Une relation binaire est un concept mathématique qui systématise des notions comme « ... est supérieur ou égal à ... » en arithmétique, ou « ... est élément de l’ensemble...) (comme < ou ∈). Pour un langage égalitaire du premier ordre ne contenant que des symboles de prédicat unaires (calcul des prédicats égalitaire monadique), il est décidable.
  • La question de savoir si oui ou non une proposition énoncée dans le langage de l'arithmétique (il faut les deux opérations, + et ×) est vraie dans le modèle standard de l'arithmétique est indécidable (c'est une conséquence du premier théorème d'incomplétude de Gödel, ou du théorème de Tarski).
  • La prouvabilité d'un énoncé à partir des axiomes de l'arithmétique de Peano est indécidable (voir problème de la décision). Gödel a montré que cet ensemble est strictement inclus dans le précédent. Comme l'axiomatique de Peano a une infinité d'axiomes, cela ne se déduit pas directement de l'indécidabilité du problème de la décision dans le langage, énoncée précédemment. Les deux résultats se déduisent d'un résultat général pour les théories arithmétiques qui satisfont certaines conditions. L'arithmétique de Peano vérifie ces conditions, mais aussi l'arithmétique Q de Robinson, qui a un nombre fini d'axiomes.
  • La prouvabilité d'un énoncé à partir des axiomes d'une théorie des ensembles (La théorie des ensembles est une branche des mathématiques créée initialement par le mathématicien allemand Georg Cantor à la fin du XIXe siècle.) cohérente, et plus généralement de toute théorie cohérente qui permet d'exprimer " suffisamment " d'arithmétique formelle est indécidable (voir problème de la décision).
  • La question de savoir si oui ou non une équation (En mathématiques, une équation est une égalité qui lie différentes quantités, généralement pour poser le problème de leur identité. Résoudre l'équation consiste à déterminer toutes les façons de donner à certaines des quantités qui y...) diophantienne a une solution. La preuve de son indécidabilité est le théorème de Matiyasevich (1970)
  • La question de savoir si oui ou non deux termes du lambda-calcul (Le lambda-calcul (ou λ-calcul) est un langage de programmation théorique inventé par Alonzo Church dans les années 1930. Ce langage a été le premier utilisé pour définir et caractériser les fonctions récursives et...) sont β-équivalents, ou de façon similaire, l'identité de deux termes de la logique combinatoire (En mathématiques, la combinatoire, appelée aussi analyse combinatoire, étudie les configurations de collections finies d'objets ou les combinaisons d'ensembles finis, et les dénombrements.). Son indécidabilité a été prouvée par Alonzo Church (Alonzo Church 14 juin 1903 - 11 août 1995 fut un mathématicien (logicien) américain à qui l'on doit certains des fondements de l'informatique théorique.).

Logiques décidables

Une logique est décidable s'il existe un algorithme qui réponde toujours par oui ou non à la question de savoir si un énoncé donné est démontrable dans cette logique. Un tel algorithme peut être facilement étendu en un algorithme de recherche (En informatique, un algorithme de recherche est un type d'algorithme qui, pour un domaine, un problème de ce domaine et des critères donnés, retourne en résultat un ensemble de solutions répondant au...) de démonstration (En mathématiques, une démonstration permet d'établir une proposition à partir de propositions initiales, ou précédemment démontrées à partir de propositions...) formelle : une fois que l'on sait qu'un énoncé est démontrable, il suffit d'énumérer toutes les démonstrations bien formées jusqu'à trouver une démonstration de cet énoncé. Cet algorithme de recherche (La recherche scientifique désigne en premier lieu l’ensemble des actions entreprises en vue de produire et de développer les connaissances scientifiques....) n'a bien sûr qu'un intérêt théorique, sauf dans des cas particulièrement simples.

Même si une logique est décidable, la complexité (La complexité est une notion utilisée en philosophie, épistémologie (par exemple par Anthony Wilden ou Edgar Morin), en physique, en...) algorithmique de sa décision peut être rédhibitoire.

Exemples de logiques décidables :

  • la théorie des corps réels clos, avec des algorithmes basés sur l'élimination des quantificateurs, qui produisent au vu d'un énoncé un énoncé équivalent sans quantificateurs ∀ou ∃ ; les énoncés sans quantificateurs de la théorie sont trivialement décidables ; la complexité des algorithmes connus est élevée et ne permet que la décision d'énoncés très simples ;
  • l'arithmétique de Presburger (arithmétique entière sans multiplication, ou, ce qui revient au même, avec multiplication restreinte au cas où l'un des opérandes est une constante)[1].

Décidabilité logique et décidabilité algorithmique

Les deux notions de décidabilité interprètent chacune la notion intuitive de décision dans des sens clairement différents. Elles sont cependant liées. En effet, on considère en mathématiques qu'une démonstration, si elle peut être difficile à trouver, doit être " facile " à vérifier, en un sens très informel (et discutable — mais ce n'est pas l'objet de cet article). Quand on formalise, on traduit ceci en demandant que le problème de reconnaître si un assemblage de phrases est une démonstration formelle, est décidable. Pour que ceci soit exact, il faut supposer que l'ensemble des axiomes de la théorie est décidable, ce qui, on l'a déjà mentionné, est très naturel.

Sous cette hypothèse, l'ensemble des théorèmes d'une théorie devient récursivement énumérable ; une telle théorie, si elle est complète, est alors décidable (voir article théorie axiomatique pour des justifications et détails supplémentaires). Par contre une théorie décidable, n'est pas forcément complète. Ainsi la théorie des corps algébriquement clos n'est pas complète, puisque la caractéristique n'est pas précisée[2], elle est pourtant décidable. La théorie des corps algébriquement clos d'une caractéristique donnée (Dans les technologies de l'information, une donnée est une description élémentaire, souvent codée, d'une chose, d'une transaction, d'un événement, etc.) est elle complète et décidable.

Notes

  1. Rabin et Fischer ont démontré en 1974 que n'importe quel algorithme de décision pour l'arithmétique de Presburger possède un pire cas avec un temps d'exécution supérieur à 2^{2^{cn}}, pour une constante c>0.
  2. Il s'agit de logique du premier ordre. Pour chaque entier premier p, le fait qu'un corps a pour caractéristique p s'énonce au premier ordre par un seul axiome. Pour la caractéristique 0, il faut une infinité d'axiomes.
Source: Wikipédia publiée sous licence CC-BY-SA 3.0.

Vous pouvez soumettre une modification à cette définition sur cette page. La liste des auteurs de cet article est disponible ici.