Une fonction calculable est une opération pour laquelle il existe une méthode mécanique, une suite d’instructions précises et sans ambiguïté, permettant d’obtenir le résultat à partir des données de départ en un nombre fini d’étapes. L’idée intuitive est celle d’une recette que n’importe qui, ou n’importe quelle machine, pourrait suivre à l’aveugle sans avoir besoin de comprendre ni d’inventer quoi que ce soit. Additionner deux nombres, trier une liste par ordre alphabétique ou vérifier si un mot figure dans un dictionnaire sont des exemples de fonctions calculables, parce qu’on peut décrire exactement les gestes à accomplir pour arriver au but. À l’inverse, certaines questions n’admettent aucune procédure de ce genre, et l’un des grands résultats de la logique du vingtième siècle a précisément été de montrer que des fonctions parfaitement bien définies peuvent malgré tout ne pas être calculables.
La notion est née dans les années 1930, avant même l’existence des ordinateurs, d’un débat entre mathématiciens et logiciens qui cherchaient à définir rigoureusement ce que signifie calculer. Plusieurs réponses ont surgi presque en même temps: Alan Turing en Angleterre avec sa machine théorique, Alonzo Church aux États-Unis avec un système de règles appelé lambda-calcul, et Kurt Gödel avec les fonctions dites récursives. Le fait remarquable est que ces approches très différentes se sont révélées équivalentes, désignant toutes exactement le même ensemble de fonctions. Cette convergence a donné naissance à ce qu’on appelle la thèse de Church-Turing, l’idée que toutes ces définitions capturent bien la notion intuitive de calcul.
L’intérêt de ce concept dépasse largement la théorie. En délimitant ce qui est calculable et ce qui ne l’est pas, il fixe les limites absolues de ce qu’un ordinateur peut faire, quelle que soit sa puissance. La machine de Turing imaginée pour ces recherches a servi de modèle abstrait à tous les ordinateurs qui ont suivi. Aujourd’hui, savoir qu’un problème n’est pas calculable évite de perdre du temps à chercher un programme qui ne peut pas exister, tandis que reconnaître qu’une tâche est calculable indique qu’on peut au moins en principe l’automatiser, même si cela reste parfois très lent en pratique.
Laisser un commentaire