Aller au contenu

Calculabilité et complexité/Introduction

Leçons de niveau 17
Une page de Wikiversité, la communauté pédagogique libre.
Début de la boite de navigation du chapitre
Introduction
Icône de la faculté
Chapitre no 1
Leçon : Calculabilité et complexité
Retour auSommaire
Chap. suiv. :Rappel sur la notion de langage
fin de la boite de navigation du chapitre
En raison de limitations techniques, la typographie souhaitable du titre, « Calculabilité et complexité : Introduction
Calculabilité et complexité/Introduction
 », n'a pu être restituée correctement ci-dessus.

La calculabilité est une notion convergente de deux domaines :

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 ? ».