Discussion:Ensemble récursif
- Admissibilité
- Neutralité
- Droit d'auteur
- Article de qualité
- Bon article
- Lumière sur
- À faire
- Archives
- Commons
Cet article est indexé par les projets Informatique et Mathématiques.
Les projets ont pour but d’enrichir le contenu de Wikipédia en aidant à la coordination du travail des contributeurs. Vous pouvez modifier directement cet article ou visiter les pages de projets pour prendre conseil ou consulter la liste des tâches et des objectifs.
| Avancement | Importance | pour le projet | |
|---|---|---|---|
| Ébauche | Faible |  | Informatique (discussion • critères • liste • stats • hist. • comité • stats vues) |
| À évaluer |  | Mathématiques (discussion • critères • liste • stats • hist. • comité • stats vues) | |
Cet article ne comporte pas de liste de tâches suggérées. Vous pouvez saisir une liste de tâches à accomplir (par exemple sous forme d'une liste à puces), puis sauvegarder. Vous pouvez aussi consulter la page d'aide.
Qualité article[modifier le code]
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)
Changements[modifier le code]
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
re-changement[modifier le code]
Heu non, en fait, elle est vrai, j'avait lu trop vite la phrase, je la remet. Je laisses néanmoins les ajouts effectués.
Cependant, il est vrai qu'à la lecture on a l'impression que ces phrases se contredisent, ce qui choque un peu. Du coup, je change la formulation afin de lisser ceci. Jick01 (d) 21 janvier 2011 à 10:52 (CET)
Exemple avec la suite de Syracuse[modifier le code]
"il existe peut-être une valeur de k > 0 telle qu'on ne puisse pas décider de l'appartenance de 1 (en un temps fini) dans le multiensemble des termes de la suite de Syracuse de premier terme u0 = k."
J'ai enlevé cette affirmation car elle est fausse.
- k étant donné en entrée de l'algorithme, savoir si 1 appartient au multiensemble est peut-être algorithmiquement indécidable.
- k étant fixé et i étant donné en entrée, savoir si i appartient au multiensemble est peut-être algorithmiquement indécidable (c'est ce que dit la phrase précédente dans l'article).
- Par contre, si k est fixé, savoir si pour ce k, il existe un algorithme indiquant si 1 appartient au multiensemble n'a pas de sens : le problème n'a pas d'entrée !
Cela doit venir d'une confusion entre les deux sens de Décidabilité. Il pourrait exister k tel que 1 n'appartient pas au multiensemble sans que ce soit décidable, disons dans ZFC, au sens logique. Aucune démonstration dans ZFC n'aboutirait alors à ce résultat. Mais dans cet article c'est hors-sujet.