La décidabilité
En termes modernes: peut-on prouver par une procédure « mécanique » qu’une formule est vraie
1936: Turing publie un article montrant l ’impossibilité de la décidabilité
Il formalise la notion de procédure de calcul, à l’aide d ’une machine « théorique », la machine de Turing