Linguagem recursivamente enumerável: diferenças entre revisões

sem resumo de edição
{{esboço-computação}}
{{mínimo}}
 
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. OUma décimolinguagem problema[http://pt.wikipedia.org/wiki/Problemas_de_Hilbert]é decomputável quando existe uma [[Hilbertmáquina de Turing]] abrangeque sempre pára, com "sim" ou 1" para instâncias positivas. Para cadeias fora da linguagem a classemáquina dasde linguagensTuring recursivamentepode enumeráveisnão parar, contrariamente ao que acontece com as [[linguagem recursiva|linguagens recursivas]].
 
O décimo [[Problemas de Hilbert|problema]] de [[Hilbert]] abrange a classe das linguagens recursivamente enumeráveis.
 
Toda [[linguagem recursiva]] é também recursivamente enumerável.
 
{{Teoria da computação}}
 
[[Categoria:Teoria da computação]]
 
[[cs:Rekurzivně spočetný jazyk]]
[[de:Rekursiv aufzählbare Sprache]]
[[en:Recursively enumerable language]]
[[es:Lenguaje recursivamente enumerable]]
[[hr:Rekurzivno prebrojiv jezik]]
[[it:Linguaggio ricorsivamente enumerabile]]
[[ja:帰納的可算言語]]
[[ko:재귀 열거 언어]]
[[pl:Język rekurencyjnie przeliczalny]]
[[ru:Рекурсивно перечислимый язык]]
[[sk:Rekurzívne vyčísliteľný jazyk]]
[[zh:递归可枚举语言]]
Utilizador anónimo