J'entends ou je lis parfois des gens affirmer doctement que « l'informatique n'est pas une science ». Il est vrai que la bureautique, c'est-à-dire ce à quoi se limite généralement leurs connaissances en la matière, n'est pas une science, et que la connaissances des particularismes de tel ou tel système d'exploitation ne relève pas non plus de la pratique scientifique. J'entends également parfois que la recherche en informatique, étant destinée à répondre aux besoins à court terme de l'industrie et de l'économie (on ajoutera capitaliste si le locuteur est plus ou moins marxiste), vit dans l'instant et ne se préoccupe de documentation scientifique que récente.

Ces personnes ne me lisent probablement pas, mais je vais toutefois leur donner des conseils de lecture. Tout d'abord, il serait bon qu'ils s'intéressent aux problèmes de la logique du début du 20e siècle : programme de Hilbert, théorèmes de complétude et d'incomplétude de Gödel, résultats de Church et de Turing. La bande dessinée Logicomix pourra fournir une présentation imagée de certains des intervenants.

Ensuite, ils pourront aborder la question que l'on retrouve derrière une bonne partie des recherches en informatique, à savoir celle de la complexité des calculs et notamment de la séparation des classes P et NP (ou, ce qui revient au même, de la complexité de la décision du calcul des prédicats). Ce problème a semble-t-il été entrevu par Gödel en 1956, mais c'est en 1971 que Leonid Levin et Stephen Cook ont indépendamment vu son importance, avec la notion de NP-complétude. Depuis, malgré des recherches difficiles menées par des scientifiques de très haut niveau, nous ne savons toujours pas si ces classes sont séparées, et nous ne savons d'ailleurs même pas si ce fait est décidable (dans le même sens que l'indécidabilité de Gödel ; pour la petite histoire, quand j'ai vu Cook en 2010 à Edimbourg et que je lui ai demandé son opinion sur la question de l'indécidabilité, il m'a plus ou moins accusé de défaitisme).

Les démonstrations de base en calculabilité et complexité ne sont pas si difficiles que cela, mais leur acquisition demande de « rentrer » dans certains concepts éventuellement initialement peu intuitifs ; c'est encore plus vrai en logique, domaine qui apparaît souvent mystérieux et riche en paradoxes. À la rentrée prochaine, Olivier Bournez, Bruno Salvy et moi-même donnerons à l'École polytechnique un enseignement visant à démystifier ces sujets. (*)

C'est également avec plaisir que j'apprends que Richard J. Lipton, auteur du blog Gödel's Lost Letter and P=NP, en a tiré un livre, sobrement titré The P=NP Question and Gödel's Lost Letter. Si vous vous demandiez quoi emmener à la plage, c'est certainement un bon choix.

(*) Je précise que je ne suis un spécialiste d'aucun de ces trois sujets, et que je suis donc en pleines révisions.