ChapitreCalculabilité

Fonctions primitives récursives

Les fonctions primitives récursives sont obtenues à partir de fonctions élémentaires par composition et par récurrence primitive. Elles contiennent toute l'arithmétique usuelle et les codages des suites finies par des entiers, sur lesquels repose toute la théorie.

Toutes sont totales, et elles ne suffisent pas à décrire tous les calculs : la fonction d'Ackermann, calculable par un procédé évident, croît plus vite que chacune d'elles.