Calculabilité

Au début du vingtième siècle, un petit groupe de logiciens et mathématiciens comprend et formalise, plusieurs décennies avant l'apparition des premiers ordinateurs, le concept de calcul et de fonction calculable. Leurs travaux vont constituer une base théorique solide sur laquelle se fondera l'informatique et ses nombreuses ramifications.

C'est toutefois une histoire moins connue, mais issue des mêmes travaux que se proposent de nous raconter les auteurs du présent ouvrage : celle de la calculabilité, discipline qui étudie les objets mathématiques sous le prisme de leur complexité calculatoire, et qui étudie en particulier les objets mathématiques incalculables. Ils réalisent cela via une notion de puissance de calcul, les degrés Turing, lesquels se révèlent d'une richesse surprenante et permettent de mieux comprendre de nombreux aspects des mathématiques générales.

La calculabilité a connu des succès majeurs en servant de fondement mathématique à l'étude de certaines qu