Développement #379

Titre : Fonctions calculables en temps récursif primitif, énumérations des fonctions récursives primitives

Contenu : Une fonction $f:\mathbb{N}\rightarrow\mathbb{N}$ est récursive primitive si et seulement si elle est calculable en temps récursif primitif par une machine de Turing. \r\rApplication : Il existe une fonction $\phi:\mathbb{N}^2\rightarrow\mathbb{N}$ récursive telle que $\{\phi(i,\cdot)|i\in\mathbb{N}\}$ est exactement l'ensemble $\{f:\mathbb{N}\rightarrow\mathbb{N}|f \text{est récursive primitive}\}$. De plus une telle application est nécessairement non récursive primitive.

Créé le : 23/07/2026 12:42

Mis à jour : 23/07/2026 12:42