In computability theory, traditionally called recursion theory, a set S of natural numbers is called recursively enumerable, computably enumerable, semidecidable, provable or Turing-recognizable if: There is an algorithm that, when given an input number, eventually halts if and only if the input is an element of S. Or, equivalently, There is an algorithm that enumerates the members of S. That means that its output is simply a list of the members of S: s1, s2, s3, ... .

PropertyValue
dbpprop:abstract
  • In computability theory, traditionally called recursion theory, a set S of natural numbers is called recursively enumerable, computably enumerable, semidecidable, provable or Turing-recognizable if: There is an algorithm that, when given an input number, eventually halts if and only if the input is an element of S. Or, equivalently, There is an algorithm that enumerates the members of S. That means that its output is simply a list of the members of S: s1, s2, s3, ... . If necessary, this algorithm may run forever. The first condition suggests why the term semidecidable is sometimes used; the second suggests why computably enumerable is used. The abbreviations r.e. and c.e. are often used, even in print, instead of the full phrase. In computational complexity theory, the complexity class containing all recursively enumerable sets is RE. In recursion theory, the lattice of r.e. sets under inclusion is denoted <math>\mathcal{E}.
  • Die rekursive Aufzählbarkeit ist ein Begriff aus der Berechenbarkeitstheorie. Er gibt Aufschluss darüber, ob sich die Elemente einer vorgegebenen Menge schrittweise von einem Computer erzeugen lassen.
  • Se denomina recursivamente enumerable (r. e. ) a un conjunto, dentro de la teoría de la computabilidad, si existe una función computable g(x) que esté definida únicamente para aquellos números naturales que pertenecen a B: <math>B = \{ x \in \mathbb{N} \mid g(x) = \downarrow \}</math>
  • 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'un fonction calculable (il faut ajouter l'ensemble vide à la dernière définition pour avoir tout à fait l'équivalence). La notion se généralise aux couples et n-uplets d'entiers et de façon plus générale aux objets qui peuvent se coder dans les entiers, mots d'un langage, formules logiques etc. Par exemple on montre que l'ensemble des programmes informatiques que l'on peut écrire dans un langage donné, ou que l'ensemble des théorèmes d'une théorie finiment axiomatisable est récursivement énumérable. Les ensembles récursifs, on dit aussi décidables, sont tous récursivement énumérables mais la réciproque est fausse, comme le montre l'indécidabilité du problème de l'arrêt, ou celle du problème de la décision. On montre que les ensembles récursivement énumérables d'entiers sont exactement les projetés des ensembles récursifs de couples d'entiers. En arithmétique on montre que les ensembles récursivement énumérables sont les ensembles définissables par divers types de formules n'utilisant essentiellement que des quantificateurs existentiels en tête, l'exemple le plus fin de ce genre de résultat étant la caractérisation de ces ensembles comme ensemble diophantiens, caractérisation qui conduit directement au théorème de Matiiassevitch.
  • Nella teoria della calcolabilità esistono due definizioni di insieme ricorsivamente enumerabile (spesso abbreviato in insieme r.e. ) o insieme semi-decidibile. Intuitivamente, un insieme numerabile <math>S si dice r.e. se esiste un algoritmo (o equivalentemente una funzione ricorsiva) che preso un certo input, termina (o è definita nel caso delle funzioni ricorsive) se e solo se l'input appartiene ad <math>S. Oppure, equivalentemente, che genera in output tutti e soli gli elementi di <math>S. La prima definizione è quella che più strettamente si riferisce al nome "insieme semi-decidibile", mentre la seconda al nome "ricorsivamente enumerabile" (la funzione ricorsiva infatti è detta in quel caso funzione enumeratrice). La classe degli insiemi ricorsivamente enumerabili è un sovrainsieme stretto degli insiemi ricorsivi.
  • 帰納的可算集合（きのうてきかさんしゅうごう、英: Recursively enumerable set）は、計算理論または再帰理論におけるある種の集合に付与された名前。自然数の集合 S について以下が成り立つ場合、その集合を指して帰納的可算、計算可枚挙、半決定可能、証明可能、チューリング-認識可能などと称する。 あるアルゴリズムに入力となる数を与えたとき、そのアルゴリズムが停止する必要十分条件が、その数が S の元であることである。 あるいは、これと同値だが、 S の元を枚挙するアルゴリズムが存在する。つまり、その出力は S の元のリスト s1, s2, s3, ... である。このアルゴリズムは必要ならば無限に動作する。 これが半決定可能集合 (semidecidable set) と時に呼ばれるのは前者の条件に由来する。また、計算可枚挙集合（computably enumerable set）という用語は後者の条件に由来する。略して r.e. あるいは c.e. と書くが、これは出版物にもよく出現する。 計算複雑性理論において、全ての帰納的可算集合を包含する複雑性クラスを RE と呼ぶ。再帰理論においては、 包含された r.e. 集合の束 (lattice) を <math>\mathcal{E} と書く。
  • Перечислимое множество — множество конструктивных объектов, элементы которого могут быть эффективно перенумерованы (возможно, с повторениями).
  • 在可计算性理论或更少称谓的递归论中，可数集合 S 被称为递归可枚举的、计算可枚举的、半可判定的或可证明的，如果 有一个算法，使得在给定一个输入，典型的是一个整数、一个整数的元组或一个字符的序列的时候，最终会停机，当且仅当输入是 S 的一个元素。 或者等价的说， 有"生成" S 的成员的算法。这意味着它的输出简单的是 S 成员的一个列表: s1, s2, s3, ... 如果需要它可以永远运行下去。 包含所有可递归枚举集合的复杂性类是 RE。 共同的编程意义会暗示出如何转换一种算法到等价的另一种算法。第一个条件暗示了为什么有时用术语半可判定的，而第二个条件暗示了为什么叫计算可枚举的。
dbpprop:hasPhotoCollection
rdfs:comment
  • In computability theory, traditionally called recursion theory, a set S of natural numbers is called recursively enumerable, computably enumerable, semidecidable, provable or Turing-recognizable if: There is an algorithm that, when given an input number, eventually halts if and only if the input is an element of S. Or, equivalently, There is an algorithm that enumerates the members of S. That means that its output is simply a list of the members of S: s1, s2, s3, ... .
  • Die rekursive Aufzählbarkeit ist ein Begriff aus der Berechenbarkeitstheorie. Er gibt Aufschluss darüber, ob sich die Elemente einer vorgegebenen Menge schrittweise von einem Computer erzeugen lassen.
  • Se denomina recursivamente enumerable (r. e. ) a un conjunto, dentro de la teoría de la computabilidad, si existe una función computable g(x) que esté definida únicamente para aquellos números naturales que pertenecen a B: <math>B = \{ x \in \mathbb{N} \mid g(x) = \downarrow \}</math>
  • 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'un fonction calculable (il faut ajouter l'ensemble vide à la dernière définition pour avoir tout à fait l'équivalence). La notion se généralise aux couples et n-uplets d'entiers et de façon plus générale aux objets qui peuvent se coder dans les entiers, mots d'un langage, formules logiques etc.
  • Nella teoria della calcolabilità esistono due definizioni di insieme ricorsivamente enumerabile (spesso abbreviato in insieme r.e. ) o insieme semi-decidibile. Intuitivamente, un insieme numerabile <math>S si dice r.e. se esiste un algoritmo (o equivalentemente una funzione ricorsiva) che preso un certo input, termina (o è definita nel caso delle funzioni ricorsive) se e solo se l'input appartiene ad <math>S.
  • Перечислимое множество — множество конструктивных объектов, элементы которого могут быть эффективно перенумерованы (возможно, с повторениями).
  • 在可计算性理论或更少称谓的递归论中，可数集合 S 被称为递归可枚举的、计算可枚举的、半可判定的或可证明的，如果 有一个算法，使得在给定一个输入，典型的是一个整数、一个整数的元组或一个字符的序列的时候，最终会停机，当且仅当输入是 S 的一个元素。 或者等价的说， 有"生成" S 的成员的算法。这意味着它的输出简单的是 S 成员的一个列表: s1, s2, s3, ...
rdfs:label
  • Recursively enumerable set
  • Rekursive Aufzählbarkeit
  • Conjunto recursivamente enumerable
  • Récursivement énumérable
  • Insieme ricorsivamente enumerabile
  • 帰納的可算集合
  • Перечислимое множество
  • 递归可枚举集合
owl:sameAs
skos:subject
foaf:page
is dbpprop:disambiguates of
is dbpprop:redirect of