Discuter:Fonction récursive

Un article de Wikipédia, l'encyclopédie libre.

	Fonction récursive fait partie du projet Informatique, qui a pour but d'enrichir le contenu de Wikipédia sur les sujets liés à l'informatique. Si vous voulez participer, vous pouvez modifier cet article ou visiter la page du projet où vous pourrez vous joindre au projet et consulter la liste des tâches et des objectifs. Le portail informatique pourrait aussi vous intéresser.
À évaluer	Cet article a été classé comme d'Avancement ? selon le Tableau d'évaluation du projet. (Voir les statistiques)
À évaluer	Cet article a été classé comme d'Importance ? selon le Tableau d'évaluation du projet. (Contester?)

[modifier] Une première discussion

On trouve sur Wikipédia les chapitres suivants :

Fonction récursive

Fonction partielle récursive

Fonction calculable

Fonction semi-calculable

Fonction récursive primitive

Comme récursive <=> calculable, il conviendrait de fusionner ces deux chapitres.

Comme partielle récursive <=> semi-calculable, il conviendrait également de fusionner ces deux chapitres.

Enfin, comme il n'existe pas de processus de décision permettant de dire si une fonction est calculable ou semi-calculable, la question se pose même si ces cinq chapitres ne doivent pas être réduits à deux seulement :

les fonctions récursives (au sens large)

les fonctions récursives primitives

Theon 31 décembre 2005 à 10:42 (CET)

J'ai complété la partie "calculabilité" de façon à en faire une page expliquant rapidement les notions et pointant sur des articles parlant de "récursif", "récursion", "récursivement", qui devraient être plus détaillés que l'article présent et dont certains sont à écrire. J'ai ajouté pour la partie calculabilité un historique (à vérifier dans les détails) tentant d'expliquer l'origine de la terminologie et les rapports entre les deux notions. Excepté pour l'article présent, je suis d'accord avec Theon, deux autres articles sont utiles.

fonction calculable (regroupant également fonction semi-calculable et fonction partielle récursive)

fonction récursive primitive

plus probablement des articles ad hoc pour certaines définitions particulières des fonctions calculables (cf liens rouges de cet article) : ça risque d'être lourd de tout mettre dans un même article. Proz 27 août 2006 à 22:47 (CEST)

[modifier] Hiérarchie de fonctions récursives

Où parle-t-on des hiérarchies de fonctions récursives, dont la hiérarchie de Grzegorczyk, la hiérarchie de Hardy, la hiérarchie lente, etc. ? Pierre de Lyon 7 novembre 2007 à 19:00 (CET)

Je ne les ai jamais vues (si ça existait on devrait y accéder par fonction d'Ackermann, à mon avis il n'y a rien). Proz 7 novembre 2007 à 22:16 (CET)

Ma question aurait dû être « Où devrait-on en parler ? ». Pierre de Lyon

J'avais mal interprété (mais si je comprends bien tu souhaites te lancer là dedans ?). Ca mérite largement un article à part, non ? C'est sûr qu'il faut déjà un titre, hiérarchies sous-récursives (comment traduis-tu "sub recursive hierarchies" ?) ? J'ai l'impression que ça n'existe même pas sur "en". Proz 8 novembre 2007 à 10:36 (CET)

Je ne souhaite pas me lancer dans un article, maintenant, mais je me disais qu'il fallait en parler quelque part. Pierre de Lyon 10 novembre 2007 à 12:07 (CET)

[[fonction primitive récursive (même si ça "déborde") ? Fonction d'Ackermann (idem) ?11 novembre 2007 à 16:25 (CET)