PR (complexidade): diferenças entre revisões

8 bytes adicionados ,  16 de julho de 2016
pequenas correções
(Criado ao traduzir a página "PR (complexity)")
 
(pequenas correções)
'''PR''' é a classe de complexidade de todas as [[Função recursiva primitiva|funções recursivas primitivas]] , ou, equivalentemente, o conjunto de todas as [[Linguagem formal|linguagens formais]] que pode ser decididodecididas por uma tal função. Isso inclui a adição, multiplicação, potência, [[tetração]], etc.
 
A [[função de Ackermann]] é um exemplo de função que ''não'' é primitiva recursiva primitiva, mostrando que PR éesta estritamente contidocontida em [[R (complexidade)|R]] (Cooper, 2004:88).
 
Por outro lado, podemos "enumerar" qualquer [[Conjuntos recursivamente enumeráveis|conjunto recursivamente enumerável]] (veja também a sua classe de complexidade [[RE (complexidade)|RE]]) por uma função primitiva recursiva primitiva no seguinte sentido: dada uma entrada (''M'', ''k''), onde ''M'' é uma [[máquina de Turing]] e ''k'' é um número inteiro, se ''M'' pára dentro de ''k'' passos, dê ''M ''como saída; caso contrário, dê nada como saída. Então, a união das saídas, através de todas as entradas possíveis (''M'', ''k''), é exatamente o conjunto dedas ''M'' que páraparam.
 
PR estritamente contém [[ELEMENTAR (complexidade)|ELEMENTAR]].
 
== Ligações externas ==
* ''[[Classe de complexidade|AO complexidadeZoo dode Zoocomplexidade]]''<span>: </span>[https://complexityzoo.uwaterloo.ca/Complexity_Zoo:P#pr PR].
[[Categoria:Classes de complexidade]]
Utilizador anónimo