Problème indécidable - Undecidable problem
Dans la théorie de la calculabilité et la théorie de la complexité computationnelle , un problème indécidable est un problème de décision pour lequel il s'avère impossible de construire un algorithme qui conduit toujours à une réponse correcte par oui ou par non. Le problème d'arrêt est un exemple : il peut être prouvé qu'il n'y a pas d'algorithme qui détermine correctement si des programmes arbitraires finissent par s'arrêter lorsqu'ils sont exécutés.
Fond
Un problème de décision est une question arbitraire par oui ou par non sur un ensemble infini d'entrées. De ce fait, il est traditionnel de définir le problème de décision de manière équivalente comme l'ensemble des entrées pour lesquelles le problème renvoie yes . Ces entrées peuvent être des nombres naturels, mais aussi d'autres valeurs d'un autre type, telles que des chaînes d'un langage formel . En utilisant un certain codage, tel qu'une numérotation de Gödel , les chaînes peuvent être codées sous forme de nombres naturels. Ainsi, un problème de décision formulé de manière informelle en termes de langage formel est également équivalent à un ensemble de nombres naturels . Pour garder la définition formelle simple, elle est formulée en termes de sous-ensembles des nombres naturels.
Formellement, un problème de décision est un sous-ensemble des nombres naturels. Le problème informel correspondant est celui de décider si un nombre donné est dans l'ensemble. Un problème de décision A est dit décidable ou effectivement soluble si A est un ensemble récursif et indécidable sinon. Un problème est appelé partiellement décidable, semi-décidable, résoluble ou prouvable si A est un ensemble récursivement énumérable .
Exemple : le problème de l'arrêt en théorie de la calculabilité
En théorie de la calculabilité , le problème d'arrêt est un problème de décision qui peut être énoncé comme suit :
- Compte tenu de la description d'un programme arbitraire et d'une entrée finie, décidez si le programme se termine ou s'exécutera indéfiniment.
Alan Turing a prouvé en 1936 qu'un algorithme général fonctionnant sur une machine de Turing qui résout le problème d'arrêt pour toutes les paires possibles d'entrées programme ne peut pas nécessairement exister. Par conséquent, le problème de l'arrêt est indécidable pour les machines de Turing.
Relation avec le théorème d'incomplétude de Gödel
Les concepts soulevés par les théorèmes d'incomplétude de Gödel sont très similaires à ceux soulevés par le problème de l'arrêt, et les preuves sont assez similaires. En fait, une forme plus faible du premier théorème d'incomplétude est une conséquence facile de l'indécidabilité du problème d'arrêt. Cette forme plus faible diffère de l'énoncé standard du théorème d'incomplétude en affirmant qu'une axiomatisation des nombres naturels qui est à la fois complète et saine est impossible. La partie "sonore" est l'affaiblissement : cela signifie que nous exigeons que le système axiomatique en question ne prouve que des déclarations vraies sur les nombres naturels. Puisque la solidité implique la cohérence , cette forme plus faible peut être considérée comme un corollaire de la forme forte. Il est important d'observer que l'énoncé de la forme standard du premier théorème d'incomplétude de Gödel est complètement indifférent à la valeur de vérité d'un énoncé, mais concerne uniquement la question de savoir s'il est possible de le trouver à travers une preuve mathématique .
La forme la plus faible du théorème peut être prouvée à partir de l'indécidabilité du problème d'arrêt comme suit. Supposons que nous ayons une axiomatisation solide (et donc cohérente) et complète de toutes les vraies déclarations logiques du premier ordre sur les nombres naturels . Ensuite, nous pouvons construire un algorithme qui énumère toutes ces déclarations. Cela signifie qu'il existe un algorithme N ( n ) qui, étant donné un nombre naturel n , calcule un véritable énoncé logique du premier ordre sur les nombres naturels, et que pour tous les énoncés vrais, il existe au moins un n tel que N ( n ) donne cette déclaration. Supposons maintenant que nous voulions décider si l'algorithme avec la représentation a s'arrête sur l'entrée i . Nous savons que cet énoncé peut être exprimé avec un énoncé logique du premier ordre, disons H ( a , i ). Puisque l'axiomatisation est complète, il s'ensuit que soit il existe un n tel que N ( n ) = H ( a , i ) soit il existe un n' tel que N ( n' ) = H ( a , i ). Donc, si nous parcourons tout n jusqu'à ce que nous trouvions H ( a , i ) ou sa négation, nous nous arrêterons toujours, et de plus, la réponse qu'il nous donnera sera vraie (par justesse). Cela signifie que cela nous donne un algorithme pour décider du problème d'arrêt. Puisque nous savons qu'il ne peut y avoir un tel algorithme, il s'ensuit que l'hypothèse selon laquelle il existe une axiomatisation cohérente et complète de toutes les vraies déclarations logiques du premier ordre sur les nombres naturels doit être fausse.
Exemples de problèmes indécidables
Les problèmes indécidables peuvent être liés à différents sujets, tels que la logique , les machines abstraites ou la topologie . Comme il existe un nombre incalculable de problèmes indécidables, toute liste, même de longueur infinie , est nécessairement incomplète.
Exemples d'énoncés indécidables
Il y a deux sens distincts du mot « indécidable » dans l'usage contemporain. Le premier d'entre eux est le sens utilisé par rapport aux théorèmes de Gödel, celui d'un énoncé n'étant ni prouvable ni réfutable dans un système déductif spécifié . Le deuxième sens est utilisé en relation avec la théorie de la calculabilité et s'applique non pas aux énoncés mais aux problèmes de décision , qui sont des ensembles infiniment dénombrables de questions nécessitant chacune une réponse par oui ou par non. Un tel problème est dit indécidable s'il n'y a pas de fonction calculable qui réponde correctement à chaque question de l'ensemble de problèmes. Le lien entre les deux est que si un problème de décision est indécidable (au sens théorique de la récursivité), alors il n'y a pas de système formel cohérent et efficace qui prouve pour chaque question A du problème soit « la réponse à A est oui » ou « la la réponse à A est non".
En raison des deux sens du mot indécidable, le terme indépendant est parfois utilisé au lieu d'indécidable pour le sens « ni prouvable ni réfutable ». Cependant, l'utilisation de « indépendant » est également ambiguë. Cela peut signifier simplement « non prouvable », laissant ouvert la question de savoir si une déclaration indépendante pourrait être réfutée.
L'indécidabilité d'un énoncé dans un système déductif particulier ne répond pas, en soi, à la question de savoir si la valeur de vérité de l'énoncé est bien définie ou si elle peut être déterminée par d'autres moyens. L'indécidabilité implique seulement que le système déductif particulier considéré ne prouve pas la vérité ou la fausseté de l'énoncé. L'existence d'énoncés dits "absolument indécidables", dont la valeur de vérité ne peut jamais être connue ou est mal spécifiée, est un point controversé parmi diverses écoles philosophiques .
L' un des premiers problèmes suspectés d'être indécidable, dans le second sens du terme, est le problème de mot pour les groupes , d' abord posé par Max Dehn en 1911, qui demande s'il y a un finiment présenté groupe pour lequel aucun algorithme existe pour déterminer si deux mots sont équivalents. Ce fut le cas en 1952.
Les travaux combinés de Gödel et Paul Cohen ont donné deux exemples concrets d'énoncés indécidables (au premier sens du terme) : L' hypothèse du continu ne peut être ni prouvée ni réfutée dans ZFC (l'axiomatisation standard de la théorie des ensembles ), et l' axiome de le choix ne peut être ni prouvé ni réfuté dans ZF (qui est tous les axiomes ZFC sauf l'axiome du choix). Ces résultats ne nécessitent pas le théorème d'incomplétude. Gödel a prouvé en 1940 qu'aucune de ces affirmations ne pouvait être réfutée dans la théorie des ensembles ZF ou ZFC. Dans les années 1960, Cohen a prouvé que ni l'un ni l'autre n'est prouvable à partir de ZF, et l'hypothèse du continu ne peut pas être prouvée à partir de ZFC.
En 1970, le mathématicien russe Yuri Matiyasevich montra que le dixième problème de Hilbert , posé en 1900 comme un défi au prochain siècle de mathématiciens, ne peut être résolu. Le défi de Hilbert recherchait un algorithme qui trouve toutes les solutions d'une équation diophantienne . Une équation diophantienne est un cas plus général du dernier théorème de Fermat ; on cherche les racines entières d'un polynôme dans un nombre quelconque de variables à coefficients entiers. Comme nous n'avons qu'une équation mais n variables, une infinité de solutions existent (et sont faciles à trouver) dans le plan complexe ; cependant, le problème devient impossible si les solutions sont limitées à des valeurs entières uniquement. Matiyasevich a montré que ce problème était insoluble en mappant une équation diophantienne à un ensemble récursivement énumérable et en invoquant le théorème d'incomplétude de Gödel.
En 1936, Alan Turing a prouvé que le problème de l' arrêt — la question de savoir si une machine de Turing s'arrête ou non sur un programme donné — est indécidable, au second sens du terme. Ce résultat a ensuite été généralisé par le théorème de Rice .
En 1973, Saharon Shelah montrait que le problème de Whitehead en théorie des groupes est indécidable, au premier sens du terme, en théorie des ensembles standard.
En 1977, Paris et Harrington ont prouvé que le principe de Paris-Harrington , une version du théorème de Ramsey , est indécidable dans l'axiomatisation de l'arithmétique donnée par les axiomes de Peano mais peut être prouvé être vrai dans le système plus large de l' arithmétique du second ordre .
Le théorème de l'arbre de Kruskal , qui a des applications en informatique, est également indécidable à partir des axiomes de Peano mais prouvable en théorie des ensembles. En fait le théorème de l'arbre de Kruskal (ou sa forme finie) est indécidable dans un système beaucoup plus fort codifiant les principes acceptables sur la base d'une philosophie des mathématiques appelée prédicativisme.
Le théorème de Goodstein est un énoncé sur la théorie de Ramsey des nombres naturels que Kirby et Paris ont montré qu'ils sont indécidables en arithmétique de Peano.
Gregory Chaitin a produit des déclarations indécidables dans la théorie algorithmique de l'information et a prouvé un autre théorème d'incomplétude dans ce contexte. Le théorème de Chaitin stipule que pour toute théorie qui peut représenter suffisamment d'arithmétique, il existe une limite supérieure c telle qu'aucun nombre spécifique ne peut être prouvé dans cette théorie pour avoir une complexité de Kolmogorov supérieure à c . Alors que le théorème de Gödel est lié au paradoxe du menteur , le résultat de Chaitin est lié au paradoxe de Berry .
En 2007, les chercheurs Kurtz et Simon, s'appuyant sur des travaux antérieurs de JH Conway dans les années 1970, ont prouvé qu'une généralisation naturelle du problème de Collatz est indécidable.