Publications
LOWER BOUND
Ce qu'aucune machine, aussi rapide soit-elle, ne pourra jamais contourner.
Qu'est-ce que LOWER BOUND ?
En informatique, une borne inférieure (lower bound) est un coût qu'aucune méthode ne peut battre, aussi astucieuse soit-elle. Trier n éléments en les comparant demande environ n log₂ n comparaisons, quel que soit l'algorithme. Effacer un bit libère au moins kT ln 2 de chaleur, quelle que soit la machine. Et certaines questions n'ont aucun algorithme capable d'y répondre dans tous les cas : savoir si un programme quelconque finira par s'arrêter, par exemple.
LOWER BOUND est la série dans laquelle le laboratoire explore ces limites. Chaque dossier part d'un fait établi, le suit jusqu'à ce que quelque chose cède, et se termine sur une question ouverte. Chaque affirmation est accompagnée de sa source.
Pourquoi ici ? Parce que LOWER BOUND applique notre méthode à la science du calcul : chercher la limite, réduire chaque idée à sa forme la plus courte, et chercher ce qui pourrait nous donner tort.
Réf. Knuth, 1973 ; Landauer, 1961 ; Turing, 1936
Les dossiers
RSSLes dossiers sont publiés en anglais ; leur texte est traduit ici, les visuels restent en anglais.
