Chapitre 2 Qu'est-ce que l'informatique ?

1 Introduction

Le statut de l'informatique en tant que discipline est ambigu et mal compris : est-il à chercher du côté de la science ou du côté de la technique ? Quel est l'objet d'étude propre aux informaticiens ? Quelles sont leurs vraies compétences ? Avant de nous engager sur ces points, commençons par éliminer les mauvaises réponses :

l'informatique n'est pas la "science des ordinateurs" (ce que, pourtant, laisse croire sa traduction anglaise, "computer science") : non, les informaticiens ne savent pas nécessairement réparer un ordinateur en panne, diagnostiquer un problème électronique ou effectuer des branchements compliqués, ils ne sont pas toujours les meilleurs guides quand il s'agit d'acheter un nouveau modèle de scanner ou de modem ; oui l'informatique peut s'étudier avec un papier et un crayon, même en absence d'ordinateur...
l'informatique n'est pas la "science des logiciels" : non, les informaticiens ne connaissent pas nécessairement toutes les nouvelles versions des programmes du commerce, ils ne savent pas toujours utiliser toutes leurs fonctions, ils ne passent pas (toujours) leurs journées à tester des jeux ou à chercher des bugs...

La compétence réelle des informaticiens n'est ni matérielle, ni fonctionnelle. Alors, qu'est ce que l'informatique ? C'est quelque chose entre les deux, quelque chose de plus abstrait et de plus fondamental sans quoi ni les ordinateurs ni les logiciels ne pourraient fonctionner... Pour arriver à une définition satisfaisante, notre démarche sera de partir de ces deux niveaux de description habituels : matériel et logiciel, et de faire émerger leurs principes sous-jacents.

Commençons donc par l'aspect logiciel. La connaissance commune de l'informatique se fonde en effet généralement sur la pratique de quelques logiciels d'usage courant : traitements de texte, tableurs, navigation sur l'Internet... L'image de l'ordinateur comme "grosse machine à calculer", fonctionnant pendant des heures pour réaliser ses calculs, reste également présente, mais de façon plus mythique et lointaine, vue au cinéma. Y a-t-il une base commune à tous ces usages, apparemment si disparates ? Quelles sont les caractéristiques partagées par tous ces logiciels ?

Pour aborder ces questions, on peut commencer par remarquer que tout programme peut être décrit par deux aspects fondamentaux : les données qu'il manipule et les traitements qu'il permet de réaliser sur ces données. Le tableau de la figure 2.1 permet de résumer ces caractéristiques pour les logiciels les plus couramment utilisés.

logiciel données traitemements

traitement de textes caractères alphanumériques (lettres de l'alphabet, chiffres et tous les autres caractères du clavier) copier, coller, effacer, déplacer, intervertir, changer la casse ou la police, mettre en page...

calculs numériques, tableurs, outils de gestion nombres, opérations et symboles mathématiques calculer, écrire et résoudre des équations, faire des graphiques

jeux dessins, personnages animés, sons appliquer les règles du jeu

bases de données, logiciels documentaires textes, images, données factuelles stocker en mémoire et rechercher des données

Internet, CD-Rom toutes les données citées précédemment tous les traitements cités précédemment + communication entre machines, échange de données

Figure 2.1: données et traitements des logiciels courants

Toutes les données citées dans ce tableau (et toutes celles, en général, manipulées par les ordinateurs) ont un point commun : ce sont des données discrètes, c'est-à-dire distinctes les unes des autres et qu'on peut énumérer une par une. Tous les traitements évoqués ici (et tous les autres traitements possibles en informatique) ont également en commun d'être des traitements effectifs, exprimables par des algorithmes. Les fondements de l'informatique sont à chercher dans ces deux notions, que nous allons donc maintenant détailler.

2 Données discrètes et codage

Tout le monde a entendu dire que les ordinateurs "ne fonctionnent qu'avec des 0 et des 1". Qu'est-ce que cela signifie exactement et où, dans l'ordinateur, sont donc cachés ces 0 et ces 1 ? Pour le comprendre, il faut cette fois partir des composants matériels qui constituent un ordinateur et aborder quelques notions élémentaires de la théorie de l'information.

2.1 La notion de bit

L'unité de base de la théorie de l'information est le bit, contraction de binary digit, qui signifie en anglais nombre binaire. Un bit, par définition, est un composant quelconque ne pouvant se trouver que dans deux états possibles, exclusifs l'un de l'autre. On peut imaginer bien des dispositifs physiques pouvant répondre à cette définition, et nombre d'entre eux ont été exploités au moins une fois dans l'histoire de l'informatique. Ainsi, par exemple :

une lampe électrique qui est soit allumée soit éteinte : les tout premiers ordinateurs, dans les années 40, utilisaient ainsi des milliers de lampes ou "tubes à vide" : un tel dispositif était hélas en panne dès qu'une lampe grillait ;
un fil électrique dans lequel le courant circule ou pas (ou sa version miniaturisée, le "circuit intégré") : c'est évidemment le composant de base des ordinateurs, avec les transistors qui peuvent, eux, être vus comme des interrupteurs miniatures. Les fibres optiques réalisent la même fonction que les fils, mais avec la lumière au lieu de l'électricité.
un aimant pouvant être polarisé "Sud" ou "Nord" : les mémoires des ordinateurs actuels, leur "disque dur", ainsi que les anciennes disquettes, sont composés de milliards de petits aimants ;
une surface ayant soit un creux soit une bosse : les CD-audio, les CD-Rom, les DVD, ne sont rien d'autre que des morceaux de plastique gravés de creux et de bosses tellement minuscules que seul un faisceau laser peut les distinguer ;
un récipient pouvant être plein ou vide : il y a, à la Cité des Sciences de la Villette, un "calculateur à eau" fonctionnant avec des seaux et des tuyaux remplis d'eau.

Par convention, pour s'abstraire de ces contingences matérielles, on appelle l'un des deux états possibles d'un tel composant 0, et l'autre 1. Ces deux symboles sont arbitraires et n'ont pas de signification numérique. On aurait tout aussi bien pu choisir les symboles a et b à la place, ou tout autre couple de deux signes distincts, puisque c'est uniquement cette distinction qui est importante.

A partir de maintenant, un bit sera donc pour nous un espace dans lequel on pourra soit écrire 0, soit écrire 1. Que faire avec de tels composants aussi élémentaires ? Avec un seul, pas grand chose, mais avec plusieurs, beaucoup de choses !

Si, en effet, on dispose de deux bits, alors le nombre total d'états possibles que peuvent prendre ces deux bits est de quatre : 00, 01, 10 ou 11.

Si on en prend trois, alors huit combinaisons sont possibles : 000, 001, 010, 011, 100, 101, 110, 111. On peut représenter ces huit combinaisons comme tous les différents parcours possibles dans un arbre où chaque branche est un choix entre 0 ou 1, comme dans la figure 2.2.

Figure 2.2: arbre des combinaisons possibles de 3 bits

En fait, ajouter un bit multiplie par deux le nombre de combinaisons possibles, puisque le bit ajouté a lui-même deux états possibles. Dans la représentation arborescente, cela revient à dédoubler chaque "feuille" de l'arbre (chaque dernier élément), et donc à multiplier par deux le nombre total de chemins possibles (égal au nombre de feuilles). Ce raisonnement permet de montrer que, avec n bits, on a 2ⁿ combinaisons possibles.

Le bit est l'unité de comptage de la mémoire des ordinateurs. Les multiples utilisés se comptent également en puissance de deux.

1 octet (byte en anglais) = 8 bits (8 = 2³) et permet 2⁸ = 256 combinaisons différentes possibles
1 Kilo-octet = 2¹⁰ octets = 1024 octets, et coïncide presque avec la définition usuelle du kilo qui vaut 10³
1 Mega-octet = 1024 Kilo-octets, soit environ 10⁶ octets
1 Giga-octet = 1024 Mega-octets, soit environ 10⁹ octets
1 Tera-octet = 1024 Giga-octets, soit environ 10¹² octets

Pour avoir un ordre de grandeur de ces valeurs : une disquette a une capacité d'environ 1 Mega-octet, une clé USB entre 64 Mega-octet et 1 Giga octet, un CD contient environ 600 Mega-octet, un DVD jusqu'à environ 17 Giga-octets. La mémoire des disques durs actuels se compte aussi en Giga-octets. On peut en déduire par exemple le nombre d'aimants contenus sur une disquette... Voyons maintenant comment coder les données citées dans le tableau de la figure 2.1 à l'aide de bits.

2.2 Les caractères alphanumériques

Les caractères alphanumériques sont tous les caractères disponibles sur un clavier d'ordinateur, ainsi que ceux qui résultent des combinaisons de touches. Combien existe-t-il de caractères alphanumériques ? L'alphabet latin utilise 26 symboles différents, dont chacun existe en version minuscule et majuscule, ce qui fait 52 symboles. A ces lettres, s'ajoutent les 10 symboles de chiffres : 0, 1, 2,...9 et une vingtaine de notations mathématiques courantes : opérateurs (+, −, *, /), comparateurs (<, >), signe d'égalité (=), symboles logiques... De nombreux autres caractères sont utilisées dans les graphies usuelles : ponctuations (“.”, “;”, “?”, “!”, “:”), apostrophe, guillemets, tirets, parenthèses, crochets, accolades, soit encore au moins quinze dessins nouveaux. De plus, des caractères spéciaux sont passés à l'usage courant : symboles de monnaies ($, €) ou abréviations comme : &, &,@... Comptons-en donc une dizaine. Enfin, un éditeur de textes considère comme symbole certains signes invisibles comme les espaces blancs, les passages à la ligne ou les fins de fichier (comptons en 5). Notre très grossier calcul nous amène donc à environ :

52+10+20+15+10+5=112

Pour associer à chacun de ces caractères une suite distincte de 0/1 qui le code, nous avons donc au minimum besoin, d'après notre calcul précédent, de 7 bits, puisque 2⁷=128. C'est précisément ce que réalisait la première version du code ASCII (pour American Standard for Communication and International Interchange).

Mais ce calcul est trop restrictif. En effet, certaines langues utilisent en outre des caractères spéciaux : voyelles accentuées, trémas et cédilles en français, tilde espagnol, β allemand... Un nouveau symbole, comme celui qui a été choisi pour l'Euro, peut apparaître pour des raisons indépendantes de l'informatique. Il est donc plus raisonnable de conserver une marge de manoeuvre, et de prendre plutôt 8 bits, soit un octet, qui permet 256 combinaisons différentes. C'est ce que réalise le code ASCII actuel.

Ce code a donc subi des modifications, et il en existe de multiples variantes, mais nous ne rentrerons pas dans ces détails ici... Ces variations expliquent toutefois que des messages peuvent être plus ou moins déchiffrables quand on les fait passer d'une machine à une autre (parfois même d'un programme à un autre sur une même machine). Il a par exemple longtemps été recommandé d'éviter d'utiliser les caractères accentués dans les courriers éléctroniques, parce que certains programmes de gestion de ces courriers utilisaient un code rudimentaire (fondé sur les claviers américains) qui les ignorait.

Quelle que soit la variante adoptée, le codage des caractères alphanumériques est donc réalisé par une association arbitraire et conventionnelle entre un caractère et une suite de bits. Le tableau de la figure 2.3 donne quelques exemples du code ASCII sur 8 bits associé à certains caractères :

code ASCII caractère

00100011 #

00100100 $

00100101 %

01111010 z

01111011 {

00100001 !

00110001 1

Figure 2.3: quelques exemples de code ASCII

Depuis les années 90, une initiative internationale cherche à promouvoir une nouvelle manière de référencer tous les caractères de toutes les langues écrites (actuelles ou ayant existé) du monde : c'est la norme unicode. Elle répertorie environ 250 000 caractères différents, chacun associé à un nombre distinct. Mais cette norme ne fixe pas un codage en bits unique, et peut utiliser un nombre variable de bits (tous les caractères ne sont pas codés avec le même nombre de bits) ; nous ne la détaillerons pas non plus ici.

Les "éditeurs de textes" (comme le "Bloc Note" de Windows) sont des programmes servant à manipuler (copier, coller, effacer, déplacer, intervertir...) les caractères alphanumériques "purs". Ils permettent donc des substitutions de bits correspondant à des codes ASCII. Ils ne sont pas adaptés à la mise en page des textes, à leur formatage visuel, mais sont largement suffisants pour écrire des messages factuels ou des programmes informatiques.

Les logiciels de "traitements de textes" utilisent en outre des codes spéciaux spécifiques pour représenter la mise en page du texte : les marges, l'aspect "centrée" ou "justifié" d'un paragraphe, la police et la taille de l'affichage des caractères... Même en prenant en compte les nouveaux codes associés à cette présentation, le codage des textes est économique : sur une disquette (environ 1 Mega-octets) on peut stocker un livre de 500 pages et sur un CD (environ 600 Mega-octets) une encyclopédie.

2.3 Les nombres entiers

On pourrait procéder avec les nombres entiers de la même façon que précédemment, c'est-à-dire par association arbitraire. Les chiffres de 0 à 9 ont d'ailleurs, nous l'avons vu, en tant que caractère, un code ASCII. Mais les nombres ont un statut et un usage particuliers : ils sont complètement ordonnés et servent à faire des calculs. Leur codage utilise une technique mathématique adaptée : la numérotation binaire (ou en base 2).

Pour comprendre le codage binaire des nombres, le mieux est d'abord de bien analyser leur représentation usuelle en base 10, dite aussi décimale. Cette représentation fait usage de 10 symboles différents de base : 1, 2, 3, ..., 9 et 0 et utilise le principe de la numérotation de position. Cette numérotation a été inventée par les indiens au Vème siècle en même temps que le symbole 0 (qu'elle rend nécessaire), et transmis en occident par l'intermédiaire des arabes (d'où le nom de "chiffres arabes"). Son principe est que chacun des symboles constituant un nombre représente en fait une puissance croissante de 10 lu de droite à gauche. La valeur réelle du nombre est alors la somme de ces puissances. Ainsi par exemple :

533=5*100+3*10+3*1=5*10²+3*10¹+3*10⁰

2001=2*1000+1*1=2*10³+0*10²+0*10¹+1*10⁰

Quand on "lit" un tel nombre, on attribue à chaque chiffre qui le constitue, en fonction de sa place dans l'écriture du nombre, une certaine puissance de 10. Ainsi, les deux symboles "3" du premier nombre ne représentent pas, en fait, la même valeur (l'un vaut 30, l'autre vaut 3). La "grille de lecture" sous-jacente est donc un tableau de la forme :

10³	10²	10¹	10⁰
	5	3	3
2	0	0	1

Le principe de la "retenue" dans les additions est alors naturel : une somme de chiffres qui dépasse 10 pour une puissance de 10 donnée peut être représentée en passant à la puissance de 10 suivante, c'est-à-dire celle immédiatement à gauche. La représentation des chiffres romains n'utilise pas, elle, la numérotation de position. Par exemple, dans l'écriture du nombre 18 en chiffre romains : XVIII, les trois symboles "I" à la fin valent tous les trois 1, indépendamment de leur position. Dans un tel système, les opérations mathématiques s'effectuent très difficilement.

Le principe de la numérotation de position se généralise à n'importe quelle base de représentation en changeant simplement la puissance correspondante : pour la représentation binaire, ce sont donc les puissances de 2 qui vont servir. Pour une fois, nous prenons donc nos symboles 0/1 au sérieux : ici, 0 correspond bien au chiffre 0 et 1 au chiffre 1. Le tableau suivant donne des exemples de codage de nombres en base 2 :

2⁵=32	2⁴=16	2³=8	2²=4	2¹=2	2⁰=1	nombre décimal
		1	0	0	1	8 + 1 = 9
			1	1	1	4 + 2 + 1 = 7
	1	0	1	1	1	16 + 4 + 2 + 1 = 23
1	0	0	1	0	1	32 + 4 + 1 = 37

Grâce à cette représentation, les opérations mathématiques usuelles sur les nombres binaires s'effectuent exactement de la même manière que sur les nombres décimaux. Ainsi, les "retenues" sont nécessaires dès que l'on dépasse un total de 2 pour une puissance de 2 donnée ; elles consistent, comme en base 10, à ajouter 1 dans une colonne plus à gauche (par exemple : si le résultat d'une colonne vaut 2, on pose 0 en bas de cette colonne et une retenue de 1 dans la colonne immédiatement à gauche, puisque "10" en base 2 correspond au nombre décimal 2).

Example 1 L'addition 10111 + 101 est exécutée en base 2 ci-dessous.

En base 10, l'opération mathématique correspondante est : 23 + 5 = 28.

Pour représenter les nombres négatifs, il suffit de réserver l'un des bits (par exemple le plus à gauche) pour coder le signe du nombre : par exemple la valeur 0 de ce bit signifie que le nombre est positif, 1 que le nombre est négatif (pour le nombre 0, la valeur de ce bit est alors indifférente : 0 a donc dans ce cas deux représentations différentes possibles). Mais ce codage rend délicat les calculs avec les nombres négatifs. D'autres codages plus astucieux (que nous ne détaillerons pas ici) permettent de réaliser des opérations mathématiques aussi simplement avec les nombres négatifs qu'avec les nombres positifs.

Pour un nombre donné, le codage en base 2 occupe plus de place que le codage décimal (c'est naturel puisque, en revanche, il utilise moins de symboles distincts de base). Pour maîtriser l'espace mémoire nécessaire au codage des nombres, un nombre fixe de bits est réservé pour toute donnée de type "nombre entier". Si, lors d'un calcul avec des nombres entiers, cet espace est insuffisant (à cause des retenues), alors le résultat annoncé du calcul sera faux (c'est le même problème que pour le "bogue de l'an 2000").

Ainsi, même dans les dernières versions de Turbo Pascal (un environnement de programmation pour le langage Pascal encore en usage), deux octets étaient réservés pour tout nombre entier. Or 2 octets ne permettent que 2¹⁶ = 65 536 combinaisons différentes de 0/1. Concrètement, cela signifie que les seuls nombres entiers relatifs qui peuvent être représentés sont ceux compris entre −32 768 et 32 767. Cette limite va donner lieu à des erreurs dès que ces bornes sont dépassées dans un calcul.

2.4 Grands nombres et nombres décimaux

Pour coder les grands nombres sans risquer les erreurs précédentes, et pour coder les nombres décimaux (c'est-à-dire avec une virgule), la méthode adoptée s'appelle "représentation en virgule flottante". Son principe est de normaliser l'écriture de ces nombres, en jouant sur les puissances de la base, et de coder indépendamment la partie "exposant" et la partie "mantisse" du résultat.

Example 2 En base 10, on peut écrire :

27 000 000 = 0,27.10⁹
0,000027=0,27.10⁻⁴

Tout nombre en base 10 peut ainsi s'écrire sous la forme d'un nombre décimal commençant par 0,... suivi de ce qui s'appelle la "mantisse", qui contient les chiffres significatifs du nombre (et commence donc toujours par un chiffre différent de 0) et multiplié par une certaine puissance entière de 10 (éventuellement négative). Le principe est exactement le même si la base de la numérotation est 2.

Par exemple le nombre 27 en base 2 peut s'écrire :

11011=0,11011.2¹⁰¹, où 11011 est la mantisse et 101 (qui vaut 5 en base 10) est l'exposant.

Dans la représentation en virgule flottante, un espace mémoire est réservé pour coder la mantisse, et un autre est réservé pour coder la valeur de la puissance. Un nombre trop grand pour être codé de façon traditionnelle sur deux octets peut être codé correctement avec ce système.

La représentation en virgule flottante n'exclut pourtant pas tout risque d'erreur : pour un nombre très grand avec beaucoup de chiffres significatifs, l'ordre de grandeur du nombre sera conservé (grâce au codage de l'exposant) mais le détail des décimales peut être perdu. De même un nombre très proche de 0, dont l'exposant est très grand en valeur absolue et négatif peut ne pas être représenté correctement : tout ordinateur a sa limite en terme de représentation des nombres (pour les petits nombres, on parle de "epsilon machine").

Les nombres décimaux qui s'écrivent avec un nombre infini non périodique de chiffres après la virgule (par exemple : π) n'appartiennent pas au monde du "discret" : les coder avec des 0/1 impose donc une part d'approximation irrémédiable. Les "erreurs d'arrondis" sont une conséquence directe et inévitable du codage des nombres réels à l'aide de symboles discrets.

2.5 Les tableaux

Les tableaux, utiles dans les tableurs ou les bases de données, peuvent être eux aussi codés à l'aide de 0/1. Imaginons par exemple que nous souhaitions coder le tableau suivant, qui ne contient que des nombres entiers :

12	5	-3	0	-1
-15	7	2	0	5
-8	-2	0	1	2

Pour représenter un tel tableau, il suffit par exemple :

de repérer le nombre de lignes et le nombre de colonnes du tableau ;
de fixer un nombre de bits permettant de coder à la fois le nombre de lignes et de colonnes et chacune des données présentes dans une case du tableau ;
de coder successivement chacune de ces données dans une longue chaîne de 0/1.

Dans notre exemple, le tableau a 3 lignes et 5 colonnes, et tous les nombres qu'il contient sont inférieurs à 16=2⁴ en valeur absolue. Chacune de ces données peut donc être codée sur 5 bits (le premier bit servira pour le signe). En codant successivement le nombre de lignes puis le nombre de colonnes et enfin chaque case lue de gauche à droite et de haut en bas, on obtient la chaîne suivante (pour faciliter la lecture, on laisse un espace entre chaque donnée distincte) :

00011 00101 01100 00101 10011 00000 10001 11111 00111 00010 00000 00101 11000 10010 00000 00001 00010

A partir de cette chaîne, et à condition bien sûr de connaître les conventions de codage, on peut entièrement reconstituer le tableau initial.

De même, on peut aussi coder un tableau de données discrètes hétérogènes (par exemple : dont certaines cases contiennent un nombre et d'autres cases un ou des caractères). Dans ce cas, il faut prévoir d'inclure dans le codage quelques bits qui signalent, pour chaque case, la nature de la donnée qu'elle contient. Par exemple, si chaque case ne peut contenir qu'un nombre ou qu'un caractère, il suffit de le signaler par un bit supplémentaire (valant 0 pour "caractère" et 1 pour "nombre") associé à chaque case, indiquant comment interpréter les bits suivants.

Les bases de données et les logiciels documentaires sont essentiellement constituées de tableaux de données hétérogènes, constituant ce que nous avons appelé dans la figure 2.1 des "données factuelles". Par exemple, le catalogue (simplifié) d'une bibliothèque peut avoir la forme du tableau de la figure 2.4, dans lequel chaque colonne est d'un type particulier. Dans notre exemple, les trois premières colonnes seraient de type "chaîne de caractères" (il faudrait préciser pour chacune le nombre de caractères maximum qu'elle peut contenir), la dernière étant de type "nombre entier".

titre de livre disponible nom auteur prénom auteur date parution

Mme Bovary Flaubert Gustave 1857

Notre Dame de Paris Hugo Victor 1831

Les misérables Hugo Victor 1862

... ... ... ...

Figure 2.4: début d'un catalogue simplifié de bibliothèque

2.6 Codage des sons

Les sons semblent être de nature différente des symboles et des nombres. On va en fait montrer comment un son, via une part d'approximation, peut se ramener à une suite de nombres. Un son peut (très schématiquement) se représenter par une courbe exprimant son amplitude en fonction du temps, comme sur la figure 2.5.

Figure 2.5: courbe sonore continue

Un son réel est en fait une superposition de courbes de ce genre, mais l'oreille humaine n'est pas sensible à toutes les "harmoniques" qu'il contient. Le principe du fameux format de codage appelé MP3 est, précisément, de ne coder que la partie du son que les sens humains perçoivent.

Pour coder une telle courbe continue en bits, il est nécessaire de la discrétiser, c'est-à-dire de transformer les paramètres qui la définissent (le temps et l'amplitude), qui varient suivant des échelles continues, en paramètres discrets ne pouvant prendre qu'un nombre fixé de valeurs distinctes. On peut décomposer ce processus en deux étapes :

on discrétise le temps, en abscisse, en procédant à un échantillonnage : le temps est "découpé en morceaux" à intervalles réguliers. On appelle fréquence d'échantillonnage le nombre d'intervalles découpés par seconde (ainsi, doubler la fréquence d'échantillonnage revient à multiplier par deux le nombre de morceaux découpés, c'est-à-dire à diviser par deux la largeur de chaque morceau) ;
on discrétise l'amplitude en approchant la courbe par un nombre : pour chaque intervalle de temps, on prend le nombre qui permet de "s'approcher le plus possible" de la courbe réelle.

En appliquant ce traitement à la courbe de la figure 2.5, avec une fréquence d'échantillonnage de 1 unité par seconde et en n'acceptant que des valeurs entières pour l'amplitude, on obtient la nouvelle courbe de la figure 2.6.

Figure 2.6: courbe sonore discrétisée

Pour coder cette courbe, il suffit maintenant de coder successivement les valeurs correspondant à chaque morceau de temps. Dans notre exemple, ces valeurs successives sont approximativement : 4, 7, 11, 11, 7, 3, 2 6, 11, 12. A condition de connaître la fréquence d'échantillonnage, la donnée de ces nombres suffit à reconstruire la courbe discrétisée, et donc à reconstituer les variations du son initial.

Sur notre exemple, l'approximation semble grossière, mais en prenant une fréquence d'échantillonnage très grande et un codage des nombres permettant une grande précision pour les réels, la courbe discrète suit de si près la courbe réelle que le son y est parfaitement retranscrit. Dans un CD-audio haute fidélité, par exemple, la fréquence d'échantillonnage est de 44 100 échantillons par seconde. Le nombre de bits occupés par un CD-audio usuel (non codé en MP3) est d'environ 500 Mega octets.

2.7 Codage des images

Il y a plusieurs manières de coder une image, de la "discrétiser". On distingue principalement deux formats de codage, chacun étant adapté à un type d'image particulier et à un usage particulier.

Le codage "bit map"

Ce codage est utilisé pour numériser des images existantes (photos, reproductions de peintures...). Il est donc plutôt adapté à l'analyse et au traitement des images. Son principe est celui du quadrillage : l'image est découpée à travers une grille au maillage plus ou moins fin, suivant des lignes horizontales et verticales. Cette grille découpe donc l'image en petits éléments rectangulaires appelés "pixels" (par contraction de l'anglais picture element). On appelle définition d'une image numérique le nombre de pixels qu'elle contient par unité d'espace, donc par cm². Cette définition est d'autant plus grande que la grille est fine, et donc que les pixels sont petits. Pour coder une image ainsi découpée, il suffit maintenant d'associer à chaque pixel sa couleur dominante, et de coder les couleurs des pixels les unes après les autres, dans un ordre fixé à l'avance (par exemple de haut en bas et de gauche à droite).

Les codages des couleurs les plus courants sont les suivants :
- le codage en noir et blanc pur : un bit suffit alors pour coder un pixel, suivant une association arbitraire (par exemple : 0 pour blanc et 1 pour noir) ;
- le codage en 256 couleurs (ou 256 niveaux de gris) : le spectre des couleurs (ou des niveaux de gris) est découpé en 256, et un code arbitraire sur un octet est associé à chacune des nuances (rappel : 1 octet = 8 bits et permet donc de coder 2⁸ = 256 couleurs différentes possibles)
- le codage en 16 millions de couleurs : ce codage, aussi appelé RGB (pour Red, Green, Blue), utilise la décomposition des couleurs à l'aide des 3 couleurs primaires (rouge, vert et bleu), comme pour les écrans de télévision. Rappelons qu'additionner des faisceaux lumineux tend à les éclaircir (puisque le blanc est la somme de toutes les couleurs) ; les règles d'addition des rayons lumineux ne sont donc pas les mêmes que celles des additions des couches de peinture... La contribution de chaque couleur primaire à la définition d'une certaine couleur est alors codée sur 1 octet, ce qui nécessite donc 3 octets pour coder chaque pixel. Dans ce cas, le premier octet code la contribution du rouge à la couleur du pixel, le deuxième la contribution du vert et le troisième celle du bleu (or 2^8*3 vaut environ 16 millions, donc il y a bien 16 millions de couleurs différentes qui peuvent être codées par ce système).
Lorsqu'on numérise une image à l'aide d'un scanner, il faut préciser la définition de l'image et le codage des couleurs souhaité ; ces 2 paramètres conditionnent fortement l'espace mémoire nécessaire au codage de l'image. Le codage d'une image "bit map" à haute définition et à l'aide de couleurs fines nécessite un grand nombre de bits. La figure 2.7 montre la même image bit map à deux échelles différentes, pour illustrer l'importance de la définition dans l'impression globale rendue par une telle image. Les images bit map sont souvent ce qui occupe le plus de place dans la mémoire des ordinateurs...

Figure 2.7: images bits map
Le codage vectoriel

Ce codage sert principalement à la synthèse d'images. Il est particulièrement bien adapté aux images qui se présentent sous la forme de schémas ou de plans. Il y en a plusieurs variantes, suivant que l'image à créer doit être vue en 2 ou en 3 dimensions.
- images en 2D
  
  Le codage vectoriel en 2D considère qu'une image est une combinaison de figures géométriques standards : ellipses, droites, rectangles, flèches... Un code arbitraire peut être associé à chacune de ces figures (il y en a un nombre fini). Par ailleurs, l'espace du dessin est repéré par un système de coordonnées classiques, désignées habituellement par X et Y. Pour repérer une figure particulière dans un dessin, il suffit de connaître :
  - sa nature (par exemple : un rectangle) déterminée par son code ;
  - les coordonnées (X, Y) de deux points extrêmes qui permettent de le situer sans ambiguïté dans l'espace (pour un rectangle : son coin supérieur gauche et son coin inférieur droit) ;
  - son éventuelle couleur de trait et de remplissage (repérée comme pour les images bit map).
  Contentons-nous ici de dessins "au crayon", sans tenir compte des couleurs. Imaginons par exemple que les codes des figures standards soient les suivants :
  - ellipse : 000 ;
  - rectangle : 001 ;
  - ligne continue : 010 ...
  et que l'on veuille coder le dessin de la figure 2.8.
  
  Figure 2.8: dessin vectoriel
  
  Les coordonnées (supposées entières) des points extrêmes peuvent aussi être codées sur 3 bits. Chaque figure élémentaire est alors représentée par 5 groupes de 3 bits chacun. Par exemple, l'ellipse de la figure 2.8 est codée par : 000 001 100 101 001. Dans ce code, le premier groupe de 3 bit est le code de la figure ellipse, les deux suivants codent les nombres 1 et 4, qui sont les coordonnées (X,Y) du point qui circonscrit cette ellipse en haut à gauche, les deux derniers codent les nombres 5 et 1 qui sont les coordonnées (X,Y) du point qui la circonscrit en bas à droite. Le dessin complet se code par la succession des codes des figures élémentaires (dans un ordre quelconque) qui le composent, soit par exemple :
  
  D'autres codes représentant la couleur de trait et de remplissage de chaque figure élémentaires, l'ordre de superposition de ces figures, etc. devraient être ajoutés à cette suite.
  
  Le codage vectoriel 2D est celui qui est exploité par les logiciels de dessin usuels comme PaintBrush, et il permet de faire subir simplement les transformations géométriques classiques (translations, rotations, symétries, homothéties...) aux images.
  
  Il est très économe en espace mémoire, et c'est aussi la raison pour laquelle il est utilisé pour créer des animations sur Internet avec la technologie "Flash".
- images en 3D
  
  Le principe de ce codage est exactement le même que le précédent, sauf que les primitives graphiques utilisées sont des volumes (sphères, cylindres, parallélépipèdes...) au lieu d'être des figures de la géométrie plane.
  
  C'est lui qui est utilisé dans les logiciels de CAO (Conception Assisté par Ordinateur), de réalité virtuelle, ou pour les effets spéciaux numériques dans les films... Il nécessite un effort de modélisation considérable pour représenter un environnement complet uniquement à partir de primitives, mais permet ensuite des applications spectaculaires en simulant les intéractions opérant dans cet environnement. Plus la modélisation est fine, plus la capacité de mémoire et de calcul nécessaire est importante.

2.8 Codage numérique et codage analogique

En résumé, les données manipulées par les ordinateurs sont exclusivement des données discrètes. Le monde du discret, dans lequel on peut énumérer chaque entité distincte les unes après les autres s'oppose au monde du continu, dans lequel ce n'est pas possible. Mathématiquement, un ensemble est discret s'il peut être mis en bijection avec N ou une partie de N, il est continu s'il peut être mis en bijection avec l'ensemble des nombres réels R, ou un de ses intervalles. Dans R, contrairement à N, on ne peut pas “compter”, c'est-à-dire énumérer tous ses éléments les uns après les autres sans en oublier aucun. Une autre manière de caractériser les données discrètes est précisément leur caractère codable à l'aide d'un alphabet fini (par exemple 0/1). On parle aussi de codage numérique (0 et 1 sont des nombres), mais cela ne signifie pas, nous l'avons vu, qu'il ne code que les nombres.

Les caractères alphanumériques et les nombres entiers appartiennent naturellement au monde du discret, et leur codage numérique ne pose donc pas de problème. En effet, quand il s'agit de traiter des données de nature discrète à l'aide d'un autre dispositif discret, le codage/décodage est exact, c'est-à-dire qu'il préserve toute l'information. En revanche, les nombres réels, les sons et les images appartiennent au monde du continu. C'est pourquoi jusqu'à l'émergence de l'informatique multimédia, leur codage passait plutôt par un mode analogique : un tel code traduit des données continues à l'aide d'un autre dispositif lui aussi continu. Par exemple, dans les anciens disques en vinyle et les anciennes cassettes audio, le son était codé et restitué grâce à un sillon continu, dont la forme reproduisait (par une relation "d'analogie") la courbe des sons. La radio FM et la télévision hertzienne actuelles sont encore transmises à l'aide d'ondes continues dont les variations (les "modulations") traduisent suivant une échelle continue les variations du son. Les photographies “argentiques” sont réalisées à l'aide d'une surface (quasi) continue de produit chimique réactif qui restitue le continuum de nuances du spectre des couleurs. Les anciennes cassettes vidéo reproduisaient ainsi, une par une, les images d'un film sur leur bande.

Le codage numérique, lui, n'a droit qu'aux symboles 0 et 1. Pour coder numériquement des données continues, il faut donc passer par une phase de discrétisation ou numérisation, qui se paie par une part d'approximation. La qualité du son des CD-audio est néanmoins supérieure à celle des anciens disques "33 tours", et la définition des photographies numériques s'approche à grands pas de la précision des photographies traditionnelles.

2.9 Codages/décodages et changements de codes

L'échange de données entre matériels fonctionnant sous un mode numérique ou analogique impose parfois de passer par des phases de numérisation. Les plus courants de ces dispositifs sont les suivants :

les modems (contraction de "modulateur"/"démodulateur") sont des appareils qui transforment des données discrètes sous forme de bits en données analogiques pouvant circuler sur les lignes téléphoniques (et réciproquement). Il sont donc indispensables pour relier les ordinateurs entre eux en passant par le réseau téléphonique français (qui, lui, transmet des données continues). Les boîtiers fournis pour se connecter à l'Internet haut débit (freebox, livebox et autres) en sont les versions améliorées. L'ADSL est en effet simplement une technologie qui emploie pour transmettre ses données des fréquences non utilisées par la voie humaine dans les conversations téléphoniques. C'est pourquoi on peut à la fois téléphoner et envoyer/recevoir des données en passant pas la même ligne téléphonique avec ces boîtiers.
les scanners ou numériseurs, transforment des images quelconques (textes ou photos) en suites de bits codant ces images sous forme "bit map".

Par ailleurs, les différents types de données étant, comme nous l'avons vu, codés de façon spécifiques, il peut parfois être nécessaire de passer d'un mode de codage à un autre. C'est ce que réalisent des logiciels comme :

les Optical Character Recognizer (OCR) sont des programmes qui transforment les images sous forme "bit map" d'un texte en une suite de caractères ASCII. Il peuvent aussi reconnaître la mise en page du texte et la traduire dans les codes spécifiques utilisés pour les représenter dans les traitements de textes. Ils sont indispensables si on veut "traiter" avec un éditeur ou un traitement de textes un fichier (2.4) issu de la numérisation d'un texte écrit.
les vectoriseurs d'images transforment les dessins sous forme "bit map" en images vectorielles. Ils sont utilisés pour traiter des plans techniques ou des dessins d'architectes.

De manière générale, tout logiciel qui permet de manipuler des données de natures différentes (par exemple, des caractères et des nombres) accorde un rôle primordial à la notion de typage ou de format. Connaître le type d'une donnée, en effet, est indispensable pour savoir comment interpréter la suite de 0/1 qui la code.

Enfin, certains codages sont plus économiques que d'autres, au sens où ils nécessitent de réserver un plus ou moins grand nombre de bits pour coder une même donnée. Les logiciels de compression de données ont pour objectif de réduire au maximum l'espace mémoire occupé par le codage d'un certain type de données. Les stratégies qu'ils mettent en oeuvre varient évidemment suivant la nature des données, et donc des codages, qu'ils ont à traiter, et suivant que la compression visée est exacte ou approchée (c'est-à-dire si elle préserve ou non toute l'information présente ou pas). Par exemple, pour compresser l'image "bit map" d'un texte, on peut commencer par coder de façon vectorielle les espaces blancs de la page. Pour le codage d'une scène vidéo (correspondant à une succession d'images "bit map"), on peut se contenter de coder complètement la première image, puis seulement la différence entre chaque image et la précédente...

On comprend mieux, à l'issue de ce passage en revue de tous les codages utilisés en informatique, la puissance du monde numérique : elle vient de la capacité à stocker et à échanger des informations de nature très variées sur un seul support, sous forme de bits. La distinction élémentaire, abstraite, entre deux états possibles de n'importe quel dispositif permet une combinatoire suffisante pour apparemment tout "coder". Loin d'être limitée, cette stratégie a rendu possible l'apparition du multimédia (qui associe textes, sons et images) dans les CD-Rom ou l'Internet et donné naissance aux "autoroutes de l'information".

2.10 En guise de conclusion : le monde est-il discret ou continu ?

A la fin du siècle dernier, le mathématicien allemand d'origine russe Georg Cantor a démontré que l'ensemble infini (et discret) des nombres entiers N est fondamentalement moins "puissant" que l'ensemble infini (et continu) des nombres réels R, c'est-à-dire qu'il est impossible de définir une bijection entre ces deux ensembles. Il existe en quelque sorte plusieurs niveaux d'infinis.

Notre monde physique, lui, est-il discret ou continu ? La réponse n'a rien d'évident. Les physiciens ont tendance à écrire et à manipuler des équations dont les variables parcourent un espace continu et dont les fonctions sont aussi continues. Le temps, par rapport auquel ils dérivent souvent les autres fonctions, est ainsi généralement considéré comme continu. Pour eux, le discret est plutôt conçu comme une approximation du continu. Pourtant, la notion de "particule élémentaire" laisse penser à une nature discrète des éléments constituant l'univers. Mais la physique quantique a aussi découvert que particules (discrètes) et ondes (continues) ne sont que les deux aspects d'une même réalité, ce qui ne contribue pas à simplifier les choses.

Il y a pourtant au moins deux domaines naturels fondamentaux dans lesquels le mode numérique a prévalu sur le mode analogique :

le code génétique : le patrimoine génétique de tous les êtres vivants est codé non pas à l'aide de 0/1 mais sur l'alphabet à quatre lettres des bases chimiques notées A, T, C et G. C'est donc un codage discret en base 4 ;
les langues humaines : elles sont toutes constituées, à chacun de leur niveaux (les sons élémentaires utilisés par une langue donnée ou phonèmes, les mots, les règles de grammaires...), d'une combinatoire d'éléments discrets.

Ces deux domaines sont ceux qui permettent la transmission d'information (génétiques ou culturelles) d'une génération à une autre. Si la nature a sélectionné des mécanismes discrets pour réaliser cette transmission, c'est sans doute que le codage numérique a de meilleures propriétés que le codage analogique. L'exercice 1 (énoncé en 1.1, corrigé en 2.1) donne quelques éléments pour comprendre comment la transmission de données discrètes peut être rendue robuste par des mécanismes d'auto-correction.

Par ailleurs, ce n'est évidemment pas un hasard si l'informatique est de plus en plus utilisé pour aider l'expertise humaine dans ces domaines, puisque le codage peut y être exact...

3 Traitements effectifs

La représentation binaire des nombres était connue bien avant l'apparition des ordinateurs ; elle fut inventée dès le XVIème siècle par Francis Bacon, et fut utilisée par Leibniz au XVIIème siècle. Evidemment, le codage numérique des autres types de données (caractères, images, sons...) ne s'est généralisé que récemment, mais les principes qu'il met en oeuvre ne sont pas fondamentalement difficiles. Ce qui, en revanche, a signé l'acte de naissance de l'informatique, c'est l'explicitation de la notion de traitement effectif, ou encore de procédure de calcul ou d'algorithme (par la suite, ces termes seront utilisés comme des synonymes), qui permet de décrire ce que réalise un ordinateur sur les données qu'on lui fournit. Nous avons montré comment l'on pouvait ramener la diversité des données à des composants élémentaires. Nous allons maintenant voir que l'on peut aussi ramener la variété des traitements réalisables par les ordinateurs à une combinatoire de traitements élémentaires.

3.1 Préhistoire des algorithmes

Qu'est-ce qu'un algorithme ? En première approximation, c'est une méthode systématique définie étape par étape et permettant de résoudre à coup sûr et en un nombre fini d'étapes une certaine classe de problèmes ou de répondre à une certaine classe de questions. Chacune de ces caractéristiques va bien sûr devoir être explicitée. De telles méthodes ont été découvertes bien avant l'apparition de l'informatique et sont connues depuis longtemps par les mathématiciens. L'enseignement des mathématiques passe d'ailleurs par l'apprentissage de nombreux algorithmes : par exemple, comment réaliser une opération élémentaire (addition, multiplication, etc.) sur 2 nombres, entiers ou décimaux, comment résoudre une équation, etc.

Partons du problème suivant, un peu plus difficile : comment savoir si un certain nombre entier n (n'importe lequel) est un nombre premier, c'est-à-dire s'il n'admet aucun autre diviseurs que lui-même et 1 ? Pour le savoir, on peut adopter la stratégie suivante :

essayer de diviser n par 2 :
⇒ si la division est juste (le reste est nul), alors n est divisible par 2 : n n'est pas premier
sinon, essayer de diviser n par 3 :
⇒ si la division est juste (le reste est nul), alors n est divisible par 3 : n n'est pas premier
... essayer de diviser n par... (essayer tous les nombres jusqu'à n−1) :
⇒ si au moins une division est juste : n n'est pas premier
⇒ si aucune division n'est juste : n est premier

Cette stratégie est très élémentaire (il en existe de bien plus efficaces : par exemple, on peut s'arrêter quand on dépasse √n), mais elle assure :

de toujours savoir ce qu'il faut faire pour obtenir la réponse ;
de fonctionner quel que soit le nombre entier n de départ : elle répond bien à une classe de questions (comme "un nombre entier quelconque est-il premier ?") et non à une question particulière (comme "le nombre 31 457 est-il premier ?") ;
de demander un nombre fini de calculs (qui dépendra néanmoins du nombre n que l'on teste) et de donner toujours une réponse correcte, qu'elle soit positive ou négative.

Un algorithme peut aussi être vu comme la réalisation concrète d'une certaine fonction : dans notre exemple, c'est la fonction f qui à chaque nombre entier associe la réponse "oui" ou "non" suivant que ce nombre est premier ou non. On peut coder cette réponse par 0 ou 1 (0 signifie "non", 1 signifie "oui"). Le nombre n à tester est la donnée d'entrée, tandis que la réponse finale est la donnée de sortie de l'algorithme. On peut donc représenter cette fonction ainsi :

f :	N—→{0,1}
	n ⊢→ f(n)

Notre exemple illustre aussi qu'un algorithme est défini à l'aide d'instructions élémentaires (comme de savoir faire une division), de tests (vérifier si le reste de cette division est nul ou non) et d'une structure définie par la façon et l'ordre dans lesquels il s'enchaînent.

Un des plus anciens algorithmes intéressants connus (légèrement plus compliqué que celui de l'exemple), appelé "algorithme d'Euclide" et datant environ de 300 avant J.C., permet de répondre à la classe de questions suivante : comment savoir si deux nombres entiers quelconques sont premiers entre eux (c'est-à-dire s'ils ont un diviseur commun) ?

Le mot "algorithme", lui, a été créé à partir du nom de Al Khowarizmi, mathématicien persan du IXème siècle, connu pour être l'auteur en 825 d'un traité d'arithmétique où il transmettait aux arabes des algorithmes de calculs connus des indiens et utilisant la numérotation de position.

La notion d'algorithme existe donc depuis longtemps. Mais la nécessité de lui donner un contenu, une définition mathématique précise n'a émergé que très tardivement, pour répondre à des interrogations plus générales.

3.2 Les problèmes de Hilbert

L'histoire contemporaine des algorithmes commence en 1900. Cette année-là, a lieu à Paris le grand congrès de la société des mathématiciens. L'invité d'honneur y est David Hilbert, très grand mathématicien allemand de l'époque. Pour faire honneur à la date de la conférence, il choisit de se livrer à l'exercice périlleux de la prospective, en proposant une liste de problèmes fondamentaux qui, selon lui, vont dominer les mathématiques du XXème siècle : ce sont les désormais célèbres "23 problèmes de Hilbert". Il n'est bien sûr pas question de tous les exposer ici, mais il suffit de savoir qu'ils ont effectivement recensé une bonne partie des recherches mathématiques à venir.

Celui qui nous intéresse particulièrement porte le numéro 10, et il s'énonce de la façon suivante : "Existe-t-il une méthode pour résoudre n'importe quelle équation diophantienne ?". Une équation diophantienne s'exprime sous la forme d'un polynôme dont les coefficients sont des nombres entiers et dont on cherche les racines entières.

Example 3 Quelques exemples d'equations diophantiennes :

chercher les valeurs entières de x telles que : 3x²−5x+1 = 0
chercher les valeurs entières de x et y telles que : 6xy²−y+7x = 0

Dans certains cas particuliers (comme dans le premier exemple), on sait résoudre le problème, mais dans la plupart des autres aucune méthode générale, aucun algorithme, n'est connu et on commence à soupçonner qu'il n'en existe peut-être pas. Or les mathématiciens savent depuis longtemps démontrer qu'une certaine stratégie, une certaine méthode de calcul qu'ils ont inventée est juste et aboutira toujours au résultat souhaité, mais comment démontrer qu'il n'en existe aucune pour répondre à un problème donné ? Comment être sûr d'avoir testé toutes les méthodes possibles si on ne fait pas de cette notion de "méthode" elle-même un objet mathématique sur lequel il sera possible de faire des raisonnements et des démonstrations ? C'est l'enjeu de la formalisation de la notion d'algorithme, qui va se préciser au fil des ans.

Ainsi en 1928, à Bologne, Hilbert, de nouveau invité au congrès des mathématiciens (qui a lieu tous les quatre ans jusqu'à aujourd'hui), précise les objectifs de sa recherche, de son "programme". A cette époque, il espère fonder les mathématiques (qui ont traversé au début du XXème siècle une "crise des fondements" due à la découverte de paradoxes dans certaines théories) à l'aide de la logique, alors en plein essor. Sans entrer dans les détails, la logique est un langage permettant d'exprimer des énoncés mathématiques et de démontrer qu'ils sont vrais ou faux. Mais pour lui faire jouer un tel rôle, il faut s'assurer qu'elle-même est "bien fondée", c'est-à-dire qu'elle est consistante (elle ne permet pas d'aboutir à des contradictions) et complète (toute formule logique doit être soit vraie soit fausse). Il serait bon aussi qu'elle soit décidable, c'est-à-dire qu'il existe une procédure effective permettant de savoir si une formule logique donnée quelconque est vraie ou fausse ; c'est ce que Hilbert appelle le "Entcheidungsproblem" ou "problème de la décision".

Malheureusement pour Hilbert, le logicien autrichien Kurt Gödel démontre en 1929 et surtout 1931 dans un article devenu très célèbre que si la logique élémentaire est effectivement complète, tout langage assez puissant pour fonder l'arithmétique est, lui, nécessairement incomplet, et que sa consistance est indémontrable. Le "programme de Hilbert" est plutôt mal parti. Reste le problème de la décision, qui ne trouvera sa solution, négative, qu'en 1936. Pour y parvenir, il a en effet fallu définir précisément ce qu'est une procédure effective et montrer qu'aucune d'entre elles ne peut résoudre ce problème. C'est ce qu'est parvenu à faire Alan Turing, auteur de l'article qui met fin à l'Entcheidungsproblem.

3.3 La machine de Turing

En 1936, Alan Turing a 24 ans. C'est un jeune et brillant étudiant en mathématiques à Cambridge, en Angleterre. Son professeur de logique a assisté à la conférence de Hilbert à Bologne, et lui-même est fasciné par la capacité humaine de raisonner et de faire des calculs. Plus tard, il cherchera à construire un "cerveau artificiel".

Dans son article de 1936, il propose tout d'abord de formaliser la notion d'algorithme grâce à la définition d'un dispositif abstrait que depuis on appelle "machine de Turing". Il montre ensuite qu'aucun de ces dispositifs ne sera jamais capable de décider si une formule logique quelconque est vraie ou fausse. La "machine de Turing" est le modèle de base qui fonde l'informatique, nous allons donc détailler sa construction et son fonctionnement.

Pour introduire cette définition de façon intuitive, essayons de décomposer un calcul en "atomes" le plus élémentaires possible, en recensant tout ce qui est nécessaire à son exécution. L'objectif est de construire la machine la plus simple possible capable de réaliser n'importe lequel de ces calculs. Soit par exemple une multiplication entre deux nombres entiers : 25 * 13.

Pour réaliser une telle opération, il faut d'abord "poser le calcul", en général en l'écrivant sur une feuille de papier. De combien de papier a-t-on besoin ? On se restreint à des opérations portant uniquement sur des données discrètes. Par définition, elles peuvent donc être codées à l'aide d'un alphabet fini : 0 et 1 par exemple ! Les deux dimensions de la feuille de papier ne sont pas fondamentales : il suffit donc de disposer d'un ruban de papier séparé en cases, chaque case pouvant contenir soit le symbole 0, soit le symbole 1, soit rester vide (caractère noté B pour "blanc", et servant à séparer les différentes données). Les données de notre multiplication peuvent ainsi être "posées" de la façon suivante :

L'accès à ces données se fait par le biais d'une tête de lecture/écriture qui a le droit de parcourir le ruban case par case, un peu comme dans un magnétophone ou un magnétoscope. Nous la notons par une flèche sous la case du ruban qui est en train d'être lue (dans le dessin précédent, la tête se trouvait en train de lire la première case). C'est l'équivalent de la pointe du crayon avec lequel on écrit quand on effectue le calcul à la main.

Pour la suite des calculs, nous aurons besoin de poser d'autres données correspondant à des résultats intermédiaires. De même qu'on peut toujours disposer d'une nouvelle feuille de brouillon, on doit toujours pouvoir disposer de cases libres sur le ruban : nous supposons donc que celui-ci est infini vers la droite (et contenant initialement, à l'infini, des cases notées B).

Le deuxième composant fondamental d'une machine de Turing est la notion d'état. En effet, pour réaliser notre multiplication, nous devons passer par plusieurs phases, plusieurs étapes au cours desquelles l'opération réalisée est différente. Chacune suppose en quelque sorte un état d'esprit différent. Dans notre exemple, au moins deux phases successives sont nécessaires :

une phase de multiplications élémentaires entre chiffres : 3 * 5 puis 3 * 2 puis 1 * 5 puis 1 * 2 ;
une phase d'additions élémentaires entre les résultats de la phase précédente.

De même, une machine de Turing disposera d'un ensemble fini d'états distincts, que par la suite nous repérerons par des nombres disposés les uns à la suite des autres dans un tableau. A chaque instant un et un seul de ces état est "actif" et on l'appelle "état courant" : c'est celui dans lequel se trouve la machine à cet instant-là. La machine peut passer de n'importe quel état à n'importe quel autre à chaque étape du calcul. Enfin, un état particulier appelé "état final" et noté F correspondra à l'état dans lequel se trouve la machine à la fin de son calcul. Il signifie l'arrêt de son fonctionnement. Ainsi, si une machine a trois états possibles (plus F) et se trouve en ce moment dans l'état 2, nous notons :

L'état courant est repéré par un cercle. La machine commence toujours en partant de l'état initial noté 1, et s'arrête dès qu'elle atteint l'état F.

On appelle configuration d'une machine de Turing l'ensemble constitué par le symbole du ruban sur lequel pointe sa tête de lecture et l'état courant dans lequel elle se trouve. La machine donnée en exemple jusqu'à présent serait ainsi dans la configuration : (symbole lu : 1, état : 2). Réaliser un calcul avec un tel dispositif consiste, fondamentalement, à enchaîner des changements de configuration à partir des données de départ, pour aboutir à de nouvelles données.

Pour comprendre le fonctionnement d'une telle machine, reprenons notre exemple de multiplication. Chaque étape du calcul revient à écrire de nouveaux chiffres sur la feuille blanche en consultant (mentalement ou matériellement) une table de multiplication ou une table d'addition, suivant l'étape de calcul dans laquelle on se trouve.

De même, dans une machine de Turing, chaque instruction élémentaire revient simplement à substituer certains symboles à d'autres sur le ruban, en tenant compte des résultats intermédiaires qui y sont déjà écrits et de l'état courant de la machine, en consultant une table.

Pour une configuration donnée, c'est-à-dire :

le contenu de la case du ruban lue par la tête de lecture ;
l'état courant de la machine.

une instruction élémentaire sera, en effet, définie par 3 composantes :

le symbole écrit par la tête de lecture à la place de celui qu'elle a lu ;
le déplacement de la tête de lecture : soit une case vers la gauche (G) soit une case vers la droite (D) ;
le nouvel état courant du calcul.

La première et la troisième composante décrivent la nouvelle configuration de la machine, la deuxième composante est le déplacement minimal qui permet d'enchaîner les instructions élémentaires les unes après les autres. La liste des instructions élémentaires constituant un calcul complet peut donc bien figurer dans un tableau dont les deux paramètres d'entrée sont le symbole lu et l'état courant, et dont chaque case contient 3 symboles correspondant aux 3 composantes de chaque instruction.

En résumé, un calcul effectué par une telle machine commence une fois les données d'entrée écrites sur le ruban, la tête de lecture mise sous la première case du ruban et l'état 1 fixé comme état courant. Chaque étape du calcul consiste à chercher dans le tableau l'instruction à exécuter et à l'effectuer, jusqu'à temps que l'état courant soit l'état F. La donnée de sortie de l'algorithme, c'est-à-dire le résultat du calcul, doit alors être lisible sur le ruban.

3.4 Un exemple simple

La machine à multiplier les nombres (décimaux ou binaires) est malheureusement trop compliquée à écrire. Nous en prenons une beaucoup plus simple ici, celle réalisant la fonction suivante :

f :	N—→ N
	n ⊢→ n+1

Notre machine de Turing doit donc ajouter 1 à un nombre binaire quelconque, écrit sur son ruban, infini dans les deux sens (le fait que le ruban soit infini dans les deux sens est aussi choisi pour simplifier l'écriture de la machine). Dans cette machine, le résultat du calcul (le nombre initial + 1) va être écrit à la place de la donnée de départ sur le ruban. Son tableau est le suivant :

état courant \ symbole lu	0	1	B
1	0,D,1	1,D,1	B,G,2
2	1,D,F	0,G,2	1,D,F

Par exemple, la case qui se trouve à l'intersection de la colonne notée 1 et de la ligne notée 2 contient l'instruction qui doit être exécutée si la tête de lecture est en face d'une case du ruban contenant le symbole 1 et que la machine se trouve dans l'état 2 (on note les états en gras pour les distinguer des symboles écrits sur le ruban). Dans notre tableau, cette instruction est : 0,G,2. Ce code signifie que l'instruction consiste alors à écrire avec la tête de lecture/écriture le symbole 0 dans la case (à la place du 1), puis à déplacer cette tête d'une case vers la gauche sur le ruban, tandis que l'état courant de la machine reste l'état 2.

Pour vérifier l'exactitude de cette table, il suffit de la tester en écrivant sur le ruban un nombre binaire (positif) quelconque, en plaçant la tête de lecture sous la première case de ce nombre et en fixant l'état courant à 1, puis en exécutant systématiquement les instructions de la table. Quand l'état F est atteint, le nouveau nombre écrit sur le ruban doit être le nombre initial +1.

Prenons l'exemple du nombre n=5, et donc de l'addition suivante :

Example 4 Au début du calcul, le ruban contient le nombre 5, codé en binaire comme suit :

Et l'état courant est l'état 1 :

L'instruction à exécuter se lit à l'intersection de la colonne 1 (symbole lu par la tête de lecture) et de la ligne 1 (état courant) : c'est 1,D,1. Le symbole 1 du ruban est recopié, et la seule modification à effectuer est donc de déplacer la tête de lecture vers la droite (l'état courant restant aussi inchangé) ; la nouvelle configuration de la machine à l'issue de cette instruction est donc :

L'instruction suivante à exécuter est : 0,D,1, qui donne lieu à la situation :

Puis, il faut de nouveau exécuter 1,D,1, et on arrive à :

En fait, cette première série d'instructions n'a fait que parcourir le nombre en le recopiant : cette étape était nécessaire au repérage de la fin du nombre (par où commence l'addition). Cette fois, la tête de lecture pointe devant une case blanche ; l'instruction à exécuter est B,G,2, qui ne modifie toujours pas le contenu du ruban, mais change l'état courant :

L'addition va pouvoir commencer : l'instruction 0,G,2 réalise l'addition du dernier chiffre du nombre écrit sur la ruban avec 1.

Il reste néanmoins une retenue à propager vers la gauche. C'est ce que réalise l'instruction : 1,D,F, qui mène à la configuration finale :

L'état F étant atteint, le calcul s'arrête. Le ruban contient la suite de symbole 110 correspondant au nombre 6 en codage binaire, qui est bien le résultat de l'opération 5 + 1.

En fait, quel que soit le nombre écrit au départ sur le ruban, le résultat de l'exécution des instructions du tableau amènera à écrire ce nombre + 1 sur le ruban : la machine de Turing réalise donc bien une fonction, un algorithme.

Les instructions de la table peuvent aussi être représentées dans un graphe, c'est-à-dire un schéma constitué d'états (représentés par des ronds) et d'arcs étiquetés reliant ces états avec les conventions suivantes :

les états du graphe correspondent aux états possibles de la machine de Turing ;
une instruction est figurée par un arc reliant l'état de départ de l'instruction et l'état dans lequel elle mène, étiqueté par 3 symboles :
- le symbole lu dans la case par la tête ;
- le symbole écrit dans la case par la tête ;
- le déplacement de la tête.

Ainsi, les instructions de la machine précédente peuvent également être représentées par le graphe de la figure 2.9. En fait, la définition d'une machine de Turing est la donnée d'un ensemble de changements de configuration. La définition d'un tel changement requiert la donnée de 5 informations : la configuration initiale (2 informations), la configuration finale (2 informations) et le déplacement (à gauche ou à droite). Le tableau ou le graphe sont deux moyens possibles de représenter des ensembles de changements de configuration (attention, dans les 2 cas, les informations en sont pas données dans le même ordre).

Figure 2.9: graphe de la machine de Turing à ajouter +1

Les états de cette machine ont le sens suivant :

l'état 1 est simplement la lecture et la recopie de gauche à droite du nombre écrit sur le ruban, on le quitte quand on rencontre le premier symbole B, c'est-à-dire quand on atteint la fin du nombre ; en revenant une case à gauche, on se place devant le dernier chiffre du nombre ;
l'état 2 est celui dans lequel l'addition +1 s'effectue vraiment :
- si le nombre se termine par 0, il suffit de transformer le 0 final en 1 pour ajouter 1 à ce nombre, et de terminer le calcul en rejoignant l'état F ;
- si le nombre se termine par 1, alors le chiffre final devient 0 et il faut propager la retenue vers la gauche en restant dans l'état 2 ;
- si on rencontre un symbole blanc B, cela signifie que l'on a atteint le début du nombre en propageant la retenue vers la gauche, et qu'il suffit donc maintenant d'écrire cette retenue pour terminer le calcul en rejoignant l'état F.

3.5 La thèse de Church-Turing

Une machine de Turing est un dispositif très rudimentaire qui réalise une fonction, puisqu'il transforme des données figurant sur un ruban en de nouvelles données, elles aussi écrites sur le ruban. La machine fonctionne étape par étape, et s'arrête quand elle atteint l'état F. Elle réalise donc bien ce qui ressemble à notre première définition des algorithmes. Mais Turing va plus loin. Il affirme que tout algorithme peut être décrit de cette façon, à l'aide d'une machine qui s'arrête toujours. Cette affirmation est connue sous le nom de thèse de Church-Turing. Elle signifie en particulier que tous les traitements cités dans la dernière colonne du tableau 2.1 peuvent être exprimés par une certaine machine de Turing. On comprend mieux, maintenant, ce qui fait l'intérêt de cette definition. Mais cette "thèse" demande quelques justifications.

Tout d'abord, remarquons qu'il est facile de construire une machine de Turing qui ne s'arrête jamais, qui "boucle à l'infini" : il suffit par exemple que la seule instruction figurant dans le tableau, quel que soit le contenu de la case lue et quel que soit l'état courant, consiste à écrire 0 sur le ruban et à déplacer la tête de lecture vers la droite (sans changer d'état courant). Le ruban étant par définition infini vers la droite, l'exécution de cette machine sur un ruban contenant une donnée quelconque ne finira jamais. Or, un algorithme s'arrête toujours, il ne peut donc coïncider qu'avec celles des machines de Turing qui s'arrêtent aussi toujours.

Notons ensuite que c'est bien une thèse qui est énoncée, et non un théorème mathématique. Cette thèse est, par nature, indémontrable puisque la notion d'algorithme, avant elle, n'avait pas de définition mathématique précise à quoi on aurait pu comparer celle des machines de Turing. La thèse de Church-Turing pose donc en fait une définition : elle introduit un nouvel objet mathématique (les machines de Turing) pour caractériser formellement une notion intuitive ancienne (la notion d'algorithme). Nous verrons plus loin ce qui, à défaut de preuves, tient lieu d'arguments en sa faveur.

La paternité de cette thèse est partagée entre Turing et Church. Alonzo Church, en effet, était un logicien américain qui, la même année que Turing, en 1936, a proposé un autre formalisme mathématique (extrêmement différent de celui de Turing) permettant également de décrire la notion de procédure effective. Ce formalisme, appelé le lambda-calcul (que nous ne détaillerons pas ici), s'est révélé être équivalent à celui des machines de Turing : toute méthode de calcul pouvant être décrite avec l'un peut l'être avec l'autre. Il est donc naturel de les associer.

Enfin, comment se convaincre de la validité de cette thèse ? Elle est maintenant largement admise et de nombreux arguments plaident en sa faveur :

arguments intuitifs : en parlant d'états d'esprit et en partant de l'exemple d'un calcul simple (ce que Turing faisait déjà dans son article), nous avons essayé de favoriser l'intuition ; de façon générale personne n'a jamais pu exhiber une procédure de calcul réalisable par un esprit humain qu'une machine de Turing ne pourrait pas elle-même réaliser.
argument de l'extension des machines de Turing : les machines de Turing sont rudimentaires, et il est possible d'élargir leur définition pour permettre, par exemple :
- d'utiliser plus de symboles différents sur le ruban (par exemple l'ensemble des caractères alphanumériques) : mais nous avons vu qu'à l'aide de 0/1 on pouvait coder n'importe quel alphabet discret ;
- de déplacer la tête de lecture plus librement en " sautant " par dessus les cases : mais en sautant case par case on peut aller aussi loin que l'on veut ;
- de disposer d'un ruban infini dans les deux sens (ce que nous avons utilisé dans l'exemple, pour qu'il soit le plus simple possible), et même de plusieurs rubans en parallèle : mais un ruban infini vers la droite uniquement suffit pour tout calcul ;
- de donner le choix entre plusieurs instructions possibles dans chaque case du tableau et en choisissant au hasard celle qui doit être exécutée (on parle alors de machine "non déterministe") : mais, là encore, on n'augmente pas fondamentalement la capacité de calcul.
Pour chacune de ces extensions, il a été démontré qu'elle ne permettait pas de réaliser un calcul qui, sur une machine classique, aurait été impossible. Elles permettent sans doute parfois d'aller plus vite et donc d'aboutir plus rapidement au résultat de l'algorithme, mais jamais d'aboutir à un résultat différent.
argument des autres formalismes : depuis 1936, de nombreux autres modèles de calcul ont été proposés pour caractériser la notion d'algorithme (comme le lambda-calcul, déjà évoqué). Tous se sont révélés avoir une puissance de calcul exactement équivalente à celle des machines de Turing, qui tient donc toujours lieu de modèle de référence.

3.6 La notion de machine universelle

Une machine de Turing n'est pas un ordinateur. Chaque machine particulière représente un algorithme particulier, servant à résoudre un problème précis. Une machine de Turing est donc plutôt une méthode de calcul, un programme.

Mais définir une machine de Turing, c'est équivalent à définir le tableau d'instructions de cette machine. Chaque case d'un tel tableau contient un triplet de données discrètes, qui est lui-même une donnée discrète. Or, nous avons vu qu'un tableau de données peut être codé (cf. 2.5). Ainsi, une machine de Turing peut elle-même être codée par une suite de 0/1. Ce code peut à son tour être écrit sur un ruban et donc servir de donnée à une autre machine.

Turing a démontré que parmi les machines qui portent désormais son nom, il en existe certaines particulières qu'il a appelées des Machines Universelles et que nous noterons U. De telles machines sont caractérisées par le fait que quand, sur leur ruban, figure successivement :

le code d'une certaine machine de Turing, notée M ;
le code d'une certaine donnée d ;

Le résultat de l'exécution de U sur ces données est le même que celui qu'on aurait obtenu en exécutant les instructions de M sur la donnée d. Ainsi U(M, d)=M(d).

Une machine universelle est donc en quelque sorte capable de simuler le comportement de n'importe quelle autre machine, dont on lui fournit la description, sur n'importe quelle donnée, qu'on lui fournit également par ailleurs. Une telle machine est ainsi capable d'exécuter n'importe quel algorithme, pourvu qu'on lui en donne un code. Si vous êtres capable de "faire fonctionner" sur du papier une machine de Turing dont on vous fournit la description (sous la forme d'un tableau ou d'un graphe) et sur le ruban de laquelle on a mis une donnée de départ, c'est que vous êtes devenu vous-même une machine universelle !

Cette notion est essentielle car elle est au fondement aussi bien du côté matériel que du côté logiciel de l'informatique.

En effet, on peut dire qu'un ordinateur est une machine universelle : quels que soient les données et les programmes qu'on lui fournit, il est capable d'exécuter ces programmes sur ces données. Le principe de la machine universelle se retrouve aussi dans l'architecture interne des ordinateurs (que nous détaillerons par la suite). En particulier, l'idée qu'il n'y a pas de différence de nature entre une donnée et une instruction, puisque chacune peut être codée par une suite de 0/1, se retrouve dans la mémoire des ordinateurs actuels, qui contient indifféremment des données et des programmes.

De même, on peut aussi dire qu'un langage de programmation est une machine universelle : il permet d'associer un code, une représentation, à n'importe quelle donnée et à n'importe quelle instruction, et d'intégrer le tout dans un programme. Tout langage de programmation permet de programmer, et donc de simuler, n'importe quelle machine de Turing.

Les machines de Turing sont néanmoins des modèles théoriques, abstraits, dont les réalisations matérielles ou logicielles ne sont que des approximations. Les principales limitations des dispositifs concrets sont l'espace mémoire disponible et le temps de calcul. Ainsi, alors que les machines de Turing disposent d'un ruban infini, les ordinateurs actuels ont évidemment une capacité de stockage finie. De même, le temps de calcul des machines de Turing réalisant un algorithme se doit d'être fini, mais aucune borne n'est fixée, tandis qu'un calcul concret nécessitant quelques centaines d'années doit être considéré comme irréalisable.

3.7 Indécidabilité

Revenons un moment sur les problèmes qui ont motivé la définition des machines de Turing. En effet, maintenant que nous disposons d'une définition mathématique de ce qu'est un algorithme, il devient possible d'explorer le domaine de l'indécidable, c'est-à-dire des problèmes qu'aucun algorithme se sera jamais capable de résoudre. De tels problèmes existent-ils ? Oui ! Et ils sont même très nombreux...

Le tout premier d'entre eux, exposé par Turing lui-même dans son article fondateur, est connu sous le nom de "problème de l'arrêt". Il s'exprime ainsi : existe-t-il un algorithme capable, quand on lui fournit le code d'une machine de Turing M et le code d'une donnée d, de prévoir si M fonctionnant avec d comme donnée d'entrée s'arrêtera ou non au bout d'un temps fini ? Remarquons que les machines universelles ne répondent pas totalement à la question puisqu'elles se contentent de simuler ce que ferait M sur la donnée d : si M s'arrête sur d, alors la machine universelle s'arrêtera aussi sur (M, d), mais si M "boucle à l'infini", alors la machine universelle aussi et elle aura été incapable de le prévoir...

Le problème de l'arrêt est indécidable : il est impossible de concevoir un algorithme capable de savoir à l'avance si une méthode de calcul appliquée à une certaine donnée s'arrêtera à coup sûr. Comme le fait de s'arrêter est précisément ce qui distingue les machines de Turing qui sont de vrais algorithmes de celles qui n'en sont pas, cela signifie qu'il est impossible de concevoir un algorithme capable de distinguer les vrais algorithmes de ceux qui n'en sont pas ! Nous ne détaillerons pas ici la démonstration de ce résultat, mais elle se rattache à la famille des paradoxes logiques dits du "menteur" (en disant "je suis un menteur", je mens donc "je dis la vérité" donc finalement c'est vrai que "je suis un menteur"...).

Ce premier problème indécidable peut sembler un peu abstrait et éloigné des "vrais problèmes" mathématiques. Pourtant, une de ses conséquences directes est qu'il n'existe pas non plus d'algorithme capable de décider si une formule logique quelconque est vraie ou fausse : c'est la solution de Turing au fameux Entcheidungsproblem.

Et, depuis 1936, de nombreux problèmes indécidables sont découverts chaque année, dont certains s'énoncent très simplement. Par exemple, certains problèmes de "pavage du plan" sont indécidables. Ces problèmes partent de la donnée de quelques figures géométriques (des polygones) et cherchent à remplir, à "paver" entièrement un plan avec ces figures sans laisser de blanc entre les figures. Il est impossible de savoir à l'avance si ce sera possible. De même, le "10ème problème de Hilbert", à l'origine lointaine de toute cette histoire (cf. 3.2), n'a finalement trouvé de solution qu'en 1970, quand le mathématicien soviétique Matijasevic a démontré qu'il n'existe aucun algorithme capable de résoudre toutes les équations diophantiennes de degré supérieur ou égal 5.

Il est important de comprendre qu'un résultat d'indécidabilité est une barrière théorique infranchissable : si un problème est indécidable, cela signifie qu'aucun algorithme ne pourra jamais le résoudre, quels que soient les progrès technologiques que pourront connaître les ordinateurs dans les années à venir.

3.8 L'héritage scientifique de Turing

L'article de 1936 de Turing est le point de départ d'une nouvelle discipline qu'on désigne depuis comme "l'informatique théorique". Un de ses objectifs est la classification des problèmes en fonction de leur solvabilité effective. La première distinction fondamentale introduite par Turing est le caractère décidable ou indécidable des problèmes.

Mais savoir qu'un problème est décidable (c'est-à-dire qu'il existe des algorithmes qui le résolvent) ne suffit pas, encore faut-il qu'il le soit efficacement, c'est-à-dire en utilisant des ressources (en temps de calcul et en espace mémoire) raisonnables. La difficulté est alors de définir un tel critère d'efficacité qui ne dépende pas de la machine sur laquelle sera exécuté l'algorithme, ou du langage de programmation dans lequel il sera écrit. C'est ce que réalise la théorie de la complexité.

Il ne peut être question d'expliquer ici cette théorie, contentons-nous donc d'en donner une simple intuition. Elle permet dans un premier temps de définir la complexité d'un algorithme particulier puis, dans un deuxième temps, la complexité intrinsèque d'un problème.

Rappelons qu'un algorithme sert à répondre à une classe de questions, du type : "étant donné un nombre quelconque, comment savoir s'il est ou non premier ?". Un algorithme réalise une certaine fonction qui, à chaque donnée d'entrée possible, associe une réponse unique. Or, il est évident que tester le caractère premier d'un nombre sera d'autant plus long que le nombre en question est grand, surtout s'il est effectivement premier et que tous les calculs doivent être menés à terme avant d'aboutir à la réponse finale. La complexité d'un algorithme se mesure donc en fonction de la taille de sa donnée d'entrée (c'est-à-dire du nombre de bits nécessaires pour la coder) et, pour une taille fixée, en se plaçant dans le pire des cas possibles. Elle se mesure suivant deux fonctions, qui dépendent chacune de cette taille :

le nombre d'opérations élémentaires de calcul nécessaires dans le pire des cas pour donner le résultat (complexité en temps) ;
le nombre de cases du ruban de la machine de Turing nécessaires dans le pire des cas pour donner le résultat (complexité en espace).

Pour définir maintenant la complexité intrinsèque d'un problème, il ne faut pas oublier qu'il peut être résolu de plusieurs façons différentes, à l'aide de plusieurs algorithmes possibles. La complexité d'un problème sera donc rattachée à la complexité du meilleur algorithme possible qui le résout. Par exemple, si un problème peut être résolu par un algorithme dont la complexité en temps de calcul s'exprime par un polynôme en fonction de la taille des données, on dira qu'il est de complexité P. P désigne ainsi la classe de tous les problèmes satisfaisant cette propriété. Une hiérarchie de telles classes a pu être définie, permettant de ranger tous les problèmes suivant leur plus ou moins grande "solvabilité".

L'étude de la complexité des algorithmes et des problèmes est un thème de recherche actif, dans lequel de nombreux résultats sont découverts chaque année.

3.9 L'héritage philosophique de Turing

Au delà de ses aspects techniques, l'oeuvre de Turing pose des questions philosophiques fondamentales. La notion d'algorithme qu'il a définie caractérise en effet l'ensemble des calculs possibles réalisables par un dispositif mécanique. Cette notion concerne-t-elle aussi les calculs réalisables par un humain ? Autrement dit, l'esprit est-il une Machine de Turing Universelle ?

Personne, évidemment, ne prétend trouver dans le cerveau l'équivalent des composants des machines de Turing (ruban, tête de lecture, tableau...). En revanche, il est possible de se demander si les capacités de calcul et de raisonnement dont font preuve les hommes, quel que soit le mécanisme physique qui le réalise, peuvent s'exprimer de façon algorithmique. Cette interrogation est à la base de la philosophie de l'esprit, qui s'est surtout développée dans les pays anglo-saxons. Elle est aussi à l'origine de la psychologie cognitive, où les opérations mentales sont conçues en termes de traitement de l'information.

Une autre manière d'aborder la question consiste à se demander si les machines peuvent - ou pourront un jour - penser. Turing lui-même a apporté sa contribution à la réflexion épistémologique sur ce thème. En 1950, il a publié dans une revue philosophique un article où il cherchait à montrer qu'il n'y a aucune raison de dénier aux machines cette capacité. Dans ce texte, il passait en revue tous les arguments qui soutiennent le contraire et tentait de les réfuter minutieusement. Il proposait aussi un jeu, appelé depuis le "test de Turing", destiné à fonder un critère de reconnaissance de la pensée des machines. Ce jeu consiste pour un "examinateur" humain à dialoguer à distance, par un dispositif quelconque, avec un interlocuteur inconnu qui peut être soit un autre humain soit une machine, et à identifier sa nature. Pour Turing, un ordinateur programmé de telle sorte que son comportement est indiscernable de celui d'un être humain, devrait être considéré comme aussi "intelligent" que lui.

Le projet de l' "Intelligence Artificielle " est en quelque sorte de réaliser un tel programme. Cette discipline née dans les années 50 (le terme date de 1956), cherche à écrire des algorithmes réalisant des opérations que l'on croyait jusque là l'apanage de l'homme : raisonnement logique, apprentissage, participation à des jeux de stratégie, compréhension du langage... Mais, alors que Turing prévoyait l'avènement de machines sortant vainqueur de son "test" vers l'an 2000, les réalisations concrètes de l'intelligence artificielle sont encore loin de telles performances, et de nombreux philosophes ou neurologues contestent maintenant la pertinence du modèle des machines de Turing pour expliquer le fonctionnement de l'esprit humain...

4 Conclusion

Que retenir de tout ce parcours ? On peut maintenant revenir à ce qui avait motivé tous ces développements. La distinction courante entre matériel et logiciel en informatique masque un niveau de description essentiel, qui n'appartient totalement ni à l'un ni à l'autre mais fonde l'un et l'autre, et qu'on pourrait appeler le niveau théorique ou logique. L'informatique peut ainsi être envisagée suivant trois points de vue différents et non deux seulement :

au niveau matériel ou physique, des données sont stockées sur des supports magnétiques ou optiques et sont transformées par des impulsions électriques ;
au niveau fonctionnel ou global, l'utilisateur a l'impression de manipuler des données à son échelle (que ce soit un tableau de nombres ou un personnage animé) auxquelles il applique des transformations macroscopiques ;
au niveau théorique ou logique, qu'il faudrait intercaler entre les deux autres, les données manipulées sont des codes stockés dans des bits, et les traitements qui leur sont appliqués s'expriment par des algorithmes.

Même s'ils ne sont pas sensés ignorer les deux autres, c'est ce dernier niveau qui est la compétence principale des informaticiens. Le terme "informatique" lui-même a été proposé en 1962 par Philippe Dreyfus pour l'Académie Française. Ce mot est construit par contraction de "information" et "automatique" et sa définition officielle est "la science du traitement de l'information considérée comme le support formel des connaissances". Cette définition est nettement moins fausse que celles évoquées en 1. Si on veut être encore plus précis, on peut définir l'informatique comme la science de tous les traitements effectifs applicables à des données discrètes.

Concrètement, cette discipline se décline suivant de nombreuses variantes, allant de la plus théorique (étudier la complexité d'un problème) à la plus ludique (programmer un jeu). Mais elle a une constante : la démarche d'un informaticien confronté à un problème donné se caractérise toujours par un effort de modélisation qui opère à deux niveaux :

d'une part en trouvant un équivalent discret, numériques aux données réelles du problème, en cherchant pour elles un bon codage, une bonne représentation ;
d'autre part en exprimant sous forme de règles formelles, d'algorithmes, les conditions de modifications de ces données permettant d'aboutir à un résultat.

Cette méthodologie est résumée dans le schéma de la figure 2.10 (dû à Jacques Arsac, un des pionniers de l'informatique en France).

Figure 2.10: démarche de l'informaticien

Dans le cas par exemple d'un simulateur de vol, ou d'un programme de prévision météorologique, le résultat de cet effort sera d'autant plus réussi que l'application des algorithmes aux données codées reproduira les conditions "naturelles" d'évolution des données initiales dans le monde réel. La nouveauté, par rapport à une discipline comme la physique (qui cherche aussi modéliser par des équations les conditions du monde réel), c'est que cette démarche peut également s'appliquer aux opérations mentales, celles qui permettent de faire un calcul, de chercher une stratégie gagnante dans un jeu ou de traduire un texte d'une langue dans une autre. L'objet de l'informatique est de trouver un équivalent dans le monde virtuel de ces processus, de définir et de tester des modèles pour ces mécanismes.

Mais la simulation n'a pas de limite : rien n'oblige non plus les programmes informatiques à s'appuyer sur le monde réel. Ils permettent de simuler n'importe quel environnement, du moment que celui-ci est régi par des règles qui peuvent s'exprimer par des algorithmes. La voie est libre à l'imagination des créateurs de monde virtuels...

Si nous avons particulièrement insisté sur les aspects théoriques de l'informatique, c'était pour contrebalancer l'image trop "technique" qu'elle véhicule habituellement. Mais il est temps désormais de regarder d'un peu plus près le fonctionnement des ordinateurs réels.

logiciel	données	traitemements
traitement de textes	caractères alphanumériques (lettres de l'alphabet, chiffres et tous les autres caractères du clavier)	copier, coller, effacer, déplacer, intervertir, changer la casse ou la police, mettre en page...
calculs numériques, tableurs, outils de gestion	nombres, opérations et symboles mathématiques	calculer, écrire et résoudre des équations, faire des graphiques
jeux	dessins, personnages animés, sons	appliquer les règles du jeu
bases de données, logiciels documentaires	textes, images, données factuelles	stocker en mémoire et rechercher des données
Internet, CD-Rom	toutes les données citées précédemment	tous les traitements cités précédemment + communication entre machines, échange de données

code ASCII	caractère
00100011	#
00100100	$
00100101	%
01111010	z
01111011	{
00100001	!
00110001	1

titre de livre disponible	nom auteur	prénom auteur	date parution
Mme Bovary	Flaubert	Gustave	1857
Notre Dame de Paris	Hugo	Victor	1831
Les misérables	Hugo	Victor	1862
...	...	...	...