La limite du possible.

Dans les années 1930 (avant internet, le téléphone portable, et même avant l'ordinateur (tel qu'on le connais aujourd'hui (puissant, personnel, courant, ergonomique))) quelques mathématiciens tripotaient allègrement des concepts relevant à l'époque de la science fiction. Les avancées théorique de cette époque influence aujourd'hui encore le développement de l'informatique.


Alan et Alonzo :
Les deux prénoms des mathématiciens qui ont laissés leurs noms sur les mathématiques de l'informatique tout comme Euclide l'a fait sur la géométrie. Avec des motifs très différents, ils ont tout deux découvert (on n'invente pas les mathématiques, on se contente d'exposer des vérités qui n'attendaient que ça) des modèles de calcul qui porte leur nom (de famille).

La Turing-calculabilité (ou T-calculabilité) :
Alan Turing cherchait à découvrir les limites du faisable. Il a donc inventer les machines de Turing, concept théorique cruellement proche des ordinateurs actuels. Il existe plusieurs modèle pour les MTs (machines de Turing) le plus simple étant de considérer un ruban (potentiellement infini(1)) sur lequel se promène une tête de lecture/écriture capable de lire et d'écrire un certain nombre (au moins 2) de symbole et dont le comportement est déterminé par un ensemble de règles (du type : si la machine est dans l'état 42 et que le symbole sous la tête de lecture est '0' alors, se placer dans l'état 24, écrire un symbole '1' et bouger la tête de lecture vers la gauche). A partir de ce modèle, Alan Turing défini un ensemble de fonctions dont on peut calculer les valeurs en un temps prévisible, un ensemble de fonctions dont on peut calculer les valeurs en un temps imprévisible (on lance la machine (au sens figuré) mais on ne sait pas quand ni même si elle va s'arrêter), un ensemble de fonction dont on ne peut pas calculer les valeurs (on lance la machine et elle ne s'arrêtera jamais).
Les machines de Turing ont une influence sur la conception des ordinateurs. Bien que la lente transition vers la mémoire en SSD fasse pencher de plus en plus les ordinateurs actuels dans le camp des machines RAM (cousines proche des MTs). L'influence de ce modèle ne s'arrête pas au Hardware, en effet les langages impératifs sont directement inspirés des fonctions de transition des MTs (avec un niveau d'abstraction plus élevé).

La LAMBDA-calculabilité :
Alonzo Church voulait développer une syntaxe permettant d'exprimer des fonctions mathématiques. Cette syntaxe est d'une simplicité effarante :

A partir de cette syntaxe, Church défini des méthodes de calculs de ses fonctions (appelées réductions) et tout les objets mathématiques courants et notamment les entiers de Church(2). Il montre que certaines fonctions sont exprimables en LAMBDA-calcul et calculable, que d'autres sont exprimables mais difficile à calculer (selon la méthode choisie, le calcul n'aboutit pas forcément), que d'autres encore ne sont pas exprimables du tout.
Oh! surprise, ces catégories coïncident avec celles d'Alan Turing et de sa machine. Les fonctions calculables dans un modèle, le sont dans l'autre ! Il en est de même pour tout les autres modèles étudiés à ce jours.


C et Haskell :
Aujourd'hui encore naissent des langages de programmation si bien que leur nombre est élevé. On peut les distingués de plusieurs manières : paradigmes (la définition est assez difficile), niveaux (ou niveaux d'abstractions), verbosité, typage...

C
Titre court s'il en est, C est, en plus de la troisième lettre de l'alphabet, le nom d'un des langages (de programmation) les plus utilisés actuellement dans le monde. Ce qui le rend intéressant pour nous (en tout cas pour tout ceux qui ont lu jusqu'ici) est qu'il est très proche du modèle des machines de Turing. Dans un pur style impératif/procédural et avec un niveau d'abstraction très bas, il est possible de travailler octet par octet (même si on préfèrera utiliser les quelques raffinement disponibles tel les entiers, les flottants, les structures...) à la manière des cases mémoire des MTs.

Haskell
Le mathématicien américain Haskell B. Curry a beaucoup influencé le LAMBDA-calcul et il a joué un rôle majeur dans l'équivalence de Curry-Howard, c'est donc tout naturellement que son prénom fut donné à un langage de programmation purement fonctionnelle (qui est inspirée du LAMBDA-calcul). Haskell a en plus un typage fort et une évaluation paresseuse tout deux liés à la théorie d'Alonzo Church.

Du faisable et du possible :
Les mathématiques sont la science du possible. Elles sont capables de décrire l'univers tel qu'il est ou tel qu'il serait si <ajouter ici une condition farfelue de votre choix>. Pour s'en convaincre, je conseil la lecture de Flatland(3) (de toute façon je la conseille même si ce n'est pas pour se convaincre de la puissance des mathématiques). Dans la même optique, on peut définir l'informatique comme la science du faisable. Le fait que tout les modèles de calculabilité découvert à ce jour coïncident poussa Alonzo (on fini par être assez intime avec les mathématiciens (et on veut surtout éviter des répétitions trop nombreuses)) à énoncer ce qui deviendra la "thèse de Church". Elle stipule que la notion de Turing calculabilité et celle de LAMBDA calculabilité sont toutes deux équivalentes à la notion intuitive de calculabilité. Il en existe une version "physique" qui dit que les deux modèles ont le même pouvoir que la nature (ils peuvent calculer les même choses).





(1) il existe plusieurs infini, des grands et des petits, des actuels et des potentiels. Un ensemble est potentiellement infini si il est toujours assez grand pour les besoins qu'on en a. Les grecs qui à cause de Zénon avait des problèmes avec l'infini voyaient les entiers comme un ensemble infini potentiel.
(2) par exemple les entiers sont représentés par des itérateurs :
0 <-> (f->id) <-> Lf.Lx.x <-> "0 est la fonction qui a une fonction f associe la fonction f itérée 0 fois"
1 <-> (f->f) <-> Lf.Lx.(f)x <-> "1 est la fonction qui a une fonction f associe la fonction f itérée 1 fois"
2 <-> (f->fof) <-> Lf.Lx.(f)(f)x <-> "2 est la fonction qui a une fonction f associe la fonction f itérée 2 fois"
etc.
(3)Flatland est un livre d'Edwin Abbott Abbott mettant en scène un univers ne possédant que deux dimension. L'auteur critique de manière virulente la société victorienne (dans laquelle il a grandi) en prétextant de l'exercice de pensée philosophique bien plus que mathématique.