ALGORITHME

Algorithmes et théorie de la calculabilité : à l’ombre d’Alan Turing

Au début du xx^e siècle, on retrouve l’idée qu’un calcul s’effectue au moyen de manipulations séquentielles de type symbolique dans l’analyse de la notion de calculabilité que propose le mathématicien et logicien britannique Alan Turing (1912–1954). Ce dernier prend comme point de départ de son analyse ce que fait un agent humain lorsqu’il est en train d’effectuer un calcul, et il écrit dans un article en 1936 : « En général, on effectue un calcul en inscrivant certains symboles sur une feuille, que l’on peut supposer divisée en cases comme un cahier d’écolier. » Cette analyse mène Turing à modéliser le calcul au moyen de machines « idéalisées », ce qu’on appelle aujourd’hui les machines de Turing. Elles sont constituées par un ruban infini et divisé en cases, ainsi que par une tête de lecture/écriture qui opère sur une case, en lisant, écrivant ou effaçant un symbole à la fois, le nombre de symboles disponibles étant fini (par exemple, 0 et 1, ce qui permet une représentation positionnelle des entiers en base 2). Elle peut aussi se déplacer à gauche ou à droite d’une case à la fois. Cependant, Turing n’emploie jamais le mot « algorithme ». Il dit plutôt que ses machines permettent de formaliser la notion intuitive de « calculabilité effective » et, plus précisément, ce qu’on appelle les « fonctions effectivement calculables », autrement dit les fonctions (des entiers vers les entiers) dont les valeurs peuvent être calculées sans recourir à aucune forme d’ingéniosité. Il suffit en effet de suivre une méthode dont chaque étape est prédéterminée et définie à partir d’opérations « suffisamment élémentaires pour pouvoir être accomplies de manière exacte et en un temps fini », comme l'affirme l’informaticien américain Donald Knuth (né en 1938), figure majeure de l’algorithmique au xx^e siècle, dans l’édition de 1997 de son livre The Art of Computer Programming. 

En 1937, Alonzo Church (1903–1995), mathématicien et logicien américain qui avait encadré le travail de doctorat de Turing, parle en revanche, au sujet de l’article de celui-ci de 1936, de fonction effectivement calculable lorsqu’« il existe un algorithme pour le calcul de ses valeurs », et considère que les machines de Turing ont l’« avantage de rendre immédiatement évidente l’identification avec l’effectivité au sens ordinaire (non explicitement défini) ». C’est pourquoi plusieurs auteurs ont pensé que l’analyse de Turing pouvait être utilisée pour caractériser de manière formelle la notion d’algorithme. Par exemple, dans un livre sur l’histoire des algorithmes dirigé par Jean-Luc Chabert (1^re éd. 1994), on lit : « La machine de Turing se présente donc comme une formalisation de l’idée intuitive que nous nous faisons d’un algorithme de calcul. » Deux types d’arguments semblent toutefois pouvoir contredire ou du moins nuancer cette conclusion.

Premièrement, il existe des machines de Turing qui, pour certaines entrées (inputs), ne s’arrêtent jamais, au sens où elles continuent à calculer à l’infini, sans qu’aucune sortie (output) puisse être atteinte en un nombre fini d’étapes de calcul. Il s’agit de machines calculant des fonctions partielles, dans lesquelles certaines entrées ne sont associées à aucune sortie (comme la fonction qui associe à un entier x l’entier n tel que n² = x, lorsque celui-ci existe ; par exemple, quand x = 3, il n’existe pas un tel entier n et la fonction n’a donc pas de sortie). Or la notion d’algorithme est souvent associée au respect d’une condition de « terminaison ». Une telle condition, formulée sous le nom de « finitude » est explicitement imposée par Knuth, dans l’ouvrage mentionné précédemment : « Un algorithme doit toujours se terminer après un nombre fini d’étapes. » L’idée est ici qu’un algorithme est une procédure mise en place pour résoudre un problème et atteindre ainsi une connaissance. Mais si cette procédure ne s’arrête pas, on n’obtiendra pas de réponse et on ne saura donc pas quelle est la solution au problème posé. Knuth lie donc fermement la notion d’algorithme à celle de terminaison, et affirme qu’une « procédure qui possède toutes les caractéristiques d’un algorithme, sauf celle, éventuellement, de la finitude, peut être appelée méthode de calcul ». Selon lui, algorithmes et méthodes de calcul doivent donc être distingués, et les machines de Turing semblent correspondre seulement à des méthodes de calcul.

Deuxièmement, même en adoptant une définition moins restrictive que celle de Knuth et en acceptant qu’un algorithme puisse correspondre à une procédure non terminante, un deuxième problème subsiste : les machines de Turing ne constituent pas un cadre suffisamment général pour capturer formellement tous les algorithmes possibles. D’autres cadres – ou mieux, d’autres modèles – permettent de formaliser la notion de fonction effectivement calculable. Le calcul, la théorie des fonctions récursives, les systèmes de Post…, chacun de ces modèles est caractérisé par ses propres symboles, sa propre syntaxe et ses propres opérations de manipulation de symboles, qu’on appelle opérations primitives. Or, en dépit de ces différences, il est possible de prouver que toute fonction (considérée comme ensemble de couples d’entrées-sorties) calculable par une machine de Turing est aussi calculable à l’intérieur de l’un de ces modèles et inversement. Toutefois, la manière d’effectuer le calcul – c’est-à-dire, la procédure de calcul – peut s’avérer différente. Par exemple, pour calculer le successeur d’un entier naturel avec une machine de Turing, il est nécessaire d’employer une suite de plusieurs opérations primitives. En revanche, dans le cadre des fonctions récursives (qui peuvent être itérées un nombre arbitraire de fois), la fonction successeur correspond à une opération primitive, évitant de faire appel à d’autres opérations pour la calculer. Au contraire, c’est cette opération qui permet de représenter les entiers en partant du seul chiffre 0 par n applications de la fonction successeur S, à savoir S(0), S(S(0)), S(S(S(0))), etc. Cet exemple suggère qu’une même fonction peut être calculée par deux algorithmes différents. Montrer qu’une fonction est calculable par une machine de Turing implique alors d’exhiber un algorithme spécifique pour la calculer. Mais si l’on essaie de traduire cet algorithme dans un autre modèle de calcul, le fait de changer d’opérations primitives et de symboles peut amener à définir un autre algorithme. Chaque modèle de calcul permettrait donc de définir certains algorithmes, mais il manquerait un cadre général permettant d’offrir un point de vue unifié sur les différents modèles de calcul.