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

Conteúdo apagado Conteúdo adicionado

Em linha

Revisão das 15h41min de 16 de julho de 2016

PR é a classe de complexidade de todas as funções recursivas primitivas , ou, equivalentemente, o conjunto de todas as linguagens formais que pode ser decididas 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 é recursiva primitiva, mostrando que PR esta estritamente contida em R (Cooper, 2004:88).

Por outro lado, podemos "enumerar" qualquer conjunto recursivamente enumerável (veja também a sua classe de complexidade RE) por uma função 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 das M que param.

PR estritamente contém ELEMENTAR.

Referências

S. Barry Cooper (2004), Teoria da Computabilidade, Chapman & Hall. ISBN 1-58488-237-9.
Herbert Enderton (2011), Teoria da Computabilidade, Academic Press. ISBN 978-0-12-384-958-8

Ligações externas

O Zoo de complexidade: PR.

@@ Linha 1: / Linha 1: @@
-'''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 decidido por uma tal função. Isso inclui a adição, multiplicação, potência, [[tetração]], etc.
+'''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 decididas 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, mostrando que PR é estritamente contido em [[R (complexidade)|R]] (Cooper, 2004:88).
+A [[função de Ackermann]] é um exemplo de função que ''não'' é recursiva primitiva, mostrando que PR esta estritamente contida 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]]) uma função primitiva recursiva no seguinte sentido: dada uma entrada (''M'',&#x20;''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'',&#x20;''k''), é exatamente o conjunto de ''M'' que pára.
+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 recursiva primitiva no seguinte sentido: dada uma entrada (''M'',&#x20;''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'',&#x20;''k''), é exatamente o conjunto das ''M'' que param.
 PR estritamente contém [[ELEMENTAR (complexidade)|ELEMENTAR]].
@@ Linha 12: / Linha 12: @@
 == Ligações externas ==
-* ''[[Classe de complexidade|A complexidade do Zoo]]''<span>: </span>[https://complexityzoo.uwaterloo.ca/Complexity_Zoo:P#pr PR].
+* ''[[Classe de complexidade|O Zoo de complexidade]]''<span>: </span>[https://complexityzoo.uwaterloo.ca/Complexity_Zoo:P#pr PR].
 [[Categoria:Classes de complexidade]]