O tema Função recursiva primitiva é assunto de interesse há muito tempo, suas diversas dimensões e ramificações têm intrigado acadêmicos, profissionais e especialistas no assunto. Desde suas origens históricas até suas aplicações modernas, Função recursiva primitiva provou ser uma área de estudo continuamente relevante e altamente importante em diversos contextos. À medida que a sociedade evolui, o interesse em Função recursiva primitiva permanece constante, demonstrando a sua capacidade de adaptação e de permanecer relevante num mundo em constante mudança. Neste artigo exploraremos as diversas facetas de Função recursiva primitiva e seu impacto em diferentes áreas, com o objetivo de fornecer uma visão holística deste fascinante tema.
Este artigo não cita fontes confiáveis. (Janeiro de 2013) |
As funções recursivas primitivas são definidas através do uso da recursão primitiva e da Composição como operações centrais.
Na teoria computacional, funções recursivas primitivas são uma classe de funções que formam um importante bloco de construção importante no caminho para chegar à total formalização da computabilidade. Essas funções são de grande importância para a teoria da prova.
Muitas das funções que normalmente são estudadas na teoria dos números, são recursivas primitivas. Por exemplo: adição, divisão, fatorial e exponenciação são todas recursivas primitivas.
A classe mais abrangente de funções recursivas parciais é definida por introduzir um operador de busca infinito. O uso desse operador pode resultar numa função parcial, isto é, a relação com, no máximo, um valor por cada argumento, mas não necessariamente tem algum valor para um argumento. Uma definição equivalente afirma que uma função recursiva parcial é uma tal que pode ser computada por uma Máquina de Turing. Uma função recursiva total é uma função recursiva parcial que é definida por cada entrada.
Toda função recursiva primitiva é recursiva total, mas nem todas as funções recursivas totais são primitivas recursivas. A função de Ackermann A(m, n) é um exemplo bem conhecido de uma função recursiva total que não é uma recursiva primitiva. Há uma caracterização das funções primitivas recursivas como um subconjunto de funções recursivas totais usando a função de Ackermann. Essa caracterização afirma que uma função é recursiva primitiva se e somente se existir um número natural m tal que a função possa ser computada por uma Máquina de Turing que sempre com A(m, n) ou menos passos, onde n é a soma dos argumentos da função recursiva primitiva.
Uma propriedade importante de funções recursivas primitivas é que elas são um subconjunto recursivamente enumerável do conjunto de todas as funções recursivas totais(o qual não é recursivamente enumerável). Isso significa que há uma única função computável f(e, n) tal que:
Entretanto, as funções recursivas primitivas não são o maior conjunto enumerável das funções totalmente computáveis.
Funções recursivas primitivas tendem a parecer com nossa intuição do que uma função computável deve ser. Certamente as funções iniciais são intuitivamente computáveis, e as duas operações pelas quais pode-se criar novas funções primitivas recursivas são também bem simples. Entretanto, o conjunto de funções recursivas primitivas não inclui toda função totalmente computável possível - isso pode ser visto com uma variante do Argumento de diagonalização de Cantor. Esse argumento fornece uma função computável total que não é primitiva recursiva. Um rascunho da prova é como se segue:
Esse argumento pode ser aplicado em qualquer classe de funções computáveis(totais) que podem ser enumeradas dessa forma, como explicado no artigo máquinas que sempre param. Note entretanto que as funções parcialmente computáveis(aquelas que não precisam ser definidas para todo argumento) podem ser explicitamente enumeradas, por exemplo enumerando codificações da Máquina de Turing.
Outros exemplos de funções recursivas totais mas não primitivas são conhecidos:
As funções recursivas primitivas estão intimamente relacionadas ao finitismo matemático, e são usadas em vários contextos na logica matematica, onde um particular sistema construtiva é desejado. Aritmética recursiva primitiva (primitive recursive arithmetic, PRA), um sistema formal de axiomas para números naturais e as funções recursivas primitivas sobre eles, é normalmente usada para este propósito. ARP é muito menos robusta que a Aritmética de Peano. Todavia, alguns resultados na Teoria dos números e na Teoria da Prova podem ser provados na PRA. Por exemplo, o teorema da imcompletude de Gödel pode formalizado na PRA, dado pelo seguinte teorema:
Similarmente, alguns dos resultados sintáticos na teoria da prova podem ser provados na PRA, que implicam que há funções recursivas primitivas que carregam a transformação sintática de provas correspodente.
Na teoria da prova e na Teoria dos conjuntos, existe um interesse nas provas de consistência finitistas, isto é, provas de consistência que por si só são finisticamente aceitáveis. Tal prova estabelece que a consistência de uma teoria T implica a consistência de uma teoria S produzindo uma função recursiva primitiva que consegue transformar uma prova da inconsistência de S em uma prova da inconsistência de T. Uma condição suficiente para que uma prova de consistência seja finitista é o fato de ela poder ser formalizada na PRA. Por exemplo, muitos resultados de consistência na teoria dos conjuntos que são obtidos por Forçamento podem ser reinterpretados como provas sintáticas que podem ser formalizadas na PRA.