Calculabilité et complexité/Introduction
La calculabilité est une notion convergente de deux domaines :
- la théorie des langages, qui permet notamment de généraliser les automates ;
- la logique et particulièrement le théorème d'incomplétude de Gödel.
Le théorème de Gödel répond à la question « que peut-on démontrer ? » et énonce que tout système formel qui contient l'arithmétique est incomplet, c'est-à-dire qu’il contient des formules valides qu'on ne peut pas démontrer. Cette remarque découle du même problème d'autoréférence qui conduit au Paradoxe du menteur et à celui du barbier.
Turing soulève lui la question « que peut-on calculer ? ».
