Commentaires sur :

Michael Sipser "Introduction to the Theory of Computation" PWS 1997

La lecture de ce livre est une drôle d'expérience. Vous l'achetez parce que vous voulez régler un vieux compte avec la théorie de l'informatique : la machine de Turing, la théorie des langages, les algorithmes, la décidabilité, le fait qu'il n'existe pas de programme qui sache vérifier les programmes, le cryptage à clé publique, les ordres de grandeur qui distinguent le faisable (polynomial) de l'impossible (exponentiel), etc. Vous feuilletez le livre en soupirant : définitions, lemmes et théorèmes s'enchaînent, cela n'a pas l'air facile à lire. Mais comme vous êtes courageux et désireux d'apprendre, un soir vous vous y mettez. Et vous y passez la nuit ! puis le livre ne vous quitte plus : vous le lisez dans le métro, dans les salles d'attente, aux chiottes (oui oui), partout où vous avez un instant de tranquillité. Vous passez des soirées de lecture délicieuse.

Une expérience m'a frappé : vous arrivez sur le quai du RER, vous constatez en râlant qu'il y en a pour sept minutes d'attente. Vous sortez le Sipser du cartable, vous lisez à peine une demie page, et hop ! le RER est là par magie. Ce livre accélère le temps.

Sipser est un grand pédagogue. Sans renoncer à la rigueur, il conduit le long d'un chemin facile, vérifiable ; en partant d'automates simples il fait découvrir les langages, les grammaires, la machine de Turing, la décidabilité, la récursion, la complexité dans le temps (durée des calculs) et dans l'espace (taille de la mémoire nécessaire), etc. Il est vrai qu'il faut  revenir souvent sur ses pas pour se remémorer les résultats acquis, mais c'est bien le moindre des efforts que l'on puisse consentir.

J'admire d'autant plus l'effort pédagogique des Américains que je me rappelle avec colère certains livres français. Connaissez-vous la recette pour faire sérieux ? la voici :

- affecter de croire que le lecteur connaît les définitions : cela dispense de les indiquer ;

- donner les démonstrations selon le formalisme le plus strict : il faudra du mérite pour les comprendre ;

- se référer au cadre théorique le plus abstrait : tout ce qui est pratique est vulgaire ;

- ne pas donner d'indication sur les intentions qui président au raisonnement : ce serait pécher contre la rigueur ;

- dans les calculs, sauter deux lignes sur trois : le lecteur ébahi cherchera le passage d'une ligne à l'autre ;

- ne pas relire les épreuves d'imprimerie : on est au dessus de ça, et une erreur par ci par là contribue à la difficulté.

La grande astuce de Sipser, c'est d'écrire deux fois la même démonstration : une fois en langage courant pour donner une idée générale (c'est ce qu'il appelle "proof ideas") ; la deuxième fois en notation formelle. Lorsque je lis un chapitre la première fois, je me contente des "proof ideas" pour avoir une idée d'ensemble. Puis je lis les démonstrations en entier pour me familiariser avec les notations.

Certes tout cela fait partie de la formation d'un étudiant en informatique. Mais je ne suis qu'un modeste praticien, je n'ai pas fait ces études-là ; je me suis toujours demandé comment font ceux qui inventent des langages, conçoivent des compilateurs, etc. J'étais écrasé par une montagne d'abstraction floue. Avec Sipser je suis au sommet de la montagne ; je domine les vallées où je me traînais auparavant. Mon expérience me permet d'y voir des choses que l'étudiant en informatique ne discerne peut-être pas : cette théorie m'est familière. Reste à consolider le pont qui la relie à ma pratique.