Que montre le théorème d’incomplétude de Godel ?
Le premier théorème d’incomplétude montre que, dans les systèmes formels qui peuvent exprimer l’arithmétique de base, une liste finie complète et cohérente d’axiomes ne peut jamais être créée : chaque fois qu’une déclaration supplémentaire cohérente est ajoutée comme axiome, il y a d’autres déclarations vraies qui ne peuvent toujours pas être créées. être prouvé, même avec le nouvel axiome …
Comment résoudre un problème indécidable ?
Dans la théorie de la calculabilité , un problème indécidable est un type de problème de calcul qui nécessite une réponse oui / non, mais où il ne peut y avoir aucun programme informatique qui donne toujours la bonne réponse; c’est-à-dire que tout programme possible donnait parfois la mauvaise réponse ou s’exécutait indéfiniment sans donner de réponse.
Y a-t-il des problèmes qui ne peuvent pas être résolus de manière algorithmique ?
Il n’y a pas d’ algorithme qui puisse résoudre ce problème pour chaque paire programme-entrée possible (au moins pour les machines de Turing). C’est ce qu’on appelle le problème d’arrêt , et c’est un exemple courant de problème indécidable en informatique.
Quels problèmes sont décidables ?
Définition : Un problème de décision qui peut être résolu par un algorithme qui s’arrête sur toutes les entrées en un nombre fini d’étapes. Le langage associé est appelé langage décidable . Également connu sous le nom de problème totalement décidable , résoluble de manière algorithmique, résoluble de manière récursive.
Chaque problème NP complet est-il indécidable ?
Notez que chaque problème NP est décidable . C’est une notion clé. Rappelez-vous que les problèmes P correspondent également à la définition de NP , donc…. Certains problèmes NP – difficiles existent également dans NP .
Le TSP est-il indécidable ?
Une solution est trop longue et ne peut pas être décrite avec une expression polynomiale sur la longueur de l’entrée. Par exemple, dans une instance TSP , demander toutes les tournées qui ont une longueur L ou moins. Un problème de calcul est considéré comme indécidable si aucun algorithme ne peut être donné pour le résoudre.
Le TSP est-il traitable ?
Comme les seules solutions au TSP sont insolubles , le TSP est connu comme un problème insoluble . Il n’a pas été prouvé qu’il n’existe pas de solution traitable au TSP , bien que de nombreux informaticiens parmi les meilleurs au monde aient travaillé sur ce problème au cours des 40 dernières années, essayant de trouver une solution mais sans succès.