Discuter:Ensemble récursif

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

	Ensemble récursif 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.
Ébauche	Cet article a été classé comme d'Avancement ébauche 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?)

Après avori cobnsulter quelques articles, et en consultant l'historique de cette page, j'en finis par me demander si wikipedia peut fonctionner sur ce genre de sujet. L'article a été manifestement dans un état plus satisfaisant que l'actuel.

- La référence aux entiers a disparu

- la référence à la fonction caractéristique récursive aussi, (mais on a laissé le "En d'autres termes" qui y fait référence !)

- une référence à la hiérarchie arithmétique : sujet peut-être un peu technique dans ce genre d'article, mais surtout c'est faux (Delta_1 et non Sigma_0)

j'effectue une modification dans le sens d'un retour a un état antérieur.

Proz 10 avril 2006 à 18:47 (CEST)

[modifier] Changements

L'article comportait l'affirmation : "Un ensemble est récursif si et seulement s'il est récursivement énumérable ainsi que son complémentaire." qui est fausse. En effet, un langage récursif est récursivement énumérable. Mais un langage récursivement énumérable n'est pas nécessairement récursif. Voir notemment le lien que j'ai ajouté pour un contre exemple :

http://www.liafa.jussieu.fr/~carton/Enseignement/Complexite/MasterInfo/Cours/recursif.html