Théorie

Calculabilité

Les fonctions récursives sont obtenues à partir de fonctions élémentaires de ${\mathbb N}$ par composition, récurrence primitive et recherche non bornée. Ce sont exactement les fonctions calculées par les machines à registres, et un programme, codé par un entier, peut en simuler tout autre.

Le problème de l'arrêt est indécidable : l'ensemble des programmes qui s'arrêtent sur leur propre code est récursivement énumérable sans être récursif. Il en découle le théorème de Rice et une forme du premier théorème d'incomplétude : l'ensemble des énoncés vrais dans $\mathbb N$ n'est pas récursivement énumérable. Avec l'arithmétisation de la syntaxe, qui code les formules et les démonstrations par des entiers, il s'ensuit que l'arithmétique de Peano n'est pas complète.