Problème de la décision

En logique mathématique, on nomme 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 dans un dispositif de déduction,...



Catégories :

Décision - Statistiques - Logique mathématique

Recherche sur Google Images :


Source image : chretiensenpolitique.eu
Cette image est un résultat de recherche de Google Image. Elle est peut-être réduite par rapport à l'originale et/ou protégée par des droits d'auteur.

Page(s) en rapport avec ce sujet :

  • Le cœur du problème de la décision est la recherche d'une méthode unique capable.... ordre et de vérifier un par un si l'équation (9) est vérifiée ou non.... (source : mathkang)


En logique mathématique, on nomme 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 dans un dispositif de déduction (voir système à la Hilbert, calcul des séquents, déduction naturelle), sans autres axiomes que ceux de l'égalité. De façon équivalente par le théorème de complétude, il s'agit de savoir si un énoncé est universellement valide, c'est-à-dire vrai dans l'ensemble des modèles (de l'égalité). Il s'agit de décidabilité algorithmique. Dit autrement, la question est celle de la décidabilité du calcul des prédicats égalitaire du premier ordre : la totalité des énoncés universellement valides du calcul des prédicats du premier ordre est-il décidable ?

Le problème de la décision dépend en fait du choix du langage du premier ordre : sa signature, les "briques" de base, qui permettent la construction des énoncés, symboles de constantes, de fonctions (ou opérations), et de prédicat (ou relation), par exemple, 0, +, ≤, ....

On parle aussi du problème de la décision dans une théorie axiomatique donnée, par exemple dans l'arithmétique de Peano. IL s'agit alors de déterminer si un énoncé est un théorème de la théorie en question. Dans un langage donné, une solution positive au problème de la décision apporte une solution positive aux problèmes de la décision pour l'ensemble des théories finiment axiomatisables de ce langage. En effet, un énoncé C se déduit d'un dispositif fini d'axiomes si et uniquement si on peut dériver en logique pure que la conjonction de ces axiomes entraîne C.

Le problème fut posé par David Hilbert et Wilhelm Ackermann en 1928. On utilise d'ailleurs quelquefois le terme allemand Entscheidungsproblem pour désigner le problème de la décision, c'est le cas fréquemment en anglais, pour éviter les confusions.

La question remonte à Gottfried Leibniz qui, au dix-septième siècle, imaginait la construction d'une machine qui pouvait manipuler des symboles pour déteminer les valeurs des énoncés mathématiques. Il comprit que le premier pas serait d'avoir un langage formel clair.

Alonzo Church et Alan Turing donnèrent (indépendamment) en 1936, une réponse négative au problème de la décision pour l'arithmétique (par exemple l'arithmétique de Peano ou une théorie cohérente plus forte). Ils utilisent beaucoup les méthodes développées par Kurt Gödel pour démontrer le premier théorème d'incomplétude. On peut énoncer ainsi le résultat :

Une théorie récursivement axiomatisable, cohérente et capable de "formaliser l'arithmétique", est algorithmiquement indécidable.

Les conditions précises du théorème sont celles du théorème de Gödel-Rosser. Si on examine ces conditions, on se rend compte qu'elles sont réalisées par une théorie finiment axiomatisable, et par conséquent on obtient une réponse négative au problème de la décision dans le langage de l'arithmétique (on peut prendre 0, 1, +, ×). Ce résultat est fréquemment nommé théorème de Church :

Le calcul des prédicats égalitaire du premier ordre dans le langage de l'arithmétique est algorithmiquement indécidable.

On en déduit par codage une réponse négative pour le problème de la décision dès que le langage contient un symbole de prédicat binaire (en plus de l'égalité). Par contre si le langage ne contient que des symboles de prédicats unaires et des symboles de constante (pas de symboles de fonction), alors le calcul des prédicats égalitaire du premier ordre correspondant, le calcul des prédicats monadiques du premier ordre, est décidable.

D'autre part, il existe des théories décidables dont le langage contient un symbole de prédicat binaire : la théorie des ordres denses (celle de Q la totalité des rationnels dans l'unique langage de l'ordre) pour prendre un exemple particulièrement simple, ou encore l'arithmétique de Presburger à laquelle on peut ajouter sans dommage la relation d'ordre, qui se définit avec l'addition.

Pour répondre à la question, en particulier pour y répondre négativement, il fallait cependant que la notion de fonction calculable, c'est-à-dire calculable mécaniquement, par un algorithme, soit formalisée. Cela s'est fait en plusieurs étapes. Plusieurs modèles de calcul, qu'on dirait désormais Turing-complets, sont apparus dans les années 1930. On peut citer les fonctions λ-calculables d'Alonzo Church (1930), les fonctions récursives générales de Herbrand et Gödel (Gödel 1934, en précisant une idée de Herbrand 1931), les machines de Turing (1936), les dispositifs de Post (1936), les fonctions récursives au sens de Kleene (1936)... Tous ces modèles se sont révélés équivalents, ce qui est un argument pour la thèse de Church (1936)  : on a bien capturé par l'un de ces modèles la notion de fonction calculable.

Pour montrer l'indécidabilité de l'arithmétique, l'argumentation d'Alan Turing est la suivante. Supposons que nous ayons un algorithme de décision pour l'arithmétique de Peano. La question de savoir si une machine de Turing donnée s'arrête ou non, peut être formulée comme un énoncé du premier ordre (on utilise les méthodes développées par Gödel), lequel serait alors résolu par l'algorithme de décision. Mais Turing avait prouvé auparavant qu'il n'y a pas d'algorithme général pour décider de l'arrêt d'une machine de Turing.

Voir aussi

References

Sources

En Français

fonctions récursives au sens de Kleene, Théorème de Church....

Théorème de Church, théories décidables et indécidables...

En Anglais

Articles originaux

Recherche sur Amazone (livres) :



Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/Probl%C3%A8me_de_la_d%C3%A9cision.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 07/04/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.
Accueil Recherche Aller au contenuDébut page
ContactContact ImprimerImprimer liens d'évitement et raccourcis clavierAccessibilité
Aller au menu