On voit souvent les ordinateurs comme de super-calculateurs. Qu'entend-on exactement par là ? Un ordinateur est-il capable de calculer plus de choses qu'un être humain, ou simplement plus vite et avec moins d'erreurs ? Y a-t-il des choses qu'un ordinateur ne peut pas calculer ? Ne pourra jamais calculer ?
Répondre à cette question n'a rien d'évident. Les mathématiciens inventent régulièrement, depuis plusieurs siècles, des objets plus ou moins barbares, aux noms aussi doux qu'endomorphismes, cohomologies, fonction zêta. Peut-être les mots de sinus ou racine carrée vous seront-ils plus familiers. Descendons encore plus simplement vers l'addition. Tout le monde sait faire une addition.
En quoi cela consiste-t-il ? Prendre une feuille de papier, écrire les deux nombres à ajouter en haut du papier, et puis appliquer une suite de règles apprises à l'école primaire jusqu'à aboutir au résultat. Si on veut ajouter plus de nombres, ou des nombres plus grands, il suffit de prendre plus de papier. Y a-t-il une limite à la taille des nombres que l'on peut ajouter ? En pratique, bien sûr. Essayez d'ajouter dix mille nombres de dix mille chiffres si vous ne me croyez pas. Mais en théorie, il n'y a pas de limite.
En fait, il serait assez étrange de poser une limite a priori : si on décide de n'ajouter que des nombres de 100 chiffres au maximum, ça ne coûte presque rien d'ajouter des nombres de 101 chiffres. C'est pareil si on décide de mettre la limite à 1000, ou à 10000. On le voit bien avec les ordinateurs : ils sont capables d'ajouter des nombres très grands, et de plus en plus grands au fil des ans. On va donc décider que pour définir ce qu'on peut calculer, la taille ne va pas être un problème. Si on a besoin d'une feuille de papier en plus, on la prend. On s'intéresse à ce que l'on pourrait calculer en théorie, si l'on avait une quantité de papier illimitée.
Pour les ordinateurs, le papier s'appelle la mémoire ; ça ne change absolument rien. Mais alors, à part être infatiguable et avoir plus de mémoire, un ordinateur peut-il calculer plus de choses qu'un être humain ? La réponse est non.
Dans les années 1940, le mathématicien Alan Turing inventa une machine, baptisée logiquement machine de Turing. Cette machine n'était pas une vraie machine (même si Turing passa une bonne partie de sa courte vie à construire les ancêtres des ordinateurs pour le gouvernement anglais). C'était une machine imaginaire, très simple. Elle dispose de feuilles de papier, en nombre illimité. Sur chacune de ces feuilles, elle peut écrire des nombres, et lire ceux qu'elle a écrit. Au démarrage, on lui donne une feuille avec les nombres à additionner (si c'est une machine de Turing qui sert à additionner, bien sûr). Elle lit alors ces nombres, ce qui la fait changer d'état. A chaque étape du calcul, elle lit un nombre, change d'état, écrit un nombre sur une feuille de papier, et passe à l'étape suivante. Quand elle arrive dans un état qu'on appelle final, elle rend la dernière feuille de papier, sur laquelle figure le résultat.
Cette notion d'état peut sembler assez vague ; elle correspond pourtant à ce que nous faisons nous mêmes quand nous ajoutons deux nombres. Souvenez-vous : si la somme des deux chiffres que je suis en train d'additionner est plus grande que dix, je note une retenue. Cette retenue, qu'il faut justement retenir, avant de passer à l'étape suivante, c'est un changement d'état : vous passez de l'état "j'additionne deux chiffres normalement" à l'état "j'additionne deux chiffres mais il ne faut pas que j'oublie la retenue". Cette analogie fonctionne tellement bien, on la retrouve tellement dans tous les domaines du calcul (et de la vie en général), que Turing était sûr et certain que ses machines étaient capables de calculer tout ce qu'un être humain pouvait calculer, et rien de plus.
Mais être certain ne suffit pas. Un autre mathématicien, Alonzo Church, s'intéressa à la même question, d'un point de vue nettement plus formel. Il écrivit des équations, posa des hypothèses, fit de nombreuses démonstrations fort compliquées et finit par arriver à une définition de ce qui était (selon lui) calculable et de ce qui ne l'était pas. Attention, ce n'est pas parce qu'il avait fait plus de calculs que son résultat avait plus de valeur que celui de Turing : tous les deux disaient « ceci est ma définition de ce qu'un être humain est capable de calculer. » Sans preuve, juste avec des exemples montrant que les choses simples pouvaient effectivement être calculées par leur système. Alors, lequel avait raison ? Comment même savoir si l'un des deux avait raison ?
J'ai horreur de laisser planer le suspense comme ça, mais je n'ai pas le temps de finir ce billet maintenant - la suite est disponible
Here is a quick test for a txt2tags plugin for nanoblogger. The code is pretty straightforward:
# NanoBlogger plugin to render txt2tags format entries
# /usr/share/nanoblogger/plugins/entry/format/txt2tags.sh
# Released in the public domain - Gabriel Kerneis
TXT2TAGS="/usr/bin/txt2tags"
TXT2TAGS_OPTS="-i - -o - --mask-email -H -q -t xhtml "
# nb_msg "$plugins_textformataction `basename $nb_plugin` ..."
NB_EntryBody=$(echo "$NB_EntryBody" | ${TXT2TAGS} ${TXT2TAGS_OPTS})
Lovely, n'est-ce pas ?
Any comment? Send an email to <blog (a) kerneis info> (obsfuscated by txt2tags).