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

m (A migrar 14 interwikis, agora providenciados por Wikidata em d:q1073063)
{{esboço}}
 
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 [[Problemas de Hilbert|problema]] de [[Hilbert]] abrange a classe das linguagens recursivamente enumeráveis.
{{TOC}}
 
== Definições ==
 
 
[[Linguagem regular]], [[linguagem livre de contexto]] e linguagem recursiva são todas recursivamente enumeráveis.
 
O [[teorema de Post]] mostra que '''[[RE (complexidade)|RE]]''', juntamente com seu [[complemento (complexity)|complemento]] [[co-RE]], correspondem ao primeiro nível da [[hierarquia aritmética]].
 
== Propriedades de fecho ==
 
Note que as linguagens recursivamente enumeráveis '''não''' são fechadas sob diferença e complemento. A diferença ''L-P'' pode ou não ser recursivamente enumerável. Se L é recursivamente enumerável, então o complemento de L é recursivamente enumerável se e somente se L também for recursiva.
 
== Links externos ==
* [http://www.cs.colostate.edu/~massey/Teaching/cs301/RestrictedAccess/Slides/301lecture23.pdf Lecture slides]
 
== Referências ==
 
* Sipser, M. (1996), ''Introduction to the Theory of Computation'', PWS Publishing Co.
* Kozen, D.C. (1997), ''Automata and Computability'', Springer.
 
== Ligações externas ==
* [http://www.cs.colostate.edu/~massey/Teaching/cs301/RestrictedAccess/Slides/301lecture23.pdf Lecture slides]
 
{{Teoria da computação}}
 
{{esboço-computação}}
[[Categoria:Teoria da computação]]
41 895

edições