Discussion:Récursivement énumérable

Titre

A mon avis, ce titre, qui est un adjectif, n'est pas acceptable. Spedona 18 déc 2004 à 19:44 (CET)

réponse 3 ans et demi après : ensemble récursivement énumérable (inverser les deux) est peut-être mieux ?

Définition de Smullyan

J'ai un peu de mal à lire ce paragraphe, le vocabulaire n'esst pas très standard, je ne vois pas où sont définis précisément les termes (objet, opérateurs, prédicats fondamentaux). s'agit-il toujours d'entiers par ex. ? Il vaudrait mieux un article clair sur les systèmes de Post il me semble. S'il faut reprendre cet article (il y a à faire), je ferais bien disparaître le paragraphe. Proz (d) 24 mai 2008 à 15:18 (CEST)

12 ans après : personne ne touche à ce truc, maintenant séparés par un paragraphe étranger au sujet. C'est une interprétation, manifestemet assez perso, des définitions du livre de Smullyan, Theory of formal systems (sa thèse) dans un cas très particulier (les formules atomiques vraies de l'arithmétique). Je propose de l'effacer. Il y a maintenant ]].Système de Post. Par ailleurs il manque les définitions formelles standards. Proz (discuter) 20 avril 2020 à 12:23 (CEST)

Au sujet de l'équivalence des définitions de Turing de l'énumérabilité

Bonjour, ma remarque concerne le début de l'article tel qu'écrit aujourd'hui (12/04/2017). Je cite:

"En théorie de la calculabilité, un ensemble récursivement énumérable ou semi-décidable est un ensemble qui est le domaine de définition, ou, de façon équivalente, l'image d'une fonction calculable (il faut ajouter l'ensemble vide à la dernière définition pour avoir tout à fait l'équivalence)".

Mon avis est que cette définition doit être précisée:

En théorie de la calculabilité, un ensemble récursivement énumérable ou semi-décidable est un ensemble qui est le domaine de définition d'une fonction partielle calculable (autrement dit qui tolère des entrées hors-domaine pour lesquelles le calcul ne finis pas), ou, de façon équivalente, l'image d'une fonction totale calculable (autrement dit, ne tolère pas de calcul infini) (il faut ajouter l'ensemble vide à la dernière définition pour avoir tout à fait l'équivalence).

Pour le cas de la fonction partielle calculable, on obtient par la suite une fonction calculable par la méthode du déployeur universelle tel que décrit par la suite. Je n'ai pas encore compris l'intérêt de la présence de l'ensemble vide. Peux-être que sa compréhension invaliderais ma correction.

Je pense que dans le RI (résumé introductif), il faut s'en tenir à une définition solide et simple, compréhensible par un maximum de lecteurs. Le RI de en:Recursively_enumerable_set me semble exemplaire de ce point de vue. Complexifier le RI (qui est déjà trop complexe, avec l'ensemble vide etc..) en parlant de "fonction partielle", ou "totale calculable", va perdre 99% des lecteurs, alors que la notion de base est très simple et très compréhensible. Plus loin dans l'article, il est possible, et même nécessaire, de parler plus rigoureusement et aborder la définition formelle. Et dans ce cas le mieux est de se mettre d'accord sur une source plutôt que de proposer des définitions. --Jean-Christophe BENOIST (discuter) 12 avril 2017 à 09:51 (CEST)

Bonsoir, votre réponse me convient. Cordialement.

D'ailleurs si pas d'opposition, je reformulerais le RI de manière à rendre son début plus semblable à celui de en:Recursively_enumerable_set. Cordialement --Jean-Christophe BENOIST (discuter) 20 avril 2017 à 13:42 (CEST)

Je suis d'accord avec vous et avec Jean-Christophe Benoist. Le début de l'article actuel n'est pas la "définition" d'un ensemble RE. La définition donnée dans les livres de calculabilité est "Un ensemble est récursivement énumérable s'il est accepté par une machine de Turing." (1). Soit généralement une proposition comme "un ensemble récursivement énumérable s'il existe un algorithme qui énumère exactement les éléments de l'ensemble." (2). Je ne suis pas sûr mais il me semble que (2) donne le nom à "récursivement énumérable". Ca ne me choque pas que (2) soit le début de l'article. L'avantage de (2) c'est que c'est plus informel, plus compréhensible et demande la maîtrise de moins de notions. Bonne journée.--Fschwarzentruber (discuter) 20 avril 2017 à 14:07 (CEST)

Je découvre a posteriori cette discussion : j'ai corrigé la définition 2 que je n'ai pas trouvé dans le Delahaye, mais je me suis rendu compte après coup que je n'avais p pas la bonne édition (1994 et non 1999). Ceci dit telle qu'elle était rédigée, je n'étais pas sûr de comprendre. En tout cas ça faisait référence à une notion d'algorithme (avec effets de bord ?) que ne formalise pas la calculabilité, ou alors à un système formel ? Que dit réellement Delahaye ? Proz (discuter) 20 avril 2020 à 02:32 (CEST)

Je suis revenu en arrière (à peu près) sans être complètement convaincu, je pense que ça serait plus clair de dire quelque chose comme : dont il est possible d'énumérer les éléments par un procédé mécanique (ou algorithmique ?). Proz (discuter) 20 avril 2020 à 04:02 (CEST)

Bonjour, pour info ce que dit Delahaye, édition 94 (page 74) :

def 2 : A est récursivement énumérable ssi il existe une machine de Turing M_i telle que W_i = A.

def 2' : A est récursivement énumérable (r-é) ssi il existe un système formel correct et complet pour les énoncés de la forme "n est dans A".

--Epsilon0 ε₀ 20 avril 2020 à 05:03 (CEST)

Au départ, c'est moi qui a sourcé la seconde définition avec Delahaye, qui est équivalente à "il est possible d'énumérer les éléments par un procédé mécanique ou algorithmique" ([1]). La première définition mérite d'être sourcée en effet. Cette partie du RI est traduite de en:Recursively enumerable set en conséquence de la discussion ci-dessus. --Jean-Christophe BENOIST (discuter) 20 avril 2020 à 09:41 (CEST)

Oui j'ai l'édition 1994, la def. 2 du Delahaye est effectivement notre première définition : W_i est la notation standard (due à Kleene) pour le domaine de définition de la fonction φ_i définie par la machine de Turing de code i, ce pourquoi j'avais reporté la référence sur cette définition (je vois que c'est p 69 du livre de Delahaye). Par contre ça ne me paraissait pas évident que la définition 2' corresponde à celle donnée en second dans l'article: du coup j'ai pensé qu'il y en avait une autre dans l'édition 1999. Mais en fait la définition de système formel, qui est assez particulière, est donnée p 73 et effectivement ça colle en parlant de sortie. Proz (discuter) 20 avril 2020 à 11:38 (CEST)