Pourquoi les fonctions calculables sont-elles également appelées fonctions récursives?

Dans la théorie de la calculabilité, les fonctions calculables sont également appelées fonctions récursives. Au moins à première vue, ils n'ont rien de commun avec ce que vous appelez "récursif" dans la programmation quotidienne (c'est-à-dire les fonctions qui s'appellent elles-mêmes).

Quelle est la signification réelle de récursif dans le contexte de la calculabilité? Pourquoi ces fonctions sont-elles appelées "récursives"?

Autrement dit: quel est le lien entre les deux sens de la «récursivité»?

Définissez quelques fonctions de base:

• fonction zéro

  $$zero: \mathbb{N} \rightarrow \mathbb{N} : x \mapsto 0$$

• fonction successeur

  $$succ: \mathbb{N} \rightarrow \mathbb{N} : x \mapsto x + 1$$

• fonction de projection

$$p_i^n: \mathbb{N}^n \rightarrow \mathbb{N} : (x_1, x_2, \dots, x_n) \mapsto x_i$$

À partir de maintenant, j'utiliserai pour indiquer (x1,x2,…,xn$\bar{x_n}$$(x_1, x_2, \dots, x_n)$

Définissez une composition:

Fonctions données

• N k → $g_1, g_2, \dots, g_m$ chacun avec signature$\mathbb{N}^k \rightarrow \mathbb{N}$
• $f : \mathbb{N}^m \rightarrow \mathbb{N}$

Construisez la fonction suivante:

$$\begin{align} h: \mathbb{N}^k \rightarrow \mathbb{N}: \bar{x_k} \mapsto h(\bar{x_k}) = f ( & g_1(\bar{x_k}), g_2(\bar{x_k}), \dots, g_m(\bar{x_k}) ) \end{align}$$

Définissez la récursion primitive:

Fonctions données

• $f: \mathbb{N}^k \rightarrow \mathbb{N}$
• $g: \mathbb{N}^{k+2} \rightarrow \mathbb{N}$

Construisez la fonction suivante (par morceaux):

$$h : \mathbb{N}^{k+1} \rightarrow \mathbb{N} : \\ (\bar{x_k}, y + 1) \mapsto \begin{cases} f(\bar{x_k}), & y + 1 = 0 \\ g (\bar{x_k}, y, h(\bar{x_k}, y)), & y + 1 > 0 \end{cases}$$

---

Toutes les fonctions qui peuvent être faites en utilisant des compositions et une récursion primitive sur des fonctions de base , sont appelées récursives primitives . On l'appelle ainsi par définition. Bien qu'il existe un lien avec des fonctions qui s'appellent elles-mêmes, il n'est pas nécessaire d'essayer de les lier les unes aux autres. Vous pourriez considérer la récursivité comme un homonyme.

Cette définition et construction ci-dessus a été construite par Gödel (quelques autres personnes étaient également impliquées) dans une tentative de capturer toutes les fonctions qui sont calculables, c'est-à-dire qu'il existe une machine de Turing pour cette fonction. Notez que le concept d'une machine de Turing n'était pas encore décrit, ou qu'il était au moins très vague.

(Un) heureusement, quelqu'un appelé Ackermann est venu et a défini la fonction suivante:

• $Ack : \mathbb{N}^2 \rightarrow \mathbb{N}$
• $Ack(0, y) = y+1$
• $Ack(x+1, 0) = Ack(x, 1)$
• $Ack(x+1, y+1) = Ack(x, Ack(x+1,y))$

Cette fonction est calculable, mais il n'y a aucun moyen de la construire en utilisant uniquement les constructions ci-dessus! (ie n'est pas récursif primitif) Cela signifie que Gödel et son groupe n'ont pas réussi à capturer toutes les fonctions calculables dans leur construction!$Ack$

Gödel a dû étendre sa classe de fonctions pour que puisse être construit. Il l'a fait en définissant ce qui suit:$Ack$

Minimisation illimitée

• $g : \mathbb{N}^k \rightarrow \mathbb{N}$
• SI ALORS AUTRE n'est pas défini.$\left[f(\bar{x_k}, y) = 0 \text{ AND } \\f(\bar{x_k}, z) \text{ is defined } \forall z < y \text{ AND } \\f(\bar{x_k}, z)\neq 0\right]$
  
  $g(\bar{x_k}) = y$
  
  $g(\bar{x_k})$

Ce dernier peut être difficile à saisir, mais cela signifie essentiellement que est la plus petite racine de (si une racine existe).$g((x_1, x_2, \dots, x_k))$$f$

---

Toutes les fonctions qui peuvent être construites avec toutes les constructions définies ci-dessus sont appelées récursives . Encore une fois, le nom récursif est juste par définition, et il n'a pas nécessairement de corrélation avec les fonctions qui s'appellent. Vraiment, considérez-le comme un homonyme.

Les fonctions récursives peuvent être des fonctions récursives partielles ou des fonctions récursives totales . Toutes les fonctions récursives partielles sont des fonctions récursives totales. Toutes les fonctions récursives primitives sont totales. Comme exemple d'une fonction récursive partielle qui n'est pas totale, considérons la minimisation de la fonction successeur. La fonction successeur n'a pas de racine, donc sa minimisation n'est pas définie. Un exemple de fonction récursive totale (qui utilise la minimisation) est .$Ack$

Maintenant, Gödel était capable de construire la fonction avec sa classe élargie de fonctions. En fait, chaque fonction qui peut être calculée par une machine de Turing, peut être représentée en utilisant les constructions ci-dessus et vice versa, chaque construction peut être représentée par une machine de Turing.$Ack$

Si vous êtes intrigué, vous pouvez essayer d'agrandir la classe de Gödel. Vous pouvez essayer de définir «l'opposé» de la minimisation illimitée. Autrement dit, la maximisation illimitée , c'est-à-dire la fonction qui trouve la plus grande racine. Cependant, vous pouvez trouver que le calcul de cette fonction est difficile (impossible). Vous pouvez lire le problème du castor occupé , qui essaie d'appliquer une maximisation illimitée.

Les fondateurs de la théorie de la calculabilité étaient des mathématiciens. Ils ont fondé ce qu'on appelle maintenant la théorie de la calculabilité avant qu'il n'y ait d'ordinateurs. Comment les mathématiciens définissaient-ils les fonctions qui pouvaient être calculées? Par des définitions récursives!

Il y avait donc une fonction récursive avant tout autre modèle de calcul comme les machines de Turing ou le calcul lambda ou les machines à registres. Les gens ont donc appelé ces fonctions des fonctions récursives. Le fait qu'ils se soient avérés être exactement ce que les machines Turing et d'autres modèles peuvent calculer est un événement ultérieur (principalement prouvé par Kleene).

Nous avons la définition simple d'une fonction récursive qui est maintenant appelée fonction récursive primitive . Il n'y avait pas assez de généralités (par exemple la fonction d'Ackermann), donc les gens ont développé des notions plus générales comme les fonctions récursives et les fonctions récursives générales de Herbrand-Gödel qui capturaient toutes les fonctions calculables (en supposant la thèse de l'Église). Church a affirmé que son modèle de calcul lambda capturait toutes les fonctions calculables. Beaucoup de gens, et en particulier Gödel, n'étaient pas convaincus que ceux-ci capturent toutes les fonctions qui peuvent être calculées. Jusqu'à l'analyse du calcul par Turing et l'introduction de son modèle de machine.$\mu$

Nom du champ utilisé pour la théorie de la récursivité. Cependant, il y a eu une poussée réussie au cours des dernières décennies pour changer le nom en quelque chose de plus attrayant de la théorie de la récursivité à quelque chose de plus informatique (vs mathy). En conséquence, le domaine est maintenant appelé théorie de la calculabilité. Cependant, si vous regardez des livres, des articles, des conférences, etc. dans les premières décennies, ils sont appelés théorie de la récursivité et non théorie de la calculabilité. Même le titre du livre de Soare de 1987 (qui était la principale personne à l'origine de la tentative de changer le nom en théorie de la calculabilité) est "Ensembles et degrés énumérables récursivement".

Si vous voulez en savoir plus sur l'histoire un endroit amusant et bon à lire est le premier chapitre de la théorie de la récursivité classique par Odifreddi.

Robert Soare a écrit un essai sur cette question. Selon lui, le terme de fonctions récursives (générales) a été inventé par Gödel, qui les a définies en utilisant une sorte de récursivité mutuelle. Le nom est resté, mais plus tard, d'autres définitions équivalentes ont été trouvées.

Pour plus d'informations, je recommande l'essai de Soare.

au lieu de mettre un long commentaire a décidé d'ajouter une réponse:

Parce qu'elles sont définies de manière récursive , c'est-à-dire que " des fonctions plus complexes sont définies en termes de fonctions précédemment définies et plus simples "

Ce type de procédure itérative ou incrémentale crée des fonctions bien définies (au sens mathématique)

C'est le sens de la récursivité dans le langage mathématique. Voir ci-dessous comment cela se rapporte à la récursivité dans le langage de programmation.

Comparez cette procédure avec des techniques et des méthodes comme l' induction (mathématique) qui est également un exemple de récursivité en mathématiques.

La programmation a une veine mathématique aussi bien qu'une ingénierie.

Cette procédure (généralement constructive) est également appelée « amorçage » dans le langage des systèmes d'exploitation.

Cependant, une récursivité d'exécution de la même fonction (c'est-à-dire se calant pendant son exécution ), car elle doit (hmm, devrait) se produire sur des valeurs (ou arguments) déjà calculés, ou en d'autres termes, dans la partie de l'ensemble de résultats déjà calculée , est également récursif dans le sens ci-dessus, c'est-à-dire " défini par rapport aux fonctions précédemment définies (et leurs valeurs) "

Sinon n'est pas bien défini et conduit à des choses comme Stack Overflow :))))

Pour donner un autre exemple des systèmes d'exploitation, une récursivité d'exécution (s'appelle elle-même) peut être considérée comme l'analogue d'un redémarrage du système d'exploitation après une certaine mise à jour (par exemple, une mise à jour principale). De nombreux systèmes d'exploitation effectuent la procédure suivante:

1. un démarrage initial pour charger des routines de bas niveau (par exemple E / S)
2. faire les mises à jour nécessaires (en utilisant les routines de bas niveau)
3. redémarrer (effectivement, se ré-appeler), mais cette fois en chargeant les routines les plus complexes (ou même tout le système)

La belle réponse d' Auberon illustre plus en détail une telle procédure.