A recursive language in mathematics, logic and computer science is a type of formal language which is also called decidable or Turing-decidable. The class of all recursive languages is often called R, although this name is also used for the class RP. This type of language was not defined in the Chomsky hierarchy of.

PropertyValue
dbpprop:abstract
  • A recursive language in mathematics, logic and computer science is a type of formal language which is also called decidable or Turing-decidable. The class of all recursive languages is often called R, although this name is also used for the class RP. This type of language was not defined in the Chomsky hierarchy of.
  • Eine Formale Sprache <math>L \subseteq \Sigma^*</math> heißt rekursiv (entscheidbar), wenn eine Turingmaschine M existiert, die auf allen Eingaben <math>w \in \Sigma^*</math> hält, d. h <math>H_M = \Sigma^*</math>, und jede Eingabe <math>w \in \Sigma^*</math> genau dann akzeptiert, wenn <math>w \in L</math> ist. Die Nicht-Rekursivität einer Sprache kann man mittels Satz von Rice nachweisen. Wenn es keine Turingmaschine gibt, die ein solches Entscheidungsproblem löst, so gibt es nach der Churchschen These überhaupt keinen Algorithmus für das Problem. Man beschränkt sich bei dieser Definition auf Entscheidungsprobleme, also auf Probleme, deren Antwort nur Ja oder Nein sein kann. Es stellt sich aber heraus, dass sie trotz dieser Einschränkung meist ausreichend ist, da die zu Entscheidungsproblemen gehörenden Berechnungsprobleme meist nicht schwieriger zu lösen sind. Der Vorteil ist, dass man alle Entscheidungsprobleme auf Sprachen zurückführen kann; diese können u.a. durch Grammatiken beschrieben werden: Eine Eingabe w ist für ein Entscheidungsproblem P genau dann eine Lösung, wenn w in der zu P gehörigen Sprache L liegt. Somit besteht eine Brücke zwischen dem erzeugenden Grammatik-Modell und dem akzeptierenden Automaten-Modell. In der Tat kann man zu jeder Chomsky-Grammatik-Klasse eine Automatenklasse finden, die genau die Sprachen der jeweiligen Klasse akzeptiert und umgekehrt. Die Menge der rekursiven Sprachen ist echte Teilmenge der Chomsky-Typ-0 (oder rekursiv aufzählbaren) Sprachen und echte Obermenge der Chomsky-Typ-1 Sprachen: Das Halteproblem ist rekursiv aufzählbar (Typ 0), aber nicht rekursiv Es gibt Sprachen, die rekursiv, aber nicht kontextsensitiv (Typ 1) sind. Es ist kein Automatenmodell bekannt, welches genau die rekursiven Sprachen beschreibt. Die Menge der rekursiven Sprachen stimmt mit allen bisher vorgeschlagenen Berechenbarkeitsmodellen überein. Hierzu gehören insbesondere die Goto-Berechenbarkeit und die While-Berechenbarkeit welche aus den gängigsten Programmierkonstrukten am Computer hervorgehen. Diese Übereinstimmungen sind Ausgangspunkt für die Churchsche These. Der Unterschied zu den rekursiv aufzählbaren Sprachen ist definitionsgemäß, dass eine Turingmaschine für eine rekursive Sprache immer halten muss, während eine für eine rekursiv aufzählbare Sprache nur halten muss, wenn das Wort in der Sprache liegt.
  • Jazyk je rekurzivní, pokud Turingův stroj slova z tohoto jazyka pouze akceptuje anebo zamítá (nezacyklí se), tzn. vždy skončí po konečném počtu kroků.
  • Un lenguaje recursivo en matemáticas, lógica e informática, es un tipo de lenguaje formal que también es llamado recursivo, decidible o Turing-decidible. Se caracterizan porque para cada uno de ellos existe una máquina de Turing que aceptará cualquier palabra del lenguaje y parará siempre.
  • En mathématiques, en logique et en informatique, un langage récursif est un type de langage formel qui est aussi appelé récursif, décidable, ou Turing-decidable.
  • In matematica, logica e informatica teorica, i linguaggi decidibili o ricorsivi sono una classe di linguaggi formali che corrisponde alla classe dei problemi decidibili. Esistono due definizioni principali equivalenti per questa classe: Un linguaggio ricorsivo è un linguaggio per il quale esiste una macchina di Turing che, data una qualsiasi stringa di input, termina accettando la stringa se essa appartiene al linguaggio, e termina rifiutando la stringa in caso contrario. Un linguaggio ricorsivo è un sottoinsieme ricorsivo dell'insieme di tutte le possibili stringhe sull'alfabeto del linguaggio. Tutti i linguaggi ricorsivi sono ricorsivamente enumerabili. Sono ricorsivi tutti i linguaggi regolari, libero dal contesto e sensibili al contesto. È degno di nota il fatto che questa categoria non abbia un corrispondente diretto nella classificazione di Chomsky.
  • 帰納言語（英: Recursive language）とは、数学・論理学・計算機科学における形式言語の一種である。決定性言語(Decidable Language)、チューリング決定性言語(Turing-decidable Language)とも呼ぶ。全ての帰納言語の属する複雑性クラスをRと呼ぶが、RPクラスを Rと呼ぶこともある。 このクラスの言語はチョムスキー階層では定義されていない（Chomsky 1959）。
  • Język rekurencyjny to klasa języków formalnych. W teorii złożoności oznaczana jest literą R. Klasa języków rekurencyjnych nie została uwzględniona w hierarchii Chomsky'ego.
  • Uma linguagem é dita recursiva ou Turing-decidível quando existe uma Máquina de Turing que sempre para com "SIM" para instâncias positivas e "NÃO" para instâncias negativas do programa, isto é, que não entra em loop. Recursividade
  • В математической логике и информатике рекурсивный язык — тип формального языка, также называемый разрешимым или разрешимым по Тьюрингу. Класс всех рекурсивных языков часто обозначается через R, хотя это же обозначение используется для класса RP. Этот тип языка не определен в иерархии Хомского .
  • 在数学、逻辑和计算机科学中，递归语言或遞迴語言是也叫做可判定语言或图灵可判定语言的形式语言类型。所有递归语言的类经常被称为 R。这种语言类型在乔姆斯基层级中没有定义。
dbpprop:harvProperty
  • Chomsky
  • 1959 (xsd:integer)
dbpprop:hasPhotoCollection
dbpprop:wikiPageUsesTemplate
rdf:type
rdfs:comment
  • A recursive language in mathematics, logic and computer science is a type of formal language which is also called decidable or Turing-decidable. The class of all recursive languages is often called R, although this name is also used for the class RP. This type of language was not defined in the Chomsky hierarchy of.
  • Eine Formale Sprache <math>L \subseteq \Sigma^*</math> heißt rekursiv (entscheidbar), wenn eine Turingmaschine M existiert, die auf allen Eingaben <math>w \in \Sigma^*</math> hält, d. h <math>H_M = \Sigma^*</math>, und jede Eingabe <math>w \in \Sigma^*</math> genau dann akzeptiert, wenn <math>w \in L</math> ist. Die Nicht-Rekursivität einer Sprache kann man mittels Satz von Rice nachweisen.
  • Jazyk je rekurzivní, pokud Turingův stroj slova z tohoto jazyka pouze akceptuje anebo zamítá (nezacyklí se), tzn. vždy skončí po konečném počtu kroků.
  • Un lenguaje recursivo en matemáticas, lógica e informática, es un tipo de lenguaje formal que también es llamado recursivo, decidible o Turing-decidible. Se caracterizan porque para cada uno de ellos existe una máquina de Turing que aceptará cualquier palabra del lenguaje y parará siempre.
  • En mathématiques, en logique et en informatique, un langage récursif est un type de langage formel qui est aussi appelé récursif, décidable, ou Turing-decidable.
  • In matematica, logica e informatica teorica, i linguaggi decidibili o ricorsivi sono una classe di linguaggi formali che corrisponde alla classe dei problemi decidibili. Esistono due definizioni principali equivalenti per questa classe: Un linguaggio ricorsivo è un linguaggio per il quale esiste una macchina di Turing che, data una qualsiasi stringa di input, termina accettando la stringa se essa appartiene al linguaggio, e termina rifiutando la stringa in caso contrario.
  • 帰納言語（英: Recursive language）とは、数学・論理学・計算機科学における形式言語の一種である。決定性言語(Decidable Language)、チューリング決定性言語(Turing-decidable Language)とも呼ぶ。全ての帰納言語の属する複雑性クラスをRと呼ぶが、RPクラスを Rと呼ぶこともある。 このクラスの言語はチョムスキー階層では定義されていない（Chomsky 1959）。
  • Język rekurencyjny to klasa języków formalnych. W teorii złożoności oznaczana jest literą R. Klasa języków rekurencyjnych nie została uwzględniona w hierarchii Chomsky'ego.
  • Uma linguagem é dita recursiva ou Turing-decidível quando existe uma Máquina de Turing que sempre para com "SIM" para instâncias positivas e "NÃO" para instâncias negativas do programa, isto é, que não entra em loop. Recursividade
  • В математической логике и информатике рекурсивный язык — тип формального языка, также называемый разрешимым или разрешимым по Тьюрингу. Класс всех рекурсивных языков часто обозначается через R, хотя это же обозначение используется для класса RP.
  • 在数学、逻辑和计算机科学中，递归语言或遞迴語言是也叫做可判定语言或图灵可判定语言的形式语言类型。所有递归语言的类经常被称为 R。这种语言类型在乔姆斯基层级中没有定义。
rdfs:label
  • Recursive language
  • Rekursive Sprache
  • Rekurzivní jazyk
  • Lenguaje recursivo
  • Langage récursif
  • Linguaggio ricorsivo
  • 帰納言語
  • Język rekurencyjny
  • Linguagem recursiva
  • Рекурсивный язык
  • 递归语言
owl:sameAs
skos:subject
foaf:page
is dbpprop:disambiguates of
is dbpprop:redirect of
is owl:sameAs of