Magazine Culture

Indécidable

Publié le 07 septembre 2013 par Etrecourt

Adjectif qui vient de l’anglais undecidable.

Se dit lorsque l’on est en présence d’un énoncé par exemple mathématique qui ne peut être ni démontré ni réfuté.
En d’autres termes ce qui est indécidable est l’impossibilité absolue et définitivement démontrée de résoudre par un procédé général de calcul un problème donné.

Ainsi de ce problème de géométrie élémentaire
Soient une liste de formes polygonales; peut-on paver un plan sans recouvrement, ni espace vide avec des exemplaires de chaque forme polygonale?
Résolution: On n’a pas de formule qui permette par un calcul fini et à partir des données(les formes polygonales)d’établir si oui ou non il est possible de paver le plan avec des exemplaires des formes
géométriques considérées. En conséquence le problème est indécidable.

Source:Calculabilité et décidabilité J. P. Delahaye Université Sciences et Technologies de Lille.
Laboratoire d’Informatique Fondamentale de Lille.


Retour à La Une de Logo Paperblog

Magazine