Cet ouvrage rassemble 24 textes fondamentaux de la théorie de la calculabilité, source de l'informatique au même titre que l'électronique. Il comprend des contributions de Babbage, de Lovelace, de Gödel, de Church, de Hilbert et de Turing. ©Electre 2025

Alors que les algorithmes s'invitent dans tous les domaines de l'activité humaine, cette anthologie de la calculabilité vient à point nommé. Le prodigieux essor de l'informatique n'aurait pas été aussi fulgurant sans les percées théoriques qui ont fait suite aux tâtonnements initiaux et dont l'histoire est ici retracée. Les recherches sur de grands problèmes de la logique mathématique - notamment celui de l'existence d'une procédure mécanique générale (un algorithme !) pour décider de la vérité d'un énoncé d'arithmétique - ont conduit, au milieu des années 1930, à trois grands modèles mathématiques équivalents de la notion informelle de calculabilité effective. Cela restera certainement comme une des grandes aventures intellectuelles du XX^e siècle. Très présents dans ce livre, deux des principaux artisans de ces découvertes, Gödel et Turing, figurent d'ailleurs parmi ces grands génies scientifiques qui, comme Einstein, marquent notre imaginaire.

Si, pour l'essentiel, l'histoire de la théorie de la calculabilité est assez étroitement délimitée dans le temps, nous en avons retracé les origines, depuis Babbage (vers 1840) et son projet de calculatrice universelle programmable, et nous en avons suivi les développements jusqu'en 1970 : c'est alors en effet que la correspondance de Curry-Howard entre preuves et programmes est venue éclairer l'importance du lambda-calcul de Church et que le théorème de Matiiassevitch a rattaché la théorie de la calculabilité à de grands desseins des mathématiques du XX^e siècle, en mettant la dernière main à la résolution du dixième des vingt-trois problèmes de la célèbre liste proposée par Hilbert en 1900.

Cette anthologie veut aider à retracer, au contact direct avec les sources, les étapes initiales décisives d'une théorie du calcul. Elle propose un ensemble de vingt-quatre textes, où l'on s'est soucié de faire une place aux contributions de l'école russe, trop souvent négligées. Chacun d'eux est accompagné d'une présentation et de notes destinées à en faciliter la lecture, rédigées par une équipe composée de spécialistes internationaux. L'ensemble est précédé d'une imposante introduction de Serge Grigorieff, qui apporte sur cette histoire le point de vue du logicien informaticien contemporain.