Théorie de la calculabilité

La théorie de la calculabilité (appelée aussi parfois théorie de la récursion) est un domaine de la logique mathématique et de l'informatique théorique. La calculabilité (parfois appelée « computationnalité », de l'anglais computability) cherche d'une part à identifier la classe des fonctions qui peuvent être calculées à l'aide d'un algorithme et d'autre part à appliquer ces concepts à des questions fondamentales des mathématiques. Une bonne appréhension de ce qui est calculable et de ce qui ne l'est pas permet de voir les limites des problèmes que peuvent résoudre les ordinateurs. Mais la notion de calculabilité ne se limite pas aux fonctions. On peut parler également de nombres calculables (réels ou complexes). Intuitivement, une fonction est une fonction calculable s'il existe une méthode précise qui, étant donné un argument , permet d'obtenir l'image en un nombre fini d'étapes. Plusieurs formalisations mathématiques de ce que peut être une méthode de calcul existent et on peut montrer qu'un grand nombre d'entre elles (fonctions récursives, machine de Turing, lambda-calcul, machine à compteurs, automate cellulaire, etc.) sont équivalentes, c'est-à-dire qu'elles définissent exactement les mêmes fonctions calculables. Formellement, une fonction calculable est donc une fonction calculable selon l'une de ces définitions, par exemple le lambda-calcul. La thèse de Church énonce que les définitions mathématiques équivalentes ci-dessus capturent bien le concept intuitif de méthode de calcul défini par des moyens finis, dit d'une autre façon . Alan Turing définit un nombre réel calculable comme étant un nombre dont l'expression décimale est calculable avec des moyens finis. Autrement dit, il existe une machine de Turing qui permet d'énumérer la suite de tous les chiffres de ce nombre (en un temps infini). Par extension, un nombre complexe est calculable si sa partie réelle et sa partie imaginaire sont simultanément calculables.