Introduction à l’analyse calculatoire des théorèmes

De nombreux théorèmes peuvent être vus comme des problèmes abstraits. Par exemple, le lemme de König nous dit que tout arbre infini à branchement fini, admet un chemin infini. Il est possible de voir le lemme de König comme le problème dont les instances sont des arbres, et dont les solutions sont des chemins à travers les arbres.

Parmi ces théorèmes classiquement vrais, certains ne sont pas calculatoirement vrais, au sens où ils admettent des instance sans solution calculable en l’instance. Dans cette présentation, nous introduirons les outils de la réduction calculatoire pour comparer les degrés d’incalculabilité desdits théorèmes.

Quels sont les théorèmes calculatoirement vrais ? Comment utiliser le contenu calculatoire d’un théorème pour en résoudre un autre ? Vous le saurez… après la pub.