Les ordinateurs sont présents dans notre vie quotidienne, et sont utilisés pour réaliser un nombre toujours plus important de tâches différentes. Il semblerait donc que les domaines d'application de l'informatique soient illimités, et que les ordinateurs ont une capacité sans borne à résoudre des problèmes. Pourtant, il est bien connu depuis les travaux d'Alan Turing (années 1920, donc bien avant la construction des premiers ordinateurs) que l'informatique est confrontée à une limite théorique intrinsèque, appelée indécidabilité. Cette notion stipule qu'il existe des problèmes que les ordinateurs ne peuvent pas résoudre. Ce cours-conférence a pour but de donner une introduction vulgarisée à ces notions théoriques fondamentales, et de montrer leur influence considérable sur tous les domaines de la recherche en informatique.

On commencera par étudier la notion de problème (comment la définir de manière rigoureuse), et la notion d'algorithme, c'est-à-dire de solution informatique à un problème donné. Cette introduction sera placée dans son contexte historique (on verra notamment les rapports avec la logique et le célèbre programme du mathématicien David Hilbert), et couvrira les travaux fondateurs d'Alan Turing et d'Alonzo Church.

Ensuite, on démontrera qu'il existe des problèmes indécidables, c'est-à-dire des problèmes pour lesquels aucune solution algorithmique ne peut exister.

Enfin, on présentera certaines conséquences de ce résultat fondamental, en brossant un panorama de la recherche actuelle en informatique, et plus particulièrement du domaine très actif de la vérification assistée par ordinateur – qui se propose d'étudier les méthodes permettant de prouver automatiquement qu'un programme est correct.