Le titre de cet article peut vous sembler bien mystérieux, mais ne soyez-pas effrayés, tout vous sera bientôt expliqué !

Dans l’article précédent sur la notion d’exergie, je vous ai parlé de l’entropie de Shannon, qui permet de mesurer la quantité d’information d’une source de données. Pour rappel, l’entropie (mesurée en bits) d’une source pouvant prendre \(N\) valeurs possibles est donnée par la formule:

où \(P_i\) est la probabilité d’apparition de chaque valeur.

Dans le même ordre d’idées, on peut se demander quelle est la quantité d’information contenue dans un nombre, par exemple 1073741824. La notion d’entropie est ici inutilisable, car en dehors de tout contexte, ce nombre ne peut pas être associé à une probabilité. Il est cependant possible de compter la quantité de bits nécessaire pour représenter ce nombre en binaire, donnée par \(log_2 (1073741824) = 30\). En première approche, la quantité d’information dans 1073741824 serait donc de 30 bits. Cependant, si on remarque que \(1073741824 = 2^{30}\), on voit que ce nombre peut s’écrire sous une forme beaucoup plus simple, qui est simplement sa décomposition en facteurs premiers. D’une certaine façon, cette expression “\(2^{30}\)” est la représentation d’un algorithme qui s’écrirait en français “multiplier 30 fois par lui-même le nombre 2”.

Prenons maintenant un cas plus intéressant: le nombre \(\pi\) (3,14159…). Ce nombre possède une infinité de décimales à première vue aléatoires, et contient donc a priori une quantité d’information infinie, d’un point de vue numérique. Cependant de nombreux algorithmes existent pour calculer les n premières décimales de \(\pi\), donc l’information contenue dans \(\pi\) peut se résumer à la description de l’un de ces algorithmes. La question devient maintenant: quelle est la quantité d’information (en bits) de cet algorithme ? Le but de l’article est justement d’apporter une réponse à cette question !

Pi

On définit la complexité de Kolmogorov (du nom du mathématicien russe Андрей Колмогоров) d’un nombre comme étant la longueur du plus petit programme nécessaire pour calculer ce nombre. Un nombre complètement aléatoire ne peut être décrit par aucun programme plus court que le nombre lui-même, et possède donc une complexité de Kolmogorov maximale (on rejoint ici le concept d’entropie, qui est maximale quand les données sont aléatoires). La définition s’étend bien sûr à d’autres types de données, comme du texte. Par exemple il est clair que le texte “la la la la la la la la la la la la la la la la la la la la” contient assez peu d’information, résumée dans l’algorithme “écrire 20 fois le mot ‘la’”.

Cette définition est intéressante mais théorique, car d’une part il a été prouvé qu’il est impossible de trouver un algorithme permettant de calculer la complexité de Kolmogorov, et d’autre part elle ne dit pas vraiment comment calculer la longueur d’un programme. Il est clair que le choix du langage de programmation a une influence sur la longueur du programme minimal, mais on peut également prouver assez facilement (théorème d’invariance) que quelque soit le langage choisi, la complexité de Kolmogorov est la même, à une constante près.

Bien qu’il soit impossible de calculer de façon automatique la complexité de Kolmogorov d’un objet (nombre ou texte), on peut obtenir une borne supérieure de cette complexité si on arrive à trouver au moins un programme permettant de produire cet objet. Il ne reste plus qu’à trouver un langage de programmation suffisamment puissant pour écrire ce programme avec le moins de bits possible, pour s’approcher au plus près de la complexité de Kolmogorov. C’est dans cet objectif que John Tromp a mis au point le λ-calcul binaire, qui est simplement une variante du λ-calcul.

Combinator

Le λ-calcul (ou “lambda-calcul”), est un formalisme inventé dans les années 1930 par le mathématicien Alonzo Church, bien avant l’apparition des premiers ordinateurs, et est l’ancêtre de tous les langages de programmation fonctionnelle (Lisp, Haskell, Clojure, etc.). La puissance du λ-calcul vient du fait qu’il permet d’écrire n’importe quel programme, à partir d’une syntaxe extrêmement simple. En λ-calcul, tout programme est une expression, qui ne peut être que l’une des 3 formes suivantes:

  1. Une variable, de la forme x, y, z ou n’importe quelle autre lettre
  2. Une abstraction, de la forme (λx.a), où x est une variable et a est une autre expression
  3. Une application, de la forme (a b), où a et b sont deux autres expressions

Et voilà c’est tout ! Mais alors, comment écrire un programme en λ-calcul ? Pour cela, il faut d’abord comprendre quelle est la signification de ces différentes formes.

Une abstraction (λx.a) est en fait simplement la définition d’une fonction, qui prend la variable x en paramètre, et renvoie l’expression a. Par exemple l’expression (λx.x) correspond à la définition de la fonction “identité”, qui renvoie toujours sa valeur d’entrée. L’expression (λx.y) définit la fonction “constante y”, qui renvoie toujours y quelque que soit la valeur d’entrée

Une application (a b) correspond en fait à un appel de fonction, et sa valeur est le résultat de la fonction a appliquée au paramètre b (en mathématiques on écrirait plutôt “a(b)”). 

Le cœur du λ-calcul est la règle suivante, dite de β-réduction, qui permet de calculer le résultat d’une application: (λx.a b) = a[x := b]. En français, cette règle signifie: “Le résultat de l’application de la fonction (λx.a) à l’expression b est égal à l’expression a dans laquelle on a remplacé toutes les occurences de la variable x par l’expression b”. Cette règle en apparence complexe est en fait ce qu’on fait tous les jours en mathématiques: par exemple si on a une fonction f définie par “f(x) = x+2”, l’application de f au nombre 4 se calcule par “f(4) = 4+2 = 6”; on a simplement remplacé x par 4 dans la définition de f. En λ-calcul, la fonction f s’écrirait “(λx.(+ x 2))”, et le calcul s’écrit: “((λx.(+ x 2)) 4) = 6)”. Attention, on écrit bien “+ x 2” et non pas “x + 2”, car la fonction à appliquer doit toujours apparaître en premier dans une expression (on parle de notation préfixe). A noter que le nom des variables n’a pas d’importance, on peut tout aussi bien écrire la fonction f comme “(λy.(+ y 2))”.

Comme cette notation introduit beaucoup de parenthèses, on prend également quelques conventions pour simplifier l’écriture: 

  • (a b c) = ((a b) c)
  • a b = (a b)
  • λa.b c = (λa.(b c))

Avec ces conventions, le calcul précédent s’écrit plus simplement “(λx.+ x 2) 4 = 6”.

Dernier détail: une fonction à deux variables peut s’écrire sous la forme λx.λy.a, une fonction à trois variables λx.λy.λz.a, etc.

Croyez-le ou non, avec ces quelques règles il est possible d’écrire n’importe quel programme !

Par exemple on définit la constante logique “VRAI” par l’expression “λx.λy.x”, qui est une fonction qui prend deux variables x et y en paramètre, et renvoie toujours x. De même on définit la constante “FAUX” par “λx.λy.y”, et l’opérateur logique “ET” par “λx.λy.y x y”. Avec ces conventions, on peut vérifier par exemple que “ET VRAI FAUX = FAUX”, grâce à la règle de β-réduction. Allons-y !

  • ET VRAI FAUX = (λx.λy.y x y) VRAI FAUX = FAUX VRAI FAUX = (λx.λy.y) VRAI FAUX = FAUX

De la même façon on vérifie facilement que “ET VRAI VRAI = VRAI”:

  • ET VRAI VRAI = (λx.λy.y x y) VRAI VRAI = VRAI VRAI VRAI = (λx.λy.y) VRAI VRAI =VRAI

Remarquez que j’ai utilisé dans les exemples précédents des nombres entiers et l’opérateur +, alors que ceux-ci ne sont absolument pas définis par le λ-calcul. Bien sûr il est difficile d’écrire des programmes sans pouvoir utiliser les nombres entiers… Church a donc imaginé une façon de définir les nombres dans le λ-calcul:

  • 0 := λx.λy.y
  • 1 := λx.λy.x y
  • 2 := λx.λy.x (x y)
  • 3 := λx.λy.x (x (x y))
  • n+1 := λx.λy.x (n x y)

Comme les opérateurs logiques, les nombres sont donc définis par des fonctions à deux variables. On remarque d’ailleurs que 0 = FAUX, ce qui est assez logique et habituel dans les langages de programmation. Avec cette convention, l’addition se définit par:

  • + := λa.λb.λx.λy.a x (b x y)

Avec ces définitions (bien compliquées), on peut vérifier que 2+1 = 3:

  • + 2 1 = (λa.λb.λx.λy.a x (b x y)) 2 1 = λx.λy.2 x (1 x y) = λx.λy.x (x (1 x y)) = λx.λy.x (x (x y)) = 3

Ouf ! De la même façon on peut définir toutes les structures de données et de contrôle utilisées habituellement en programmation: paires, ensembles, listes, boucles, récursivité, tests, etc. !

Tunnel

Le λ-calcul est donc un langage de programmation qui permet d’écrire n’importe quel algorithme, mais pour en revenir au but initial, comment peut-on mesurer la longueur en bits d’un programme λ-calcul ? Il s’agit de trouver un codage pour écrire une expression en binaire, de la façon la plus efficace possible.

La première chose à faire est d’utiliser la notation des index de De Bruijn, qui consiste à remplacer les noms de variable par des nombres. Dans une fonction à n variables, la première variable est notée 1, la deuxième variable est notée 2, etc. Il faut également rétablir les parenthèses, pour ne garder que des applications de la forme (a b).

Par exemple la fonction “identité” λx.x s’écrit simplement “λ1”, le nombre 1 (λx.λy.x y) s’écrit “λλ(1 2)”, l’opérateur + (λa.λb.λx.λy.a x (b x y)) s’écrit “λλλλ(1 (3 ((2 3) 4)))”, etc.

La deuxième étape est de convertir l’expression en binaire, grâce au codage suivant:

  • λa = 00 a’   (où a’ est le codage binaire de l’expression a)
  • (a b) = 01 a’ b’
  • 1 = 10
  • 2 = 110
  • 3 = 1110
  • etc.

Avec ce codage, l’identité (λ1) devient donc “00 10”, le nombre 1 (λλ(1 2)) devient “00 00 01 10 110”, et l’opérateur + (λλλλ(1 (3 ((2 3) 4))) devient “00 00 00 00 01 10 01 1110 01 01 110 1110 11110”.

Si on utilise les nombres de Church, on peut montrer que l’opérateur “exposant” (\(x^y\)) s’écrit tout simplement λx.λy.y x, autrement dit λλ(2 1), qui se code en “00 00 01 110 10”. Grâce au λ-calcul binaire, on peut donc coder l’algorithme “exposant” en seulement 11 bits. L’opérateur \(x^{x^x}\), qui s’écrit λx.x x x, se code lui en “00 01 10 01 10 10”, soit 12 bits.

Prenons maintenant le nombre 1 suivi de 10 milliards de zéro. Ce nombre gigantesque peut s’écrire \(10^{10^{10}}\), et est donc le résultat de l’opérateur \(x^{x^x}\) appliqué à 10. On peut montrer que le nombre 10 s’écrit avec 47 bits en λ-calcul binaire, donc le programme qui permet de calculer \(10^{10^{10}}\) a une longueur de 2+47+12=61 bits, alors que si on écrit simplement \(10^{10^{10}}\) en binaire, on obtient un nombre de plus de 332 milliards de bits !

La complexité de Kolmogorov de \(10^{10^{10}}\) est donc au maximum de 61 bits; il resterait à prouver qu’il n’existe pas d’algorithme plus efficace (en utilisant le λ-calcul) pour calculer ce nombre, pour montrer que la complexité est exactement égale à 61 bits.