Instructions détaillées définissant un processus de calcul (qui est alors dit algorithmique), qui commence par une entrée arbitraire (parmi un certain nombre d’entrées possibles pour l’algorithme donné), et par des instructions visant à obtenir un résultat (ou sortie) qui est entièrement déterminé par l’entrée. Par exemple, les règles enseignées dans les écoles élémentaires pour l’addition, la soustraction, la multiplication et la division en colonnes sont des algorithmes ; dans ces algorithmes, les résultats possibles sont des entiers non négatifs écrits dans le système décimal, tandis que les entrées possibles sont des paires ordonnées de ces nombres. En général, on ne suppose pas que le résultat soit nécessairement obtenu : le processus d’application d’un algorithme à une entrée possible (c’est-à-dire un processus algorithmique qui se déroule à partir de cette entrée) peut également se terminer sans qu’un résultat soit obtenu (dans ce cas, on a un arrêt sans résultat) ou ne pas se terminer du tout. Si le processus se termine (ne se termine pas), alors on dit que l’entrée convient (ne convient pas) à l’algorithme en question.
Un résultat important dans ce domaine est l’indécidabilité du problème dit de halte. Il est possible de construire un algorithme $ \alpha $ tel qu’il n’existe pas d’algorithme pour décider si oui ou non une entrée arbitraire qui est possible pour $ \alpha $ est aussi convenable pour $ \alpha $. En particulier, on peut trouver un tel algorithme $ \alpha $ pour lequel l’ensemble de ses entrées possibles est l’ensemble des nombres naturels.
La notion d’algorithme est l’un des concepts centraux des mathématiques modernes, en particulier dans le domaine des calculs. Un exemple est donné ci-dessous. Trouver la solution numérique d’équations d’un type donné revient à construire un algorithme qui convertit une équation arbitraire de ce type et un nombre rationnel positif arbitraire $ \epsilon $en un nombre (ou un ensemble de nombres) qui diffère de la ou des racines de cette équation par moins de $ \epsilon $. Toutefois, l’expression « processus de calcul », utilisée dans le contexte d’un algorithme, ne doit pas être comprise comme signifiant uniquement des calculs numériques : même en algèbre élémentaire, des calculs avec des lettres sont utilisés. Les calculs arithmétiques standard font intervenir certains symboles qui ne sont pas des chiffres (parenthèses, signes d’égalité, symboles des opérateurs arithmétiques). Il est donc utile de considérer les algorithmes impliquant des symboles arbitraires et des objets composés de symboles. L’exemple le plus simple d’un tel objet est une séquence linéaire de symboles formant un mot. Il est également possible de considérer des objets « non linéaires » – matrices algébriques, arbres de dérivation de certains langages formels et graphes généraux. Intuitivement, la moindre exigence sur les entrées et les résultats des algorithmes est qu’ils doivent être des objets constructifs (cf. Objet constructif). Ainsi, le concept d’algorithme est très général. On peut parler d’un algorithme pour la traduction d’une langue dans une autre, de l’algorithme d’un contrôleur aérien (traitant les informations sur les mouvements des avions selon des règles fixes), et d’autres exemples de processus de contrôle décrits par des algorithmes. Par conséquent, le concept d’algorithme est l’une des idées centrales de la cybernétique et de l’informatique.
Exemple d’un algorithme.
Les entrées possibles et les résultats possibles sont tous les mots possibles sur l’alphabet $ \{ a, b \} $. La transition d’un mot $ X $à un mot $ Y $est » admissible » dans les deux cas suivants (où $ P $désigne un mot arbitraire) : 1) $ X $est de la forme $ aP $, et $ Y $est de la forme $ Pb $ ; ou 2) $ X $est de la forme $ baP $, tandis que $ Y $est de la forme $ Paba $. Les instructions sont formulées comme suit : « désignant un certain mot comme entrée, exécuter les transitions autorisées jusqu’à obtenir un mot de la forme aaP ; puis s’arrêter et laisser le mot P être le résultat » . Ces instructions constituent un algorithme, qui sera désigné par $ \mathfrak A $. Prenons le mot $ babaa $ comme entrée. Après une transition, on obtient $ baaaba $ ; après la seconde, on obtient $ aabaaba $. Ici l’algorithme s’arrête avec $ baaba $ comme résultat. Considérons une autre entrée $ baaba $. On obtient, successivement, $ abaaba, baabab, abababa, bababab, babababa, … $. On peut montrer que ce processus ne se terminera jamais (c’est-à-dire qu’aucun des mots générés ne commencera jamais par $ aa $). Prenons maintenant $ abaab $ comme entrée. On obtient $ baabb, abbaba, bbabab $ ; aucune autre transition admissible n’est possible, et, en même temps, la condition de fin n’est pas satisfaite. On a un arrêt sans résultat. Ainsi, l’entrée $ babaa $ convient à $ \mathfrak A $, et les entrées $ baaba $ et $ abaab $ ne conviennent pas.
La signification des algorithmes.
En science, on rencontre des algorithmes partout : une solution « générale » à un problème nécessite un algorithme. La capacité de l’homme à additionner des nombres en est un exemple. Non pas le fait qu’il puisse trouver, tôt ou tard, la somme de deux nombres quelconques, mais plutôt dans le sens où il possède une méthode d’addition unique de deux nombres quelconques donnés sous forme écrite, c’est-à-dire un algorithme d’addition tel que la méthode bien connue de l’addition en colonne. « Généralement », la résolution d’un problème est formalisée comme la résolution d’un problème algorithmique. Un problème algorithmique se compose d’instances de problème distinctes, et un algorithme unique doit être trouvé pour la solution de toutes ces instances. Si un tel algorithme n’existe pas, on dit que le problème algorithmique est insoluble. Ainsi, le problème de la résolution numérique d’équations d’un type donné et le problème de la traduction automatique sont des problèmes algorithmiques. Leurs instances de problème sont, respectivement, de trouver la solution numérique d’équations individuelles du type donné, et la traduction de phrases individuelles. D’autres exemples sont la vérification des égalités algébriques en algèbre ; le problème algorithmique de la reconnaissance de la déductibilité des propositions à partir d’axiomes donnés en logique mathématique. (En logique mathématique, le concept d’algorithme est également important car il sert de base au concept clé de calcul, qui est une généralisation et une forme plus précise des concepts intuitifs de « preuve » et de « démonstration »). L’établissement de l’insolvabilité d’un problème algorithmique donné (par exemple, le problème de l’établissement de la vérité ou de la démontrabilité des phrases dans un certain langage logico-mathématique) est important, car il montre qu’en principe, les instances spécifiques de ce problème ne peuvent être résolues que par des méthodes qui sont spécifiques à chaque instance individuelle du problème.
L’importance scientifique du concept d’algorithme est reconnue depuis longtemps. Depuis les temps les plus reculés, les gens ont cherché des méthodes constructives pour résoudre les problèmes mathématiques. Ces efforts ont généralement bénéficié de la nouvelle disponibilité de notations symboliques appropriées. Ce processus a apporté une contribution significative à la connaissance scientifique, surtout après qu’il soit devenu évident que certains problèmes sont intrinsèquement insolubles (la quadrature du cercle, etc.). Après qu’il ait été reconnu que certains problèmes ne peuvent être résolus par des calculs directs, le concept théorique d’ensemble est né au XIXe siècle. Ce n’est qu’après une période de développement rapide de ce concept (qui n’impliquait pas de problèmes de méthodes constructives dans leur sens moderne), qu’il a été possible au milieu du 20ème siècle de revenir aux problèmes constructifs, mais ceci à un niveau différent, enrichi par le concept d’algorithme qui s’était cristallisé entre temps. Ce concept constitue la base du courant constructif en mathématiques.
Le mot « algorithme » vient du mot « algoritmi » , ce dernier étant la translittération latine du nom du mathématicien arabe du 9ème siècle Al-Khwarizmi. Un « algorithme » dans l’Europe du Moyen Âge était « le système décimal-positionnel et l’art de calculer avec lui » , puisque c’est par la traduction latine (12e siècle) du traité d’Al-Khwarizmi que le système positionnel a été introduit en Europe.
La structure d’un processus algorithmique.
Un processus algorithmique est un processus de conversion consécutive d’objets constructifs par « étapes » discrètes , chaque étape consistant à remplacer un objet constructif par un autre. Ainsi, lorsqu’on applique l’algorithme $ \mathfrak A $au mot $ baaba $, il s’ensuit, successivement, les mots $ baaba, abaaba, baabab $, etc. Si l’on applique, par exemple, l’algorithme de la soustraction en colonne à la paire de nombres <307, 49 >, on obtient, successivement, les objets constructifs suivants :
$$ \begin{array}{rrrr}307 &3 \dot{0} 7 &\dot{3}. \dot{0} 7 &\dot{3} \dot{0} 7 \\N-underline{- 49 } &\underline{- 49 } &\underline{- 49 } &\underline{- 49 } \\{} & 8 &58 &258 \\\end{array}$$
On remarquera que, dans une série d’objets constructifs successifs, chaque objet constructif successif est entièrement déterminé (dans le cadre de l’algorithme donné) par l’objet constructif qui le précède immédiatement. Dans l’approche plus rigoureuse, on suppose également que la transition de tout objet constructif vers celui qui le suit immédiatement est suffisamment « élémentaire » – en ce sens que la transformation en une étape de l’objet précédent en l’objet qui lui succède immédiatement est locale (ce n’est pas l’objet constructif entier qui est transformé, mais seulement sa partie limitée par l’algorithme ; de plus, cette transformation elle-même n’est pas déterminée par l’objet précédent complet, mais seulement par une partie limitée de celui-ci).
En conséquence, on a non seulement un ensemble d’entrées possibles et un ensemble de résultats possibles, mais aussi un ensemble de résultats intermédiaires possibles, représentant le milieu de travail dans lequel évolue le processus algorithmique. En ce qui concerne $ \mathfrak A $, ces trois ensembles coïncident, mais ce n’est pas le cas de l’algorithme de la soustraction par colonne – les entrées possibles sont des paires de nombres, les résultats possibles sont des nombres (tous dans le système décimal), tandis que les résultats intermédiaires possibles sont des enregistrements « à trois étages » du type
$ \begin{array}{r} p \\\\underline{- q } \\\\\\N r \N\N\N\N\N -end{array}$
où $ q $ est la trace écrite du nombre dans le système décimal, $ r $ est une trace similaire ou le mot vide, tandis que $ p $ est la trace écrite d’un nombre dans le système décimal, avec des points sur certains des chiffres. En règle générale, on peut distinguer plusieurs paramètres (non indépendants) caractéristiques d’un algorithme : 1) l’ensemble des entrées possibles ; 2) l’ensemble des résultats possibles ; 3) l’ensemble des résultats intermédiaires possibles ; 4) la règle de départ ; 5) la règle de transition directe ; 6) la règle de terminaison ; et 7) la règle de récupération du résultat.
Formalisation du concept d’algorithme.
Le concept d’algorithme dans sa forme générale est un concept mathématique fondamental qui ne peut être défini en termes de concepts plus simples. A proprement parler, les formalisations du concept d’algorithme le restreignent en fait quelque peu. Dans chacune de ces formalisations, une définition exacte est donnée d’une certaine classe à l’intérieur de laquelle chacun des paramètres peut varier. Les diverses formalisations diffèrent les unes des autres par le choix de ces classes. Puisque les paramètres définissent sans ambiguïté un algorithme, un choix de domaines de paramètres détermine une certaine classe d’algorithmes. Cependant, un tel choix ne peut prétendre être une formalisation du concept intuitif d’algorithme, que si l’on peut être sûr que pour tout algorithme « intuitif », il existe un algorithme équivalent dans la classe d’algorithmes définie par le choix considéré. Cette exigence est formulée pour chaque formalisation comme une hypothèse fondamentale, qui, dans l’état actuel des connaissances, ne peut être démontrée mathématiquement.
Les premières formalisations de ce type sont dues à E.L. Post
et à A.M. Turing , dont les constructions ont anticipé à bien des égards les idées sur lesquelles reposent les ordinateurs modernes. Il existe également des versions formulées par A.A. Markov ,
(cf. Algorithme normal) et par A.N. Kolmogorov , , qui a fondé l’approche sur des complexes topologiques constructifs d’un certain type, ce qui permet d’exprimer plus précisément la propriété « d’être local » d’une transformation. Dans chacune de ces formalisations, l’hypothèse fondamentale est en accord satisfaisant avec la pratique. Un autre argument en faveur de cette hypothèse est le fait que, comme on peut le démontrer, toutes les versions formelles (de la calculabilité effective) qui ont été proposées sont équivalentes.
À titre d’exemple, considérons la formalisation proposée par Turing. Dans sa forme originale, il s’agissait d’une description d’un ordinateur théorique consistant en 1) une bande infinie, divisée en cellules consécutives, chaque cellule pouvant contenir un symbole de l' »alphabet de la bande » de la machine ; et 2) une « commande finie » qui, à chaque instant, se trouve dans un « état » (parmi une liste finie donnée d’états). La commande finie peut se déplacer le long de la bande, une cellule à la fois, et modifier le contenu des cellules qu’elle traverse. Un programme qui contrôle le mouvement de la commande finie constitue l’algorithme des calculs effectués sur une telle machine (un « algorithme de Turing »). Pour une description plus exacte et plus détaillée, voir Machine de Turing. On trouvera ici une exposition modernisée de la construction de Turing. Pour définir un algorithme de Turing, on spécifie a) des alphabets disjoints par paire $ B, D, C $, avec une lettre distinguée $ \lambda $ dans $ D $ et des lettres distinguées $ \alpha $ et $ \omega $ dans $ C $ ; et b) un ensemble de paires de la forme $ \langle p \xi , \eta Tq \rangle $où $ p, q \in C $, $ \xi , \eta \in B \cup D $, tandis que $ T $ est l’un des trois symboles $ -, 0, + $ ; dans cet ensemble (qui est appelé un programme) il n’y a pas deux paires avec la même première coordonnée. Les entrées et les sorties possibles sont des mots sur $ B $, tandis que les résultats intermédiaires possibles sont des mots sur $ B \cup D \cup C $ qui ne contiennent pas plus d’une lettre de $ C $. La règle de départ est que le mot initial $ P $ est converti en mot $ \lambda \alpha P \lambda $. La règle de fin est qu’un résultat intermédiaire qui contient $ \omega $ est final. La règle de récupération de la sortie est que la sortie est la séquence de lettres du résultat intermédiaire final qui suit $ \omega $et précède la première lettre n’appartenant pas à $ B $. La règle de transformation qui convertit $ A $en $ A ^ \prime $est la suivante. La lettre $ \lambda $ est écrite à gauche et à droite de $ A $ ; dans le mot ainsi formé, la partie de la forme $ \epsilon p \xi $, où $ p \in C $, $ \epsilon \xi \in B \cup D $, est remplacée par un mot $ Q $ conformément à la règle : on cherche dans le programme un couple dont le premier terme est $ p \xi $ ; que le second terme de ce couple soit $ \eta Tq $ ; si $ T $est $ – $, $ Q = q \epsilon \eta $ ; si $ T = 0 $, $ Q = \epsilon q \eta $ ; si $ T $ est $ + $, $ Q = \epsilon \eta q $. Le mot produit par cet échange est $ A ^ \prime $. Pour les références, voir , , , , ,
de Algorithmes, théorie des.
L’hypothèse fondamentale mentionnée ci-dessus est généralement appelée la thèse de Church-Turing ou hypothèse de Turing. Cette thèse affirme que ce qui peut être effectivement calculé selon l’intuition de chacun sur ce qui constitue un processus efficace, peut également être calculé par une machine de Turing, c’est-à-dire une notion d’algorithme formellement définie. Par sa nature même d’identifier une notion informelle intuitive avec une définition formelle précise, la thèse de Church-Turing ne peut pas être prouvée formellement.
De nombreuses formalisations se sont avérées équivalentes, et aucune formalisation ne s’est révélée strictement plus puissante. Outre les formalisations mentionnées ci-dessus, les références suivantes sont les plus courantes en Occident : La formalisation par Church des nombres et des fonctions calculables par des termes lambda, les schémas récursifs généraux de Kleene, et le modèle de machine à registre proposé par J.C. Shepherdson et H.E. Sturgis, qui a été étendu en un modèle d’ordinateur plus réaliste par S.A. Cook et R.A. Reckhow. Les versions de Markov et de Kolmogorov sont moins connues. Pour être complet, les références originales de Turing et Post sont également données.
| A.M. Turing, « On computable numbers, with an application to the Entscheidungsproblem » Proc. London Math.Soc. Ser. 2 , 42 (1936) pp. 230-265 | |
| A.M. Turing, « Corrections à « On computable numbers, with an application to the Entscheidungsproblem » » Proc. London Math.Soc. Ser. 2 , 43 (1937) pp. 544-546 | |
| A. Church, « An unsolvable problem of elementary number theory » Amer. J. Math. , 58 (1936) pp. 345-363 | |
| S.C. Kleene, « General recursive functions of natural numbers » Math. Ann. , 112 (1936) pp. 727-742 | |
| E.L. Post, « Formal reductions of the general combinatorial decision problem » Amer. J. Math. , 65 (1943) pp. 197-268 | |
| J.C. Shepherdson, H.E. Sturgis, « Computability of recursive functions » J. Assoc. Comp. Mach. , 10 (1963) pp. 217-255 | |
| S.A. Cook, R.A. Reckhow, « Time-bounded random access machines » J. Computer and System Sciences , 7 (1973) pp. 354-375 |
.