In mathematics, logic and computer science, a recursively enumerable language is a type of formal language which is also called partially decidable or Turing-recognizable. It is known as a type-0 language in the Chomsky hierarchy of formal languages. The class of all recursively enumerable languages is called RE.

PropertyValue
dbpprop:abstract
  • In mathematics, logic and computer science, a recursively enumerable language is a type of formal language which is also called partially decidable or Turing-recognizable. It is known as a type-0 language in the Chomsky hierarchy of formal languages. The class of all recursively enumerable languages is called RE.
  • Eine rekursiv aufzählbare Sprache oder semientscheidbare Sprache L ist dadurch definiert, dass es eine Turingmaschine gibt, die alle Wörter aus L akzeptiert, aber keine Wörter, die nicht in L liegen. Im Unterschied zu rekursiven Sprachen oder entscheidbaren Sprachen muss bei den rekursiv aufzählbaren Sprachen die Turingmaschine nicht halten, wenn ein Wort nicht in L liegt. Das heißt, unter Umständen muss man auf die Lösung unendlich lange warten. Alle rekursiven Sprachen sind deshalb auch rekursiv aufzählbar. Rekursiv aufzählbare Sprachen bilden die oberste Stufe der Chomsky-Hierarchie und heißen deshalb auch Typ-0-Sprachen (oder Grammatiken). Sie können somit auch als all die Sprachen definiert werden, deren Wörter sich durch eine beliebige formale Grammatik ableiten lassen. Eines der wichtigsten Probleme, das rekursiv aufzählbar ist, aber nicht rekursiv, ist das so genannte Halteproblem. Ein nicht semi-entscheidbares Problem ist die so genannte Diagonalsprache D: die Menge der Codierungen all derer Turingmaschinen, die auf ihrer eigenen Codierung als Eingabe nicht halten. D = {<M> | M hält nicht auf <M>} Auch das Komplement des (semi-entscheidbaren) Halteproblems ist nicht semi-entscheidbar, während das Komplement der Diagonalsprache semi-entscheidbar ist. In der Tat ist das Komplement des Halteproblems eine Erweiterung der Diagonalsprache und das Komplement der Diagonalsprache ein Spezialfall des Halteproblems. Ein Beispiel für eine Sprache, für die weder sie selbst noch ihr Komplement semi-entscheidbar sind, ist das Äquivalenzproblem für Turingmaschinen (Eq): die Menge von Paaren von zwei Turingmaschinen, die dieselbe Sprache akzeptieren. Eq = {<M1>#<M2> | L(M1) = L(M2)} Diese Eigenschaft der Nicht-semi-Entscheidbarkeit folgt leicht daraus, dass das Halteproblem auf dieses Problem und auch auf dessen Komplement reduzierbar ist. Sie gilt allerdings bereits für deterministische Kellerautomaten anstelle von allgemeinen Turingmaschinen. Allgemein gilt für eine Sprache L und ihr Komplement K(L) stets genau eine der folgenden drei Eigenschaften: L und K(L) sind rekursiv (und somit auch rekursiv aufzählbar). L und K(L) sind nicht rekursiv aufzählbar. Genau eine der Sprachen L und K(L) ist rekursiv aufzählbar (aber nicht rekursiv), die andere ist nicht rekursiv aufzählbar.
  • Rekurzivně spočetný jazyk je taková množina slov nad abecedou Σ, pro niž existuje Turingův stroj, který pro všechna slova z Σ buď slovo akceptuje, nebo zamítá, či cyklí. Jedná se o pojem z teorie vyčíslitelnosti. Množina je rekurzivně spočetná právě tehdy, pokud je oborem hodnot nějaké ČRF
  • En matemáticas, lógica e informática, un lenguaje recursivamente enumerable es un tipo de lenguaje formal que es también llamado parcialmente decidible o Turing-computable. Son conocidos como lenguajes tipo-0 en la Jerarquía de Chomsky.
  • Un insieme A è detto ricorsivamente enumerabile quando esiste una funzione di enumerazione f tale che A è l'insieme delle immagini di f (cioè A è il codominio di f). Essendoci una corrispondenza biunivoca tra l'insieme delle funzioni calcolabili e l'insieme dei programmi in un qualsiasi linguaggio di programmazione, un insieme è quindi ricorsivamente enumerabile se è possibile generare i suoi elementi attraverso un programma per calcolatore (per la tesi di Church-Turing è indifferente il linguaggio di programmazione scelto). Un insieme ricorsivamente enumerabile è anche detto semidecidibile in quanto è possibile stabilire (in un tempo non quantificabile) se un elemento generico appartiene ad A, ma non è possibile stabilire la non appartenenza di un elemento.
  • 帰納的可算言語（英: Recursively enumerable language）とは、数学・論理学・計算機科学における形式言語の一種である。部分決定性言語（Partially Decidable Language）、チューリング受理性言語（Turing-recognizable Language）とも呼ぶ。形式言語のチョムスキー階層におけるタイプ-0言語に相当する。全ての帰納的可算言語は複雑性クラス RE に属する。
  • Język rekurencyjnie przeliczalny (ang. recursively enumerable language) to język formalny określany jako język klasy 0 w hierarchii Chomsky'ego, który generowany jest przez gramatyki rekurencyjnie przeliczalne.
  • Uma linguagem formal é dita recursivamente enumerável se ela é computável, ou seja, se existe um algoritmo que reconhece esta linguagem mas que não necessariamente para qualquer entrada. Uma linguagem é computável quando existe uma máquina de Turing que sempre pára, com "sim" ou 1" para instâncias positivas. Para cadeias fora da linguagem a máquina de Turing pode não parar, contrariamente ao que acontece com as linguagens recursivas. O décimo problema de Hilbert abrange a classe das linguagens recursivamente enumeráveis. Toda linguagem recursiva é também recursivamente enumerável.
  • В математике, логике и информатике, рекурсивно перечислимым языком называется тип формального языка, также известный как частично разрешимый или распознаваемый по Тьюрингу. В иерархии Хомского он известен как язык типа 0. Класс всех рекурсивно перечислимых языков называется RE.
  • 在数学、逻辑和计算机科学中，递归可枚举语言是也叫做部分可判定语言或图灵可识别语言的形式语言类型。它在形式语言的乔姆斯基层级中叫做类型-0 语言。所有递归可枚举语言的类叫做 RE。
dbpprop:czooProperty
  • Class RE
  • R re
dbpprop:hasPhotoCollection
dbpprop:wikiPageUsesTemplate
rdf:type
rdfs:comment
  • In mathematics, logic and computer science, a recursively enumerable language is a type of formal language which is also called partially decidable or Turing-recognizable. It is known as a type-0 language in the Chomsky hierarchy of formal languages. The class of all recursively enumerable languages is called RE.
  • Eine rekursiv aufzählbare Sprache oder semientscheidbare Sprache L ist dadurch definiert, dass es eine Turingmaschine gibt, die alle Wörter aus L akzeptiert, aber keine Wörter, die nicht in L liegen. Im Unterschied zu rekursiven Sprachen oder entscheidbaren Sprachen muss bei den rekursiv aufzählbaren Sprachen die Turingmaschine nicht halten, wenn ein Wort nicht in L liegt. Das heißt, unter Umständen muss man auf die Lösung unendlich lange warten.
  • Rekurzivně spočetný jazyk je taková množina slov nad abecedou Σ, pro niž existuje Turingův stroj, který pro všechna slova z Σ buď slovo akceptuje, nebo zamítá, či cyklí. Jedná se o pojem z teorie vyčíslitelnosti. Množina je rekurzivně spočetná právě tehdy, pokud je oborem hodnot nějaké ČRF
  • En matemáticas, lógica e informática, un lenguaje recursivamente enumerable es un tipo de lenguaje formal que es también llamado parcialmente decidible o Turing-computable. Son conocidos como lenguajes tipo-0 en la Jerarquía de Chomsky.
  • Un insieme A è detto ricorsivamente enumerabile quando esiste una funzione di enumerazione f tale che A è l'insieme delle immagini di f (cioè A è il codominio di f).
  • 帰納的可算言語（英: Recursively enumerable language）とは、数学・論理学・計算機科学における形式言語の一種である。部分決定性言語（Partially Decidable Language）、チューリング受理性言語（Turing-recognizable Language）とも呼ぶ。形式言語のチョムスキー階層におけるタイプ-0言語に相当する。全ての帰納的可算言語は複雑性クラス RE に属する。
  • Język rekurencyjnie przeliczalny (ang. recursively enumerable language) to język formalny określany jako język klasy 0 w hierarchii Chomsky'ego, który generowany jest przez gramatyki rekurencyjnie przeliczalne.
  • Uma linguagem formal é dita recursivamente enumerável se ela é computável, ou seja, se existe um algoritmo que reconhece esta linguagem mas que não necessariamente para qualquer entrada. Uma linguagem é computável quando existe uma máquina de Turing que sempre pára, com "sim" ou 1" para instâncias positivas. Para cadeias fora da linguagem a máquina de Turing pode não parar, contrariamente ao que acontece com as linguagens recursivas.
  • В математике, логике и информатике, рекурсивно перечислимым языком называется тип формального языка, также известный как частично разрешимый или распознаваемый по Тьюрингу. В иерархии Хомского он известен как язык типа 0.
  • 在数学、逻辑和计算机科学中，递归可枚举语言是也叫做部分可判定语言或图灵可识别语言的形式语言类型。它在形式语言的乔姆斯基层级中叫做类型-0 语言。所有递归可枚举语言的类叫做 RE。
rdfs:label
  • Recursively enumerable language
  • Rekursiv aufzählbare Sprache
  • Rekurzivně spočetný jazyk
  • Lenguaje recursivamente enumerable
  • Loch
  • Linguaggio ricorsivamente enumerabile
  • 帰納的可算言語
  • Język rekurencyjnie przeliczalny
  • Linguagem recursivamente enumerável
  • Рекурсивно перечислимый язык
  • 递归可枚举语言
owl:sameAs
skos:subject
foaf:page
is dbpprop:redirect of
is owl:sameAs of