calculabilité et décidabilité - informatique.

calculabilité et décidabilité - informatique. 1 PRÉSENTATION calculabilité et décidabilité, propriétés assignées à des fonctions, en vue de savoir si elles pourront être implémentées dans un programme. 2 THÈSE DE LA CALCULABILITÉ DE CHURCH-TURING Prenons une classe de fonctions mathématiques ou logiques dont chacune appelle une réponse par oui ou par non. On se pose alors la question de savoir s'il existe une procédure permettant de résoudre n'importe laquelle des questions de cette classe en un nombre fini d'étapes, c'est-à-dire de savoir si ces fonctions sont calculables ou non. La thèse de Church-Turing (Alonzo Church en 1936, Alan Turing en 1937) fait l'hypothèse que les fonctions « mécaniquement calculables « (ou calculables au sens intuitif, autrement dit par une suite d'opérations de base, telles que l'addition ou la multiplication) sont calculables par des machines de Turing, que l'on considère ici comme des équivalents abstraits et idéalisés des ordinateurs. Cette thèse est le fondement de l'informatique classique. En effet, l'étude et le développement de programmes informatiques n'a de sens qu'à partir du moment où l'on dispose d'un concept précis de machine permettant tous les calculs a priori possibles. La conception d'un ordinateur classique est très éloignée de la notion de machine de Turing, mais on peut montrer que les deux modèles sont équivalents. 3 PROBLÈME DE LA DÉCIDABILITÉ DE HILBERT Reste un problème crucial : existe-t-il des questions (pourtant bien posées) qui ne sont pas solubles algorithmiquement, autrement dit des problèmes qu'il est inutile de chercher à résoudre puisque nous savons que leur solution ne peut pas exister ? Ce problème est fondamental car il marque les limites de l'informatique : c'est le problème de la décidabilité, ou problème de la décision (Entscheidungsproblem), posé par le mathématicien allemand David Hilbert en 1900. Ce problème a reçu une réponse définitive en 1936 : oui. Cette réponse se base sur une démonstration prouvant qu'on ne peut pas concevoir un algorithme qui calcule, si une machine de Turing (ou un ordinateur, par analogie) peut s'arrêter sur une donnée, ou tourner en rond indéfiniment : ce problème n'est pas décidable. On peut noter qu'il existe des problèmes dits semi-décidables, pour lesquels un algorithme calculera la réponse si cette réponse est « vrai «, mais ne s'arrêtera pas si la réponse est « faux «. Microsoft ® Encarta ® 2009. © 1993-2008 Microsoft Corporation. Tous droits réservés.