| dbo:abstract
|
- طبقًا لنظرية الحوسبة، والمعروفة عادةً بنظرية العدد أو التكرار، فإن مجموعة الأعداد الطبيعية S تكون مرقّمة بشكلٍ عوديّ (تراجعي)، وقابلة للعد أو الإحصاء حسابيًا، وتكون قابلة للحسم جزئيًا، ويمكن إثباتها بالبرهان أو يمكن لآلات تورنغ تمييزها والتعرُّف عليها بسهولة إذا:
* كان هناك خوارزمية ما بحيث تكون مجموعة الأرقام المدْخَلة فيها والتي تنتهي وتتوقّف عندها هذه الخوارِزِمية هي نفسها مجموعة الأرقام الموجودة في S. أو، بشكلٍ مساوٍ،
* إذا كان هناك خوارِزِميّة تسرد وتحصي بشكلٍ دقيق عناصر المجموعة S. فإنّ هذا يعني أنّ نواتج هذه الخوارِزِميّة ما هي إلا قائمة بعناصر المجموعة S: s1، s2، s3.... وإذا لزِم الأمر، فإن هذه الخوارِزِميّة قد لا تتوقّف أبدًا. فالحالة الأولى توضِّح لماذا يُسْتَخدَم مصطلح «قابلة للحسم جزئيًا» في بعض الأحيان؛ في حين أنّ الحالة الثانية تشير إلى سبب استخدام مصطلح «قابلة للإحصاء حسابيًا». وغالبًا ما تُسْتَخدَم الاختصارات r.e. (مرقّمة بشكلٍ عوديّ)، و c.e. (قابلة للإحصاء حسابيًا)، بدلاً من العبارة كاملة حتى في الوسائل المطبوعة.وفي نظرية التعقيد الحسابي، تكون فئة التعقيد التي تحتوي على جميع المجموعات التي يمكن إحصاء تكرارها (أو المرقّمة بشكلٍ عوديّ) هي أيضًا فئة مرقّمة بشكلٍ عوديّ. أمّا في النظرية العودية أو الحاسوبية، فإنّ شبكة المجموعات المرقّمة بشكلٍ عوديّ والتي تكون تحت الإدراج يُرمَز لها بـ . (ar)
- Als rekursiv aufzählbare Menge (auch semi-entscheidbare Menge, positiv semi-entscheidbare Menge, halb-entscheidbare Menge, berechenbar aufzählbare Menge, kurz r.e., c.e.) wird in der Berechenbarkeitstheorie eine Menge von natürlichen Zahlen bezeichnet, wenn es einen Algorithmus gibt, der die Elemente dieser Menge aufzählt.Äquivalent ist diese Charakterisierung:Es gibt einen Algorithmus, der 1 ausgibt, wann immer die Eingabe ein Element der betreffenden Menge ist, und auf anderen Eingaben nie hält. Jede entscheidbare Menge ist rekursiv aufzählbar, aber es gibt rekursiv aufzählbare Mengen, die nicht entscheidbar sind. Mengen von anderen Objekten als natürlichen Zahlen heißen rekursiv aufzählbar, wenn sie sich durch Gödelisierung in eine rekursiv aufzählbare Menge natürlicher Zahlen übersetzen lässt. In der Literatur taucht gelegentlich der Begriff der berechenbaren Menge auf. Dieser Begriff wird uneinheitlich verwendet. Es können damit entscheidbare Mengen oder rekursiv aufzählbare Mengen gemeint sein. (de)
- In computability theory, a set S of natural numbers is called computably enumerable (c.e.), recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable if:
* There is an algorithm such that the set of input numbers for which the algorithm halts is exactly S. Or, equivalently,
* There is an algorithm that enumerates the members of S. That means that its output is simply a list of all the members of S: s1, s2, s3, ... . If S is infinite, this algorithm will run forever. The first condition suggests why the term semidecidable is sometimes used. More precisely, if a number is in the set, one can decide this by running the algorithm, but if the number is not in the set, the algorithm runs forever, and no information is returned. A set that is "completely decidable" is a computable set. The second condition suggests why computably enumerable is used. The abbreviations c.e. and r.e. are often used, even in print, instead of the full phrase. In computational complexity theory, the complexity class containing all computably enumerable sets is RE. In recursion theory, the lattice of c.e. sets under inclusion is denoted . (en)
- 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: (es)
- En théorie de la calculabilité, un ensemble E d'entiers naturels est récursivement énumérable ou semi-décidable si :
* il existe un algorithme qui prend un entier naturel en entrée, et qui s'arrête exactement sur les entiers de E ; ou, de manière équivalente :
* il existe un procédé algorithmique qui, au cours de son fonctionnement, énumère en sortie tous les entiers de E et seulement ceux-ci (il est possible, et même nécessaire quand E est infini, qu'il ne s'arrête pas). Cette notion, définie pour les nombres entiers, 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. Par exemple l'ensemble des programmes informatiques qui s'arrêtent est un ensemble récursivement énumérable et non récursif de par l'indécidabilité du problème de l'arrêt. Dit autrement si un ensemble est décidable, il est semi-décidable, mais les deux notions ne sont pas équivalentes. 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 ensembles diophantiens, caractérisation qui conduit directement au théorème de Matiiassevitch. En théorie de la complexité, la classe des langages récursivement énumérables est notée RE. (fr)
- 帰納的可算集合（きのうてきかさんしゅうごう、英: Recursively enumerable set）は、計算理論または再帰理論におけるある種の集合に付与された名前。自然数の集合 S について以下が成り立つ場合、その集合を指して帰納的可算、計算可枚挙、半決定可能、証明可能、チューリング-認識可能などと称する。
* あるアルゴリズムに入力となる数を与えたとき、そのアルゴリズムが停止する必要十分条件が、その数が S の元であることである。 あるいは、これと同値だが、
* S の元を枚挙するアルゴリズムが存在する。つまり、その出力は S の元のリスト s1, s2, s3, ... である。このアルゴリズムは必要ならば無限に動作する。 これが半決定可能集合 (semidecidable set) と時に呼ばれるのは前者の条件に由来する。また、計算可枚挙集合（computably enumerable set）という用語は後者の条件に由来する。略して r.e. あるいは c.e. と書くが、これは出版物にもよく出現する。 計算複雑性理論において、全ての帰納的可算集合を包含する複雑性クラスを RE と呼ぶ。再帰理論においては、 包含関係に基づく r.e. 集合の束 (lattice) を と書く。 (ja)
- 계산 이론에서 재귀적 열거 가능 집합(Recursively enumberable set), 귀납적 가산 집합(歸納的可算集合)은 다음 조건을 만족하는 집합 S를 말한다.
* 집합 S의 모든 원소에 대해서만 진리값 참을 내놓는 알고리즘이 존재한다. (r.e.) 이 정의는 다음과 동치이다.
* 어떤 알고리즘을 이용해 집합 S의 원소를 처음부터 하나씩 열거(자연수로의 단사 함수)해 모두 세어 나갈 수 있다. 곧 출력이 s1, s2, s3... 와 같은 식으로 S의 원소의 목록이다. 이 알고리즘은 필요하다면 무한한 시간 동안 작동할 수도 있다. 계산 복잡도 이론에서 이와 같은 집합을 모임 RE (복잡도)로 분류한다. (c.e.) 이외에 열거 가능 집합(enumerable set), 계산 열거 가능 집합(computably enumerable set), 준결정성 집합(semidecidable set), 튜링 인식 가능 집합(Turing-recognizable set) 등으로도 불린다. 줄여서 r.e. 또는 c.e.라고 쓰이기도 한다. (ko)
- 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 si dice r.e. se esiste un algoritmo (o equivalentemente una funzione ricorsiva totale) che:
* preso un certo input, se l'input appartiene a allora esso termina (o è definita nel caso delle funzioni ricorsive). Oppure, equivalentemente,
* genera in output tutti e soli gli elementi di . 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. (it)
- Na Teoria da computabilidade, tradicionalmente chamada teoria da recursão, um conjunto S de números naturais é chamado recursivamente enumerável, computavelmente enumerável, semi-decidível, demonstrável ou Turing-reconhecível se:
* Existe um algoritmo tal que o conjunto de números de entrada para qual o algoritmo pára é exatamente o conjunto de números em S. Ou, equivalentemente,
* Existe um algoritmo que enumera os membros de S. Isso significa que sua saída é simplesmente uma lista de membros de S: s1, s2, s3, ... . Se necessário, esse algoritmo pode rodar para sempre. A primeira condição sugere porque o termo semi-decidível às vezes é usado; o segundo sugere porque computavelmente enumerável é usado. Na teoria de complexidade computacional, a classe de complexidade que contém todos os conjuntos recursivamente enumeráveis é RE (recursivamente enumerável). Na teorica da recursão, o Reticulado de conjuntos recursivamente enumeráveis sobre inclusão é denominado . (pt)
- Перечисли́мое мно́жество (эффекти́вно перечислимое, рекурси́вно перечислимое, полуразреши́мое множество) — множество (например, натуральных чисел), все элементы которого могут быть получены с помощью некоторого алгоритма. Дополнение перечислимого множества называется корекурсивно перечислимым. Всякое перечислимое множество является арифметическим. Корекурсивно перечислимое множество может не быть перечислимым, но всегда является арифметическим. Перечислимые множества соответствуют уровню , а корекурсивно перечислимые — уровню Всякое разрешимое множество является перечислимым. Перечислимое множество является разрешимым тогда и только тогда, когда его дополнение также перечислимо. Другими словами, множество является разрешимым в том и только том случае, когда оно и перечислимо, и корекурсивно перечислимо. Подмножество перечислимого множества может не быть перечислимым (и даже может не быть арифметическим). Совокупность всех перечислимых подмножеств является счётным множеством, а совокупность всех неперечислимых подмножеств — несчётным. (ru)
- 递归可枚举集合（英語：Recursively enumerable set）是可计算性理论或更狭义的递归论中的一个概念。可数集合S被称为是递归可枚举、计算可枚举的、半可判定的或可证明的，如果
* 存在一个算法，只有当输入是S中的元素时，算法才会中止。 或者等价的说，
* 存在一个算法，可以将S中的成员枚举出来。也就是说该算法的输出就是 S 的成员列表: s1, s2, s3, ... 如果需要它可以永远运行下去。 包含所有可递归枚举集合的复杂性类是 。 共同的编程意义会暗示出如何转换一种算法到等价的另一种算法。第一种情况说明了为什么有时说半可判定的，而第二种情况说明了为什么叫计算可枚举的。 (zh)
|
| rdfs:comment
|
- 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: (es)
- 帰納的可算集合（きのうてきかさんしゅうごう、英: Recursively enumerable set）は、計算理論または再帰理論におけるある種の集合に付与された名前。自然数の集合 S について以下が成り立つ場合、その集合を指して帰納的可算、計算可枚挙、半決定可能、証明可能、チューリング-認識可能などと称する。
* あるアルゴリズムに入力となる数を与えたとき、そのアルゴリズムが停止する必要十分条件が、その数が S の元であることである。 あるいは、これと同値だが、
* S の元を枚挙するアルゴリズムが存在する。つまり、その出力は S の元のリスト s1, s2, s3, ... である。このアルゴリズムは必要ならば無限に動作する。 これが半決定可能集合 (semidecidable set) と時に呼ばれるのは前者の条件に由来する。また、計算可枚挙集合（computably enumerable set）という用語は後者の条件に由来する。略して r.e. あるいは c.e. と書くが、これは出版物にもよく出現する。 計算複雑性理論において、全ての帰納的可算集合を包含する複雑性クラスを RE と呼ぶ。再帰理論においては、 包含関係に基づく r.e. 集合の束 (lattice) を と書く。 (ja)
- 계산 이론에서 재귀적 열거 가능 집합(Recursively enumberable set), 귀납적 가산 집합(歸納的可算集合)은 다음 조건을 만족하는 집합 S를 말한다.
* 집합 S의 모든 원소에 대해서만 진리값 참을 내놓는 알고리즘이 존재한다. (r.e.) 이 정의는 다음과 동치이다.
* 어떤 알고리즘을 이용해 집합 S의 원소를 처음부터 하나씩 열거(자연수로의 단사 함수)해 모두 세어 나갈 수 있다. 곧 출력이 s1, s2, s3... 와 같은 식으로 S의 원소의 목록이다. 이 알고리즘은 필요하다면 무한한 시간 동안 작동할 수도 있다. 계산 복잡도 이론에서 이와 같은 집합을 모임 RE (복잡도)로 분류한다. (c.e.) 이외에 열거 가능 집합(enumerable set), 계산 열거 가능 집합(computably enumerable set), 준결정성 집합(semidecidable set), 튜링 인식 가능 집합(Turing-recognizable set) 등으로도 불린다. 줄여서 r.e. 또는 c.e.라고 쓰이기도 한다. (ko)
- 递归可枚举集合（英語：Recursively enumerable set）是可计算性理论或更狭义的递归论中的一个概念。可数集合S被称为是递归可枚举、计算可枚举的、半可判定的或可证明的，如果
* 存在一个算法，只有当输入是S中的元素时，算法才会中止。 或者等价的说，
* 存在一个算法，可以将S中的成员枚举出来。也就是说该算法的输出就是 S 的成员列表: s1, s2, s3, ... 如果需要它可以永远运行下去。 包含所有可递归枚举集合的复杂性类是 。 共同的编程意义会暗示出如何转换一种算法到等价的另一种算法。第一种情况说明了为什么有时说半可判定的，而第二种情况说明了为什么叫计算可枚举的。 (zh)
- طبقًا لنظرية الحوسبة، والمعروفة عادةً بنظرية العدد أو التكرار، فإن مجموعة الأعداد الطبيعية S تكون مرقّمة بشكلٍ عوديّ (تراجعي)، وقابلة للعد أو الإحصاء حسابيًا، وتكون قابلة للحسم جزئيًا، ويمكن إثباتها بالبرهان أو يمكن لآلات تورنغ تمييزها والتعرُّف عليها بسهولة إذا:
* كان هناك خوارزمية ما بحيث تكون مجموعة الأرقام المدْخَلة فيها والتي تنتهي وتتوقّف عندها هذه الخوارِزِمية هي نفسها مجموعة الأرقام الموجودة في S. أو، بشكلٍ مساوٍ، (ar)
- In computability theory, a set S of natural numbers is called computably enumerable (c.e.), recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable if:
* There is an algorithm such that the set of input numbers for which the algorithm halts is exactly S. Or, equivalently,
* There is an algorithm that enumerates the members of S. That means that its output is simply a list of all the members of S: s1, s2, s3, ... . If S is infinite, this algorithm will run forever. (en)
- Als rekursiv aufzählbare Menge (auch semi-entscheidbare Menge, positiv semi-entscheidbare Menge, halb-entscheidbare Menge, berechenbar aufzählbare Menge, kurz r.e., c.e.) wird in der Berechenbarkeitstheorie eine Menge von natürlichen Zahlen bezeichnet, wenn es einen Algorithmus gibt, der die Elemente dieser Menge aufzählt.Äquivalent ist diese Charakterisierung:Es gibt einen Algorithmus, der 1 ausgibt, wann immer die Eingabe ein Element der betreffenden Menge ist, und auf anderen Eingaben nie hält. Jede entscheidbare Menge ist rekursiv aufzählbar, aber es gibt rekursiv aufzählbare Mengen, die nicht entscheidbar sind. (de)
- En théorie de la calculabilité, un ensemble E d'entiers naturels est récursivement énumérable ou semi-décidable si :
* il existe un algorithme qui prend un entier naturel en entrée, et qui s'arrête exactement sur les entiers de E ; ou, de manière équivalente :
* il existe un procédé algorithmique qui, au cours de son fonctionnement, énumère en sortie tous les entiers de E et seulement ceux-ci (il est possible, et même nécessaire quand E est infini, qu'il ne s'arrête pas). En théorie de la complexité, la classe des langages récursivement énumérables est notée RE. (fr)
- 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 si dice r.e. se esiste un algoritmo (o equivalentemente una funzione ricorsiva totale) che:
* preso un certo input, se l'input appartiene a allora esso termina (o è definita nel caso delle funzioni ricorsive). Oppure, equivalentemente,
* genera in output tutti e soli gli elementi di . La classe degli insiemi ricorsivamente enumerabili è un sovrainsieme stretto degli insiemi ricorsivi. (it)
- Перечисли́мое мно́жество (эффекти́вно перечислимое, рекурси́вно перечислимое, полуразреши́мое множество) — множество (например, натуральных чисел), все элементы которого могут быть получены с помощью некоторого алгоритма. Дополнение перечислимого множества называется корекурсивно перечислимым. Всякое перечислимое множество является арифметическим. Корекурсивно перечислимое множество может не быть перечислимым, но всегда является арифметическим. Перечислимые множества соответствуют уровню , а корекурсивно перечислимые — уровню (ru)
- Na Teoria da computabilidade, tradicionalmente chamada teoria da recursão, um conjunto S de números naturais é chamado recursivamente enumerável, computavelmente enumerável, semi-decidível, demonstrável ou Turing-reconhecível se:
* Existe um algoritmo tal que o conjunto de números de entrada para qual o algoritmo pára é exatamente o conjunto de números em S. Ou, equivalentemente,
* Existe um algoritmo que enumera os membros de S. Isso significa que sua saída é simplesmente uma lista de membros de S: s1, s2, s3, ... . Se necessário, esse algoritmo pode rodar para sempre. (pt)
|
