Função recursiva primitiva

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.

Relacionamento com funções recursivas

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:

Para toda função recursiva primitiva g, há um e tal que g(n) = f(e, n) para todo n
Para todo e, a função h(n) = f(e, n) é primitiva recursiva

Entretanto, as funções recursivas primitivas não são o maior conjunto enumerável das funções totalmente computáveis.

Limitações

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:

As funções recursivas primitivas de um argumento(i.e., funções unárias) podem ser enumeradas computavelmente. Enumeração usa as definições de funções recursivas primitivas(que são essencialmente apenas expressões com as operações de recursão primitiva e composição como operadores e as funções recursivas primitivas como atômicas), e pode ser adotada para conter todas as definições de uma vez, mesmo porque uma mesma definição ocorrer muitas vezes na lista(uma vez que muitas definições definem a mesma função; realmente simplesmente compor usando a função identidade gera infinitamente muitas definições de uma função recursiva primitiva). Isso significa que a n-ésima definição de uma função recursiva primitiva nessa enumeração pode ser efetivamente determinada de n. De fato, se for usado alguma numeração de Gödel para codificar definições como números, então essa n-ésima definição na lista é computada por uma função recursiva primitiva de n. Admita que fn denota a função recursiva primitiva unária dada por esta definição.

Agora defina a "função avaliadora" ev com 2 argumentos, por ev(i,j) = fi(j). Claramente ev é total e computável, já que podemos determinar eficientemente a definição de fi, e sendo uma função recursiva primitiva fi é em total e computável, então fi(j) é sempre definida e eficientemente computável. Entretanto, um argumento diagonal mostrará que a função ev de 2 argumentos não é primitiva recursiva.

Suponha que ev fosse uma primitiva recursiva, então a função unária g definida por g(i) = S(ev(i, i)) seria também recursiva primitiva, como é definido via composição da função sucessor e ev. Mas então g aparece na enumeração, logo há algum número n no qual g = fn. Mas agora g(n) = S(ev(n, n)) = S(fn(n)) = S(g(n)) nos dá uma contradição.

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:

A função que usa m em AckermannAckermann(m, m) é recursiva total unária e não é recursiva primitiva.
O Teorema de Patis-Harrington engloba uma função recursiva total que não é recursiva primitiva. Como essa função é motivada pela teoria de Ramsey, é considerada, por vezes, mais natural que a função Ackermann.
A Função de Sudan

Finitismo e resultados consistentes

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:

Se T é uma teoria da aritmética satisfazendo determinada hipotese, sendo G a sentença de Gödel, então PRA prova que Con(T)?G.

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.

Ver também