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

Détails/Enoncé :

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.

Application : 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.

Recasages pour l'année 2019 :

Versions :

  • Auteur :
  • Remarque :
    Très peu sourcé mais relativement bien fait dans ce TD : https://www.normalesup.org/~srideau/docs/class/LogEns/Td09_corr.pdf

    Il est peut être nécessaire de travailler avec d'autres notations et il est impératif de traiter la fonction d'Ackermann et de savoir qu'il existe une machine de Turing universelle. La notion de domination est nécessaire pour pouvoir obtenir un schéma $\mu$ borné et rester dans le cadre des fonction récursives primitives.