Début du XXème : des progrès théoriques
En 1928, David Hilbert énonce le problème de la décision : est-il possible de trouver une méthode « effectivement calculable » pour décider si une proposition est démontrable ? Pour définir ce qui est calculable, Alonzo Church et Alan Turing proposent, en 1936, deux visions différentes mais équivalentes :
- le lambda-calcul de Church ;
- la machine universelle de Turing.
Ils posent ainsi ainsi les bases de l’informatique et définissent de façon théorique un ordinateur. Ils mettent en évidence également que certains problèmes ne peuvent pas être résolus par les machines.
|
|
En 1938, Claude Shannon explique comment construire des machines à relais en utilisant l'algèbre de Boole pour décrire l'état des relais (1 : fermé, 0 : ouvert). Pendant la guerre, il fonde la théorie de l’information.
La cohérence des mathématiques
Au début du XXième, le grand mathématicien Hilbert exprime le souhait que ses collègues arrivent à prouver la cohérence des mathématiques : toute proposition mathématique doit pouvoir être prouvée ou réfutée.
Les premiers résultats vont dans le sens d’Hilbert, en particulier le logicien et mathématicien Kurt Gödel prouve que les différents types de raisonnements logiques sont déjà tous connus.
À la surprise générale, il démontre ensuite en 1931 que le projet d’Hilbert n’est pas réalisable : il existera toujours des propositions dont on ne peut ni démontrer qu’elles sont vraies, ni démontrer qu’elles sont fausses. C’est le cas par exemple de l’hypothèse du continu.