Recursively enumerable language (original) (raw)
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.
| Property | Value | |
|---|---|---|
| dbo:abstract | En matemàtiques, lògica i complexitat computacional un llenguatge formal és un llenguatge enumerable recursivament (o també parcialment decidible o Turing-computable) si és un subconjunt enumerable recursivament del conjunt de totes les paraules amb l'alfabet del llenguatge. Equivalentment, un llenguatge és enumerable recursivament si existeix una màquina de Turing que accepta i s'atura amb qualsevol cadena del llenguatge. Aquest tipus de llenguatges s'etiqueten com de tipus 0 en la jerarquia de Chomsky dels llenguatges formals. Tots els llenguatges regulars, lliures de context i recursius son llenguatges enumerables recursivament. La classe de tots els llenguatges enumerables recursivament s'anomena RE. (ca) Formální jazyk L je rekurzivně spočetný, jestliže pro něj existuje Turingův stroj (dále TS), který všechna slova z tohoto jazyka přijímá (akceptuje). Slova, která nejsou z tohoto jazyka, pak může buď odmítat, nebo se může stroj zacyklit. Tím se liší od rekurzivního jazyka, u kterého TS vždy zastaví (buď akceptuje nebo zamítne, i když mu je dáno slovo z doplňku jazyka). Pokud takový TS M existuje, říkáme, že TS M přijímá jazyk L. Množina je rekurzivně spočetná právě tehdy, pokud je definičním oborem nějaké ČRF. Také platí, že množina je rekurzivně spočetná právě tehdy, pokud je oborem hodnot nějaké ČRF. (cs) In der theoretischen Informatik ist eine rekursiv aufzählbare Sprache (auch bekannt als semientscheidbare oder erkennbare Sprache) dadurch definiert, dass es eine Turingmaschine gibt, die alle Wörter aus akzeptiert, aber keine Wörter, die nicht in liegen. Im Unterschied zu rekursiven Sprachen (entscheidbare Sprachen) muss bei den rekursiv aufzählbaren Sprachen die Turingmaschine nicht halten, wenn ein Wort nicht in 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; die entsprechenden Grammatiken sind die Typ-0-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 : die Menge der Codierungen all derjenigen Turingmaschinen, die auf ihrer eigenen Codierung als Eingabe nicht halten. D = { | M hält nicht auf } 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 ist, ist das Äquivalenzproblem für Turingmaschinen (Eq): die Menge von Paaren von zwei Turingmaschinen, die dieselbe Sprache akzeptieren. Eq = {# | 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 und ihr Komplement stets genau eine der folgenden drei Eigenschaften: * und sind rekursiv (und somit auch rekursiv aufzählbar). * und sind nicht rekursiv aufzählbar. * Genau eine der Sprachen und ist rekursiv aufzählbar (aber nicht rekursiv), die andere ist nicht rekursiv aufzählbar. (de) 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. (es) In mathematics, logic and computer science, a formal language is called recursively enumerable (also recognizable, partially decidable, semidecidable, Turing-acceptable or Turing-recognizable) if it is a recursively enumerable subset in the set of all possible words over the alphabet of the language, i.e., if there exists a Turing machine which will enumerate all valid strings of the language. Recursively enumerable languages are known as type-0 languages in the Chomsky hierarchy of formal languages. All regular, context-free, context-sensitive and recursive languages are recursively enumerable. The class of all recursively enumerable languages is called RE. (en) Un insieme A è detto ricorsivamente enumerabile quando esiste una f di cui A è il codominio. 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. (it) 재귀적 열거 가능 언어(再歸的列擧可能言語, 영어: Recursively enumerable language, 귀납적 가산 언어(歸納的可算言語)), 부분 결정성 언어 또는 튜링 수리성 언어는 계산 이론과 수리논리학에서 다루는 형식 언어의 종류로, 문자열의 집합의 재귀 열거인 부분집합이다. 촘스키 위계의 type-0 언어이기도 하다. 재귀 열거 언어의 모임을 RE라고 한다. (ko) 帰納的可算言語（きのうてきかさんげんご、英: Recursively enumerable language）は、数学・論理学・計算機科学における形式言語の一種である。部分決定性言語（Partially Decidable Language）、チューリング受理性言語（Turing-recognizable Language）とも呼ぶ。形式言語のチョムスキー階層におけるタイプ-0言語に相当する。全ての帰納的可算言語は複雑性クラス RE に属する。 (ja) 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 gramatykę kombinatoryczną. (pl) Em matemática, lógica e ciência da computação, uma linguagem recursivamente enumerável é um tipo de Linguagem formal que também é chamada de linguagem Turing-reconhecível. Também é conhecida como tipo-0 na hierarquia de Chomsky das linguagens formais. O décimo problema de Hilbert abrange a classe das linguagens recursivamente enumeráveis. (pt) В математике, логике и информатике рекурсивно перечислимым языком называется тип формального языка, также известный как частично разрешимый, или распознаваемый по Тьюрингу. В иерархии Хомского он известен как язык типа 0. Класс всех рекурсивно перечислимых языков называется RE. (ru) 在数学、逻辑和计算机科学中，递归可枚举语言是也叫做部分可判定语言或图灵可识别语言的形式语言类型。它在形式语言的乔姆斯基层级中叫做类型-0语言。所有递归可枚举语言的类叫做RE。 (zh) |
| dbo:wikiPageExternalLink | http://www.cs.colostate.edu/~massey/Teaching/cs301/RestrictedAccess/Slides/301lecture23.pdf | |
| dbo:wikiPageID | 54789 (xsd:integer) | |
| dbo:wikiPageLength | 4688 (xsd:nonNegativeInteger) | |
| dbo:wikiPageRevisionID | 1102289416 (xsd:integer) | |
| dbo:wikiPageWikiLink | dbr:Entscheidungsproblem dbr:Mortality_(computability_theory) dbr:Computable_function dbr:Concatenation dbr:Context-free_grammar dbr:Mathematics dbr:Context-free_language dbr:Context-sensitive_language dbr:Arithmetical_hierarchy dbr:Alphabet_(computer_science) dbr:Logic dbr:Closure_(mathematics) dbr:Complement_(complexity) dbr:Computably_enumerable_set dbr:Computer_science dbr:Post_correspondence_problem dbc:Mathematics_of_computing dbr:Formal_language dbr:Set_difference dbr:RE_(complexity) dbr:Recursion dbr:Regular_language dbr:Intersection_(set_theory) dbr:Halting_Problem dbc:Formal_languages dbc:Theory_of_computation dbr:Chomsky_hierarchy dbc:Alan_Turing dbr:Co-RE dbr:Recursive_language dbr:Infinity dbr:Recursively_enumerable_set dbr:Set_(mathematics) dbr:Kleene_star dbr:Turing_machine dbr:Union_(set_theory) dbr:Post's_theorem dbr:Subset dbr:Springer-Verlag dbr:Literal_string dbr:PWS_Publishing_Co | |
| dbp:wikiPageUsesTemplate | dbt:No_footnotes dbt:Short_description dbt:CZoo dbt:Formal_languages_and_grammars | |
| dct:subject | dbc:Mathematics_of_computing dbc:Formal_languages dbc:Theory_of_computation dbc:Alan_Turing | |
| rdf:type | yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Communication100033020 yago:Event100029378 yago:Language106282651 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:WikicatAlgorithms yago:WikicatFormalLanguages | |
| rdfs:comment | 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. (es) Un insieme A è detto ricorsivamente enumerabile quando esiste una f di cui A è il codominio. 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. (it) 재귀적 열거 가능 언어(再歸的列擧可能言語, 영어: Recursively enumerable language, 귀납적 가산 언어(歸納的可算言語)), 부분 결정성 언어 또는 튜링 수리성 언어는 계산 이론과 수리논리학에서 다루는 형식 언어의 종류로, 문자열의 집합의 재귀 열거인 부분집합이다. 촘스키 위계의 type-0 언어이기도 하다. 재귀 열거 언어의 모임을 RE라고 한다. (ko) 帰納的可算言語（きのうてきかさんげんご、英: Recursively enumerable language）は、数学・論理学・計算機科学における形式言語の一種である。部分決定性言語（Partially Decidable Language）、チューリング受理性言語（Turing-recognizable Language）とも呼ぶ。形式言語のチョムスキー階層におけるタイプ-0言語に相当する。全ての帰納的可算言語は複雑性クラス RE に属する。 (ja) 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 gramatykę kombinatoryczną. (pl) Em matemática, lógica e ciência da computação, uma linguagem recursivamente enumerável é um tipo de Linguagem formal que também é chamada de linguagem Turing-reconhecível. Também é conhecida como tipo-0 na hierarquia de Chomsky das linguagens formais. O décimo problema de Hilbert abrange a classe das linguagens recursivamente enumeráveis. (pt) В математике, логике и информатике рекурсивно перечислимым языком называется тип формального языка, также известный как частично разрешимый, или распознаваемый по Тьюрингу. В иерархии Хомского он известен как язык типа 0. Класс всех рекурсивно перечислимых языков называется RE. (ru) 在数学、逻辑和计算机科学中，递归可枚举语言是也叫做部分可判定语言或图灵可识别语言的形式语言类型。它在形式语言的乔姆斯基层级中叫做类型-0语言。所有递归可枚举语言的类叫做RE。 (zh) En matemàtiques, lògica i complexitat computacional un llenguatge formal és un llenguatge enumerable recursivament (o també parcialment decidible o Turing-computable) si és un subconjunt enumerable recursivament del conjunt de totes les paraules amb l'alfabet del llenguatge. Equivalentment, un llenguatge és enumerable recursivament si existeix una màquina de Turing que accepta i s'atura amb qualsevol cadena del llenguatge. La classe de tots els llenguatges enumerables recursivament s'anomena RE. (ca) Formální jazyk L je rekurzivně spočetný, jestliže pro něj existuje Turingův stroj (dále TS), který všechna slova z tohoto jazyka přijímá (akceptuje). Slova, která nejsou z tohoto jazyka, pak může buď odmítat, nebo se může stroj zacyklit. Tím se liší od rekurzivního jazyka, u kterého TS vždy zastaví (buď akceptuje nebo zamítne, i když mu je dáno slovo z doplňku jazyka). Pokud takový TS M existuje, říkáme, že TS M přijímá jazyk L. (cs) In der theoretischen Informatik ist eine rekursiv aufzählbare Sprache (auch bekannt als semientscheidbare oder erkennbare Sprache) dadurch definiert, dass es eine Turingmaschine gibt, die alle Wörter aus akzeptiert, aber keine Wörter, die nicht in liegen. Im Unterschied zu rekursiven Sprachen (entscheidbare Sprachen) muss bei den rekursiv aufzählbaren Sprachen die Turingmaschine nicht halten, wenn ein Wort nicht in 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. (de) In mathematics, logic and computer science, a formal language is called recursively enumerable (also recognizable, partially decidable, semidecidable, Turing-acceptable or Turing-recognizable) if it is a recursively enumerable subset in the set of all possible words over the alphabet of the language, i.e., if there exists a Turing machine which will enumerate all valid strings of the language. The class of all recursively enumerable languages is called RE. (en) | |
| rdfs:label | Llenguatge enumerable recursivament (ca) Rekurzivně spočetný jazyk (cs) Rekursiv aufzählbare Sprache (de) Lenguaje recursivamente enumerable (es) Linguaggio ricorsivamente enumerabile (it) 帰納的可算言語 (ja) 재귀 열거 언어 (ko) Język rekurencyjnie przeliczalny (pl) Recursively enumerable language (en) Linguagem recursivamente enumerável (pt) Рекурсивно перечислимый язык (ru) 递归可枚举语言 (zh) | |
| owl:sameAs | freebase:Recursively enumerable language yago-res:Recursively enumerable language wikidata:Recursively enumerable language dbpedia-ca:Recursively enumerable language dbpedia-cs:Recursively enumerable language dbpedia-de:Recursively enumerable language dbpedia-es:Recursively enumerable language dbpedia-fa:Recursively enumerable language dbpedia-hr:Recursively enumerable language dbpedia-it:Recursively enumerable language dbpedia-ja:Recursively enumerable language dbpedia-ko:Recursively enumerable language dbpedia-nn:Recursively enumerable language dbpedia-no:Recursively enumerable language dbpedia-pl:Recursively enumerable language dbpedia-pt:Recursively enumerable language dbpedia-ru:Recursively enumerable language dbpedia-sh:Recursively enumerable language dbpedia-sk:Recursively enumerable language dbpedia-sr:Recursively enumerable language dbpedia-zh:Recursively enumerable language https://global.dbpedia.org/id/9XV2 | |
| prov:wasDerivedFrom | wikipedia-en:Recursively_enumerable_language?oldid=1102289416&ns=0 | |
| foaf:isPrimaryTopicOf | wikipedia-en:Recursively_enumerable_language | |
| is dbo:wikiPageRedirects of | dbr:Nonrecursively_enumerable dbr:Recognizable_language dbr:Turing-acceptable_language dbr:Turing-recognizable_language dbr:Turing_recognizable dbr:R.e._language dbr:Partially_decidable_language dbr:Recursively_enumerable_languages dbr:Type-0_language | |
| is dbo:wikiPageWikiLink of | dbr:List_of_computability_and_complexity_topics dbr:List_of_formal_language_and_literal_string_topics dbr:Nonrecursively_enumerable dbr:Index_of_computing_articles dbr:Index_of_philosophy_articles_(R–Z) dbr:JFLAP dbr:List_of_mathematical_logic_topics dbr:Computability dbr:Cone_(formal_languages) dbr:Context-sensitive_grammar dbr:Combinatorics_on_words dbr:Complexity_class dbr:Computable_set dbr:Computably_enumerable_set dbr:Theory_of_computation dbr:Multi-track_Turing_machine dbr:Unrestricted_grammar dbr:Diophantine_set dbr:Formal_language dbr:Recognizable_language dbr:Abstract_family_of_languages dbr:Chomsky_hierarchy dbr:Recursive_language dbr:Automata_theory dbr:Polynomial_hierarchy dbr:Type_0 dbr:Universal_Turing_machine dbr:Van_Wijngaarden_grammar dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Outline_of_logic dbr:Rice's_theorem dbr:Turing-acceptable_language dbr:Turing-recognizable_language dbr:Turing_recognizable dbr:R.e._language dbr:Partially_decidable_language dbr:Recursively_enumerable_languages dbr:Type-0_language | |
| is foaf:primaryTopic of | wikipedia-en:Recursively_enumerable_language |