Leçons sur l'informatique

Richard P. Feynman

• Éditeur: Odile Jacob
• Année: 2006
• Imprimer l'ISBN: 9782738114150
• ISBN de l'eBook: 9782738183040
• Sujet: Informatique
• Sujet: Sciences générales de l'informatique

Richard Feynman était un calculateur prodige. Dans le Projet Manhattan, il fut chargé du calcul à la main de l'énergie libérée par l'explosion d'une bombe atomique. Il connaissait mieux que personne les possibilités et les limites du calcul électronique. Dans ces leçons, il expose les bases de l'informatique : les machines de Türing, l'architecture des ordinateurs, la théorie du calcul informatique, la théorie du codage et de l'information. Il livre aussi ses réflexions sur les relations profondes entre physique et informatique : thermodynamique, ordinateurs quantiques et physique des semi-conducteurs. On retrouve ici avec délectation le style brillant et humoristique de Feynman. Richard Feynman, prix Nobel de physique en 1965, était professeur de physique théorique au California Institute of Technology. Les éditions Odile Jacob ont notamment publié ses célèbres Leçons sur la physique et ses Leçons sur la gravitation.

LEÇON 1

---

Les ordinateurs : introduction

Les ordinateurs peuvent faire tout un tas de choses. Ils sont capables d’additionner des millions de nombres en un clin d’œil. Ils peuvent vaincre les plus grands maîtres d’échecs. Certains guident des missiles jusqu’à leur cible, d’autres nous permettent de réserver dans l’avion une place non-fumeur, entre une religieuse férue de guitare et un professeur de physique. Certains peuvent même jouer du bongo... autant dire que c’est plutôt varié ! Donc, si nous devons étudier les ordinateurs, mieux vaut sélectionner tout de suite ceux d’entre eux qui nous intéresseront, et en quoi.

En fait, nous ne nous attarderons pas longtemps sur les machines elles-mêmes. En effet, l’inspection des entrailles d’un ordinateur révèle qu’à l’instar des êtres humains, ces engins se ressemblent tous plus ou moins. Ils pourront se distinguer par leur fonction, par la nature de leurs données d’entrée ou de sortie — l’un fera de la musique et l’autre du dessin, certains pourront être commandés par un clavier, d’autres par le couple moteur des roues d’une voiture — mais dans le fond, tous sont très semblables. Nous ne nous intéresserons donc qu’à leurs entrailles. En outre, nous ne ferons aucune hypothèse sur leurs structures d’entrée et de sortie, ni sur la manière dont l’information entre et sort de la machine. Tout ce qui nous intéressera, quelle que soit la manière dont la donnée d’entrée est fournie à la machine, c’est qu’elle le soit sous forme numérique ; de même, quel que soit le signal de sortie quittant les entrailles de l’ordinateur, nous demanderons uniquement qu’il s’agisse d’un signal numérique. J’entends par là un nombre binaire : une série de 0 et de 1.

À quoi ressemblent les entrailles d’un ordinateur ? Grosso modo, disons que la machine est construite à partir d’un ensemble d’éléments simples. Ces derniers n’ont rien de particulier (ils pourraient être des valves de contrôle, par exemple, ou des perles sur les fils d’un boulier) et il existe un large choix de possibilités pour l’ensemble élémentaire. Tout ce qui compte, c’est que nous puissions les utiliser pour tout construire. Comment s’agencent-ils ? Ici encore, les choix sont nombreux ; la meilleure structure sera sélectionnée en fonction, par exemple, de la vitesse, de la dissipation d’énergie, de l’esthétique ou de ce qui nous passera par la tête. À cet égard, la diversité des ordinateurs s’apparente un peu à la diversité des habitations : à première vue, nous dirions d’un immeuble hausmannien qu’il n’a rien de commun avec un hangar à bateaux. Et pourtant, tous deux sont construits à partir des mêmes éléments (briques, mortier, bois, huile de coude) ; certes, il en faudra plus pour édifier un immeuble hausmannien, et il faudra les agencer différemment suivant les besoins de ses occupants. Mais au fond, ces deux édifices ont beaucoup de points communs.

Restons dans l’abstrait pour le moment et posons-nous la question de savoir comment câbler un ensemble de tels ou tels éléments afin qu’il accomplisse le plus de choses possible. Voilà une question qui peut sembler fondamentale. Et pourtant, ici encore, j’y répondrai en disant que, dans une certaine mesure, cela importe peu. Un ordinateur sachant faire un certain nombre de choses (ou, plus rigoureusement, une machine possédant un certain « ensemble suffisant » de procédures élémentaires), effectuera à peu près les mêmes tâches que n’importe quel autre. Voilà en gros l’essence du grand « principe d’universalité ». « Holà ! pas si vite, vous écriez-vous, ma calculette de poche est incapable de faire des simulations concernant Jupiter comme une armée de super-calculateurs Cray ! » Eh bien, si : il faudrait la réorganiser un peu, gonfler sa mémoire... certes, elle serait terriblement lente, mais avec suffisamment de temps, votre calculette pourrait reproduire n’importe quel calcul mené par un Cray. Plus généralement, imaginons deux ordinateurs A et B, et supposons que nous connaissions A sur le bout des doigts (nous savons comment il fonctionne, nous connaissons ses « règles de changement d’état », et ainsi de suite). Supposons que la machine B soit capable de décrire plus ou moins l’état de A. Nous pouvons alors utiliser B pour simuler le fonctionnement de A en décrivant ses changements d’état successifs. Autrement dit, B imiterait la machine A. Cela prendrait une éternité dans le cas de figure d’une machine B rudimentaire et d’un ordinateur A très sophistiqué, mais au bout du compte, B pourra reproduire tout ce que fait A. Nous en ferons la preuve un peu plus loin dans le cours, lorsque nous nous intéresserons à la conception d’ordinateurs tels que B, connus sous le nom de « machines de Turing ».

Abordons la question de l’universalité sous un autre angle. Le langage fournit une bonne analogie. Posons-nous la question de savoir comment désigner au mieux un objet donné ? Disons... un véhicule à essence, muni de quatre roues. Bien sûr, dans la plupart des langues, ou tout du moins dans les langues occidentales, il existe un mot pour désigner cet engin : nous dirions voiture, les Anglo-Saxons disent car, les Italiens machina et ainsi de suite. Toutefois certaines langues, dans leur évolution, n’ont pas eu besoin d’un mot pour dire voiture, et les natifs de ces langues-ci auront à inventer une description, sûrement longue et compliquée, à partir de leurs éléments linguistiques de base. Et pourtant, aucune de toutes ces descriptions n’est intrinsèquement « meilleure » qu’une autre : toutes font leur boulot, et seule l’efficacité les distingue. Inutile d’introduire une démocratie des mots. Poursuivons jusqu’aux alphabets. Quel serait, par exemple, le meilleur alphabet pour la langue française ? J’entends par là : pourquoi nous cantonner à nos vingt-six lettres habituelles ? Tout ce que nous pouvons faire avec ces vingt-six lettres, nous le faisons tout aussi bien à l’aide de trois symboles seulement (je pense à l’alphabet morse : point, tiret, espace), voire même deux (par exemple dans le code télégraphique Bacon, où les lettres A à Z sont représentées par des nombres binaires à cinq chiffres). Nous avons donc beaucoup de liberté dans le choix de notre ensemble fondamental d’éléments, et ce choix n’affecte que l’efficacité de notre langage, le poids de nos livres : il n’existe pas d’alphabet ou de langage « meilleur » que les autres ; chacun est universel dans sa logique et chacun peut imiter tous les autres. Pour revenir aux ordinateurs, le principe d’universalité énonce en fait que l’ensemble des besognes compliquées que peut effectuer un « ensemble suffisant » de procédures élémentaires est indépendant du détail de la structure de cet ensemble de base.

Afin que les ordinateurs d’aujourd’hui puissent accomplir les tâches si complexes qui leur sont imparties, nous devons établir une décomposition précise et exhaustive de cette tâche en procédures simples — le software — et disposer d’une machine effectuant ces étapes élémentaires dans un ordre particulier — voilà le hardware. Ces instructions doivent être exactes et non ambiguës. Bien entendu, dans la vie, nous ne nous disons jamais tout ce que nous avons à nous transmettre dans les moindres détails, car le contexte, le langage corporel ou le degré d’intimité avec notre interlocuteur sont autant d’aspects qui « comblent les ellipses » et nous préservent des ambiguïtés. En revanche, les ordinateurs sont incapables de « deviner » ce que nous voulons dire comme pourrait le faire un être humain. Nous devons tout décortiquer jusque dans les moindres détails. Qui sait, peut-être nos machines parviendront-elles un jour à interpréter des descriptions plus approximatives, mais pour le moment, nous devons rester très pointilleux lorsque nous demandons quelque chose à un ordinateur.

Voyons comment construire des instructions compliquées à partir d’un ensemble d’éléments simples. Manifestement, si nous partons d’un ensemble d’instructions très rudimentaire (notons-le B), il nous faudra, pour réaliser un processus complexe, une description faramineuse, et le « programme » correspondant sera long et compliqué. Imaginons par exemple la situation suivante : nous voulons que notre ordinateur exécute toutes sortes d’opérations numériques, mais la multiplication ne fait pas partie des opérations élémentaires de l’ensemble B. Demandons à notre machine de multiplier 35 par 3, elle répond : « Faire... quoi ? » Toutefois, si B contient l’addition, en y réfléchissant une seconde, vous verrez qu’on peut bel et bien effectuer des multiplications en additionnant plusieurs fois le même nombre (dans notre exemple, il suffit d’ajouter deux fois de suite 35 à lui-même). Cela étant, la rédaction des programmes à exécuter à partir de B sera beaucoup plus simple si nous ajoutons à B l’instruction distincte « multiplier », que nous définissons à partir des instructions élémentaires de B permettant de fabriquer la multiplication. Dans ce cas, il nous suffit alors, pour multiplier deux nombres, de demander : « Ordinateur ! 3 fois 35 ? », et celui-ci reconnaîtra l’instruction « fois » (ce n’est rien de plus que quelques additions, opération qu’il connaît bien). La machine décompose ces instructions à tiroir en leurs composants élémentaires. Ce faisant, elle nous évite de nous enliser en revenant sans cesse aux concepts élémentaires. Les processus complexes sont donc construits étape par étape. Il existe dans la vie de tous les jours un analogue très semblable : nous avons coutume de remplacer par un mot tout un ensemble d’idées, et les liaisons de l’une à l’autre. Lorsque nous utilisons ces idées ou leur interconnexion, nous pouvons donc nous contenter d’un seul mot, ce qui nous évite de remonter jusqu’aux concepts élémentaires. Les ordinateurs sont si complexes qu’il s’avère généralement indispensable de simplifier les idées de la sorte, et il est essentiel de bien les concevoir pour ne pas se perdre dans les détails.

Nous commencerons par construire un ensemble de procédures très élémentaires, afin de comprendre comment exécuter des opérations comme l’addition de deux nombres ou le transfert de nombres d’une case mémoire à une autre. Puis nous passerons au niveau de complexité suivant, en utilisant ces instructions dans le but de produire des opérations comme la multiplication, et ainsi de suite. Nous ne poursuivrons pas très loin dans la hiérarchie, mais si vous tenez à voir jusqu’où cela peut aller, consultez par exemple l’article de P. J. Denning et R. L. Brown sur les systèmes opératoires (Scientific American, septembre 1984, p. 96-104) : ils en dénombrent treize niveaux ! Ils partent du niveau 1, celui des circuits électroniques (enregistreurs, portes, bus) et terminent au niveau 13, celui du système d’exploitation, qui gère l’environnement de programmation de l’utilisateur. Cette décomposition hié...

Table des matières

• Couverture
• Titre
• Copyright
• Sommaire
• LEÇON 1 - Les ordinateurs : introduction
• LEÇON 2 - De l’organisation des ordinateurs
• LEÇON 3 - La théorie du calcul informatique
• LEÇON 4 - Codage et théorie de l’information
• LEÇON 5 - Réversibilité et thermodynamique du calcul informatique
• LEÇON 6 - Ordinateurs quantiques
• LEÇON 7 - Aspects physiques de l’informatique
• Suggestions de lectures
• Index