Qu’est-ce qu’un calcul ?

Chaque niveau de ce site calcule quelque chose. Les portes calculent des fonctions booléennes, le CPU calcule l’effet d’une instruction, un programme calcule sa sortie, une application calcule ce qu’elle doit afficher. Mais qu’est-ce qu’un calcul ? Qu’ont en commun toutes ces choses, et y a-t-il quelque chose qu’un ordinateur ne peut pas faire, aussi rapide et aussi grand soit-il ?

Ces questions ont trouvé leur réponse dans les années 1930, avant qu’existe le moindre ordinateur électronique, chez des mathématiciens qui cherchaient à dire précisément ce qu’est « une procédure ». Leurs réponses sont toujours le socle : elles disent ce que tout ordinateur peut faire en principe, pourquoi une machine peut en imiter n’importe quelle autre, et pourquoi certains problèmes ne pourront jamais être résolus par aucun programme.

Les algorithmes

Un algorithme est une liste finie d’instructions précises qui transforme une entrée en une sortie. Le mot vient du nom du mathématicien persan du IXe siècle al-Khwârizmî, dont l’ouvrage a diffusé des méthodes de calcul pas à pas, mais le plus ancien algorithme encore utilisé chaque jour est plus vieux : l’algorithme d’Euclide pour le plus grand commun diviseur, mis par écrit vers 300 av. J.-C.

Pour trouver le PGCD de a et b : si b vaut 0, la réponse est a. Sinon, remplacer (a, b) par (b, a mod b) et recommencer.

Pour 1071 et 462 :

1071 = 2 × 462 + 147
 462 = 3 × 147 +  21
 147 = 7 ×  21 +   0     → the GCD is 21

Cette courte recette a tout ce qui fait un algorithme :

• chaque étape est définie : elle ne demande aucun jugement, un employé ou une machine peut la suivre ;
• chaque étape est effective : on peut réellement l’exécuter, avec un crayon et du papier, en un temps fini ;
• elle se termine : le second nombre diminue strictement à chaque étape, donc il finit par atteindre 0 ;
• elle est finie, mais fonctionne pour des entrées de n’importe quelle taille.

Une recette qui dit « remuer jusqu’à ce que ça ait l’air bon » n’est pas un algorithme ; « remuer trois minutes » en est presque un.

Qu’est-ce qui compte comme une étape ?

En 1928, David Hilbert a demandé s’il existait une procédure mécanique capable de décider, pour tout énoncé de la logique mathématique, s’il est démontrable : l’Entscheidungsproblem, le « problème de la décision ». Pour répondre « non », il faut dire exactement ce qu’est une procédure mécanique ; sinon quelqu’un pourra toujours prétendre qu’il en existe une plus astucieuse.

En 1936, deux réponses sont parues à quelques mois d’intervalle. Alonzo Church a défini le calcul par le lambda-calcul, un système où tout est une fonction appliquée à d’autres fonctions. Alan Turing, dans son article On Computable Numbers, a pris une voie plus physique : il a imaginé une personne qui calcule avec un crayon et du papier, et a réduit ce qu’elle fait au strict minimum.

La machine de Turing

Une machine de Turing possède :

• un ruban, divisé en cases, illimité dans les deux sens, chaque case contenant un symbole d’un alphabet fini (ici 0, 1 et le blanc _) ;
• une tête qui lit et écrit une case à la fois et peut se déplacer d’une case à gauche ou à droite ;
• un état, pris dans un ensemble fini ;
• une table de règles : pour chaque couple (état, symbole lu), quoi écrire, dans quel sens se déplacer, et dans quel état passer ensuite.

C’est tout. Il n’y a ni arithmétique, ni adresses mémoire, ni variables : seulement une table finie et un ruban. Voici une machine qui ajoute 1 à un nombre binaire. Elle démarre dans l’état right, sur le chiffre le plus à gauche :

Elle marche vers la droite jusqu’au bout du nombre, fait demi-tour, et propage la retenue : chaque 1 devient 0 jusqu’à ce qu’un 0 (ou un blanc, au-delà du chiffre de gauche) devienne 1. Lancée sur 1011 (onze), elle fait huit pas ; la position de la tête est entre crochets :

0  right  [1]011
1  right  1[0]11
2  right  10[1]1
3  right  101[1]
4  right  1011[_]
5  carry  101[1]_
6  carry  10[1]0_
7  carry  1[0]00_
8  halt   1[1]00_      → 1100, twelve

Voici la machine elle-même. Le ruban est la rangée de cases, le triangle est la tête, et l’étiquette colorée en dessous est l’état. À chaque pas, la ligne surlignée de la table est la seule règle qui correspond à l’état courant et au symbole sous la tête : la machine n’a aucun autre choix à faire.

Lancée sur 1011, elle passe par les neuf mêmes configurations que la trace ci-dessus et s’arrête sur 1100. Essayez 111 : la retenue sort par la gauche, la machine écrit un 1 sur la case blanche qui s’y trouve, et 111 devient 1000, là encore en huit pas. Tapez n’importe quel nombre binaire : les six mêmes règles lui ajoutent 1 ; seul le nombre de pas change, selon la longueur du nombre et la série de 1 qui le termine.

Remarquez ce qui se passe quand vous appuyez sur Lecture : une machine, l’ordinateur devant vous, exécute un programme qui est une autre machine. C’est l’idée au cœur de ce chapitre.

La thèse de Church-Turing

Les machines de Turing ont l’air désespérément faibles. Pourtant, avec assez d’états, elles savent additionner, multiplier, comparer, trier, exécuter n’importe quel algorithme jamais écrit. Le lambda-calcul de Church s’est révélé calculer exactement les mêmes fonctions que les machines de Turing, et il en est allé de même pour toutes les autres définitions proposées depuis : fonctions récursives, machines à registres, automates cellulaires, tous les langages de programmation dotés d’une mémoire illimitée.

La thèse de Church-Turing affirme que ce n’est pas une coïncidence : tout ce qui peut être calculé par une procédure effective pas à pas peut l’être par une machine de Turing. C’est une thèse, pas un théorème, parce que « procédure effective » est une notion informelle ; on ne peut pas la démontrer, seulement l’étayer. Quatre-vingt-dix ans de nouveaux modèles, tous équivalents, l’étayent solidement.

Un système capable de calculer tout ce que calcule une machine de Turing est dit Turing-complet. C, Python, JavaScript et le jeu d’instructions x86 le sont, avec une mémoire illimitée. Par accident, des choses très étranges le sont aussi : le jeu de la vie de Conway, les templates C++ évalués à la compilation. Il en faut étonnamment peu : de la mémoire à lire et à écrire, et un moyen de choisir quoi faire ensuite en fonction de ce qu’on a lu.

L’universalité : une machine pour les exécuter toutes

L’idée la plus importante de Turing se trouve dans le même article de 1936. La table de règles d’une machine n’est qu’une liste finie de symboles, donc on peut l’écrire sur un ruban. Turing a décrit une machine universelle : une machine de Turing fixe qui lit sur son ruban la description de n’importe quelle autre machine, suivie de l’entrée de celle-ci, et la simule pas à pas.

C’est exactement ce qu’est un ordinateur à programme enregistré. Le CPU est un matériel fixe ; le programme en mémoire dit quoi calculer. La même puce exécute un tableur, un jeu ou un simulateur de machine de Turing, ou un interpréteur pour une tout autre machine, comme l’interpréteur de bytecode JVM du chapitre sur le bytecode, lui-même un programme exécuté par une machine universelle.

Toute l’idée des niveaux repose là-dessus. Chaque niveau est une machine virtuelle (voir niveaux d’abstraction), réalisée en l’interprétant ou en la traduisant au niveau inférieur, et matériel et logiciel sont logiquement équivalents : tout ce que fait l’un, l’autre peut le faire. L’universalité en est la raison. Vers 1970, la plupart des ISA étaient interprétées par un microprogramme, un petit interpréteur intégré au processeur. Aujourd’hui, comme le montre le chapitre sur la microprogrammation, les instructions courantes d’un CPU haute performance sont décodées directement par le matériel en micro-opérations internes, le microcode étant réservé aux instructions complexes et rares. L’équilibre a bougé, mais l’équivalence reste la même.

On attribue parfois le COLOSSUS à Turing, et au COLOSSUS le déchiffrement d’Enigma ; en réalité, le COLOSSUS a été conçu par l’ingénieur Tommy Flowers contre le chiffre de Lorenz, et la machine de guerre de Turing était la Bombe, utilisée contre Enigma. Le chapitre sur les niveaux d’abstraction retrace cette histoire. La vraie contribution de Turing, c’est l’idée de machine universelle, qu’incarne tout ordinateur depuis les machines à programme enregistré de 1948–49.

Une réserve sur l’universalité : un vrai ordinateur a une mémoire finie, donc, à strictement parler, c’est un automate fini (gigantesque), pas une machine de Turing. En pratique la distinction compte rarement : quand un programme manque de mémoire, on en ajoute, ou bien le problème était trop gros pour n’importe quelle machine.

Ce qu’aucun programme ne peut faire

L’universalité a sa face sombre. Si des programmes peuvent prendre des programmes en entrée, on peut poser des questions sur les programmes, et certaines de ces questions n’ont pas d’algorithme.

La plus célèbre est le problème de l’arrêt : étant donnés un programme p et une entrée x, p finit-il par s’arrêter quand on l’exécute sur x, ou tourne-t-il indéfiniment ? Turing a démontré qu’aucun programme ne peut répondre correctement pour tous les p et tous les x. La preuve est courte. Supposons qu’on nous donne une fonction qui fait ceci :

int halts(program p, input x);   /* 1 if p(x) stops, 0 if it runs forever. Always answers. */

Alors on peut écrire ce programme :

void paradox(program p) {
    if (halts(p, p))     /* would p stop when given its own text? */
        for (;;) { }     /* then loop forever */
    else
        return;          /* otherwise stop */
}

Exécutons maintenant paradox sur son propre texte. Si halts(paradox, paradox) dit qu’il s’arrête, paradox boucle indéfiniment. S’il dit qu’il boucle indéfiniment, paradox s’arrête. Les deux réponses sont fausses. Donc halts ne peut pas exister, non parce qu’il serait difficile à écrire, mais parce que son existence est une contradiction. Le même argument a répondu à Hilbert : il n’existe pas de procédure mécanique qui décide de toutes les mathématiques.

Ce n’est pas qu’une curiosité. D’après le théorème de Rice (1953), toute question non triviale sur ce que fait un programme (affiche-t-il un jour « hello », accède-t-il un jour à ce tableau hors de ses bornes, est-ce un virus ?) est indécidable en général. C’est pourquoi les compilateurs ne peuvent pas trouver tous les bogues, pourquoi les antivirus s’appuient sur des signatures et des heuristiques, et pourquoi un analyseur statique doit parfois répondre « peut-être » : chacun répond à une version restreinte ou approchée d’une question impossible.

Des questions d’apparence simple peuvent être très difficiles même quand elles ne sont pas impossibles. Le problème du castor affairé (busy beaver) demande combien de pas peut faire la machine de Turing à n états qui s’arrête après avoir tourné le plus longtemps (sur un ruban vierge, avec deux symboles). Pour 4 états, la réponse est 107 pas. Pour 5 états, c’est 47 176 870, une valeur démontrée seulement en 2024, par un projet collaboratif qui a examiné toutes les machines à 5 états avec des preuves vérifiées par ordinateur. Pour 6 états, personne ne sait, et les candidats connus tournent bien plus longtemps qu’il n’y a d’atomes dans l’univers.

Calculable ou efficace

La thèse de Church-Turing dit ce qui peut être calculé ; elle ne dit rien de la vitesse. Une machine de Turing et un CPU moderne calculent les mêmes fonctions, mais pas à la même vitesse : notre machine de Turing a eu besoin de 8 pas pour ajouter 1 à un nombre de 4 chiffres, et en aurait besoin de plus pour des nombres plus longs, alors que le CPU additionne deux nombres de 64 bits en une seule instruction add. La représentation compte : le même calcul peut coûter un pas ou beaucoup, selon la machine.

Ce qui reste stable d’une machine raisonnable à l’autre, c’est le taux de croissance. Un problème qui demande un nombre de pas polynomial en la taille de l’entrée (n, n log n, n³) sur une machine raisonnable en demande un nombre polynomial sur n’importe quelle autre. C’est pourquoi la théorie de la complexité peut parler des problèmes indépendamment du matériel, et pourquoi le chapitre sur la complexité compte des pas plutôt que des secondes.

Cela répartit les problèmes en trois grandes catégories :

Tout problème dont les réponses se vérifient vite peut-il aussi se résoudre vite ? Cette question, P contre NP, est la plus célèbre question ouverte de l’informatique. La plupart des chercheurs pensent que la réponse est non, et beaucoup de choses reposent sur la difficulté : la cryptographie à clé publique dépend de problèmes, comme la factorisation des grands nombres, pour lesquels on ne connaît pas d’algorithme efficace.

À retenir

• Un algorithme est une liste finie d’étapes définies et effectives qui se termine : le PGCD d’Euclide en est un, vieux de 2 300 ans.
• Une machine de Turing (un ruban, une tête, un état et une table de règles) est le modèle complet de calcul le plus simple ; l’incrémenteur binaire ajoute 1 à 1011 en 8 pas.
• La thèse de Church-Turing : tout ce qui est calculable par une procédure effective l’est par une machine de Turing. Tout langage de programmation généraliste et tout CPU est Turing-complet, avec assez de mémoire.
• Une machine universelle exécute n’importe quelle autre machine à partir de sa description : c’est l’ordinateur à programme enregistré, et la raison pour laquelle fonctionnent les interpréteurs, les émulateurs et les niveaux de machines virtuelles.
• Le problème de l’arrêt n’a pas d’algorithme, et d’après le théorème de Rice aucune question non triviale sur le comportement d’un programme n’en a : les outils ne peuvent qu’approcher.
• Calculable ne veut pas dire efficace : certains problèmes ont des algorithmes rapides (P), d’autres ne peuvent qu’être vérifiés rapidement (NP), et d’autres encore ne peuvent pas être résolus du tout.