"En 1936, dont l'article ""Sur les nombres calculables, avec une application au problème d'Entscheidungs"" a prouvé qu'une machine pouvait effectuer n'importe quel calcul mathématique imaginable si elle pouvait être représentée comme un algorithme ?
Alan Turing
En 1936, Alonzo Church et Alan Turing ont publié des articles indépendants montrant qu'une solution générale au problème de l'Entscheidungs ​​est impossible, en supposant que la notion intuitive de « effectivement calculable » est capturée par les fonctions calculables par une machine de Turing (ou de manière équivalente, par celles exprimables dans le calcul lambda). Cette hypothèse est maintenant connue sous le nom de thèse Church-Turing. Avant de pouvoir répondre à cette question, il fallait définir formellement la notion d'« algorithme ». Cela a été fait par Alonzo Church en 1936 avec le concept de « calculabilité efficace » basé sur son calcul λ et par Alan Turing la même année avec son concept de machines de Turing. Turing a immédiatement reconnu qu'il s'agissait de modèles de calcul équivalents. La réponse négative à la question ' a ensuite été donnée par Alonzo Church en 1935-1936 et indépendamment peu de temps après par Alan Turing en 1936. Church a prouvé qu'il n'existe pas de fonction calculable qui décide pour deux expressions de λ-calcul données si elles sont équivalentes ou non. Il s'est fortement appuyé sur les travaux antérieurs de Stephen Kleene. Turing a réduit le problème d'arrêt des machines de Turing au . Le travail des deux auteurs a été fortement influencé par les travaux antérieurs de Kurt Gödel sur son théorème d'incomplétude, notamment par la méthode d'attribution de nombres (une numérotation de Gödel) aux formules logiques afin de réduire la logique à l'arithmétique.
En mathématiques et en informatique, le ' (, allemand pour « problème de décision ») est un défi posé par David Hilbert en 1928. Le demande un algorithme qui prend en entrée un énoncé d'une logique du premier ordre (éventuellement avec un nombre fini d'axiomes au-delà des axiomes habituels de la logique du premier ordre) et répond « Oui » ou « Non » selon que l'énoncé est universellement valable, c'est-à-dire valable dans toute structure satisfaisant les axiomes. Selon le théorème de complétude de la logique du premier ordre, une affirmation est universellement valide si et seulement si elle peut être déduite des axiomes, de sorte que cela peut également être considéré comme demandant à un algorithme de décider si une affirmation donnée est prouvable à partir des axiomes en utilisant les règles de la logique.

En 1936, Alonzo Church et Alan Turing ont publié des articles indépendants montrant qu'une solution générale au problème de l'Entscheidungs ​​est impossible, en supposant que la notion intuitive de « effectivement calculable » est capturée par les fonctions calculables par une machine de Turing (ou de manière équivalente, par celles exprimables dans le calcul lambda). Cette hypothèse est maintenant connue sous le nom de thèse Church-Turing.

Histoire du problème

L'origine du concept remonte à Gottfried Leibniz qui, au XVIIe siècle, après avoir construit avec succès une machine à calculer mécanique, rêvait de construire une machine capable de manipuler des symboles afin de déterminer les valeurs de vérité des énoncés mathématiques. Il s'est rendu compte que la première étape devrait être un langage formel clair, et une grande partie de son travail ultérieur a été orienté vers cet objectif. En 1928, David Hilbert et Wilhelm Ackermann posèrent la question sous la forme décrite ci-dessus.

Dans la continuité de son « programme », Hilbert posa trois questions lors d'une conférence internationale en 1928, dont la troisième fut connue sous le nom de « celle de Hilbert ». Jusqu’en 1930, il pensait qu’il n’y aurait pas de problème insoluble.

Réponse négative

Avant de pouvoir répondre à cette question, il fallait définir formellement la notion d'« algorithme ». Cela a été fait par Alonzo Church en 1936 avec le concept de « calculabilité efficace » basé sur son calcul λ et par Alan Turing la même année avec son concept de machines de Turing. Turing a immédiatement reconnu qu'il s'agissait de modèles de calcul équivalents.

La réponse négative à la question ' a ensuite été donnée par Alonzo Church en 1935-1936 et indépendamment peu de temps après par Alan Turing en 1936. Church a prouvé qu'il n'existe pas de fonction calculable qui décide pour deux expressions de λ-calcul données si elles sont équivalentes ou non. Il s'est fortement appuyé sur les travaux antérieurs de Stephen Kleene. Turing a réduit le problème d'arrêt des machines de Turing au . Le travail des deux auteurs a été fortement influencé par les travaux antérieurs de Kurt Gödel sur son théorème d'incomplétude, notamment par la méthode d'attribution de nombres (une numérotation de Gödel) aux formules logiques afin de réduire la logique à l'arithmétique.

Ceci est lié au dixième problème de Hilbert, qui demande un algorithme pour décider si les équations diophantiennes ont une solution. L’inexistence d’un tel algorithme, établi par Yuri Matiyasevich en 1970, implique également une réponse négative au problème de l’Entscheidungs.

Certaines théories du premier ordre sont décidables algorithmiquement ; des exemples incluent l'arithmétique de Presburger, les champs fermés réels et les systèmes de types statiques de nombreux langages de programmation. La théorie générale du premier ordre des nombres naturels exprimée dans les axiomes de Peano ne peut cependant pas être décidée avec un tel algorithme.

Procédures de décision pratiques

Disposer de procédures de décision pratiques pour les classes de formules logiques présente un intérêt considérable pour la vérification de programmes et de circuits. Les formules logiques booléennes pures sont généralement décidées à l'aide de techniques de résolution SAT basées sur l'algorithme DPLL. Les formules conjonctives sur l'arithmétique linéaire réelle ou rationnelle peuvent être décidées à l'aide de l'algorithme du simplexe, les formules en arithmétique linéaire entière (arithmétique de Presburger) peuvent être décidées à l'aide de l'algorithme de Cooper ou du test Omega de William Pugh. Les formules avec négations, conjonctions et disjonctions combinent les difficultés des tests de satisfiabilité avec celles de la décision des conjonctions ; ils sont généralement décidés aujourd'hui à l'aide de techniques de résolution SMT, qui combinent la résolution SAT avec des procédures de décision pour les conjonctions et les techniques de propagation. L'arithmétique polynomiale réelle, également connue sous le nom de théorie des champs réels fermés, est décidable ; il s'agit du théorème de Tarski-Seidenberg, qui a été implémenté dans les ordinateurs en utilisant la décomposition algébrique cylindrique.