PR (complexidade)
Neste artigo, exploraremos PR (complexidade) e seu impacto na sociedade atual. PR (complexidade) é um tema de interesse e debate há muito tempo, e a sua relevância continua a ser evidente em diversas áreas. Serão analisadas diferentes perspectivas e abordagens que surgiram em torno de PR (complexidade), bem como a sua evolução ao longo do tempo. Além disso, serão abordadas as implicações que PR (complexidade) pode ter em diferentes contextos, desde a vida quotidiana até ao nível global. Este artigo fará uma análise exaustiva de PR (complexidade) e sua influência em diversos aspectos da sociedade, com o objetivo de oferecer uma visão abrangente e enriquecedora deste amplo e significativo tema.
 | Este artigo ou secção contém uma lista de referências no fim do texto, mas as suas fontes não são claras porque não são citadas no corpo do artigo, o que compromete a confiabilidade das informações. (Agosto de 2021) |
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