Função recursiva primitiva - Primitive recursive function

Na teoria da computabilidade , uma função recursiva primitiva é, grosso modo, uma função que pode ser calculada por um programa de computador cujos loops são todos loops "for" (ou seja, um limite superior do número de iterações de cada loop pode ser determinado antes de entrar no ciclo). As funções recursivas primitivas formam um subconjunto estrito das funções recursivas gerais que também são funções totais .

A importância das funções recursivas primitivas reside no fato de que a maioria das funções computáveis ​​que são estudadas na teoria dos números (e mais geralmente na matemática) são recursivas primitivas. Por exemplo, adição e divisão , o fatorial e função exponencial , e a função que devolve o n th privilegiada são todos recursiva primitiva. Na verdade, para mostrar que uma função computável é recursiva primitiva, basta mostrar que sua complexidade de tempo é limitada acima por uma função recursiva primitiva do tamanho de entrada. Segue-se que é difícil conceber uma função computável que não seja recursiva primitiva, embora algumas sejam conhecidas (ver § Limitações abaixo).

O conjunto de funções recursivas primitivas é conhecido como PR na teoria da complexidade computacional .

Definição

As funções recursivas primitivas estão entre as funções teóricas dos números, que são funções dos números naturais (inteiros não negativos) {0, 1, 2, ...} aos números naturais. Essas funções recebem n argumentos para algum número natural n e são chamadas de n - ário .

As funções recursivas primitivas básicas são dadas por estes axiomas :

Funções recursivas primitivas mais complexas podem ser obtidas aplicando as operações fornecidas por estes axiomas:

Exemplo. Tomamos f ( x ) como o S ( x ) definido acima. Este f é uma função recursiva primitiva 1-ária. E também g ( x ) = S ( x ). Portanto, h ( x ) definido como f ( g ( x )) = S ( S ( x )) também é uma função 1-ária recursiva primitiva. Falando informalmente, h ( x ) é a função que transforma x em x +2.

Exemplo. Suponha que f ( x ) = P ₁ ¹ ( x ) = x e g ( x , y , z ) = S ( P ₂ ³ ( x , y , z )) = S ( y ). Então h (0, x ) = x e h ( S ( y ), x ) = g ( y , h ( y , x ), x ) = S ( h ( y , x )). Agora h (0,1) = 1, h (1,1) = S ( h (0,1)) = 2, h (2,1) = S ( h (1,1)) = 3. Este h é uma função recursiva primitiva 2-ária. Podemos chamá-lo de 'adição'.

Interpretação. A função h atua como um loop for de 0 até o valor de seu primeiro argumento. O resto dos argumentos para h , denotados aqui com x _i ’s ( i = 1, ..., k ), são um conjunto de condições iniciais para o loop For que pode ser usado por ele durante os cálculos, mas que são imutáveis ​​por isto. As funções f e g no lado direito das equações que definem h representa o corpo do laço, que executa cálculos. A função f é usada apenas uma vez para realizar os cálculos iniciais. Os cálculos para as etapas subsequentes do loop são executados por g . O primeiro parâmetro de g é alimentado com o valor “atual” do índice do loop For. O segundo parâmetro de g é alimentado com o resultado dos cálculos anteriores do loop For, das etapas anteriores. O resto dos parâmetros para g são aquelas condições iniciais imutáveis ​​para o loop For mencionado anteriormente. Eles podem ser usados ​​por g para realizar cálculos, mas eles próprios não serão alterados por g .

As funções recursivas primitivas são as funções básicas e aquelas obtidas das funções básicas aplicando essas operações um número finito de vezes.

Papel das funções de projeção

As funções de projeção podem ser usadas para evitar a aparente rigidez em termos de aridade das funções acima; usando composições com várias funções de projeção, é possível passar um subconjunto dos argumentos de uma função para outra função. Por exemplo, se g e h são funções recursivas primitivas 2-árias, então

${\ displaystyle f (a, b, c) = g (h (c, a), h (a, b)) \!}$

também é recursivo primitivo. Uma definição formal usando funções de projeção é

${\ displaystyle f (a, b, c) = g (h (P_ {3} ^ {3} (a, b, c), P_ {1} ^ {3} (a, b, c)), h (P_ {1} ^ {3} (a, b, c), P_ {2} ^ {3} (a, b, c))).}$

Recursão primitiva fraca

A função predecessora de 1 lugar é recursiva primitiva. Ele decorre imediatamente do início das funções S e P ₁ ² pela regra da recursão primitiva. Fischer, Fischer & Beigel removeram o predecessor implícito da regra de recursão, substituindo-o pela regra mais fraca

${\ displaystyle {\ begin {array} {lcl} h (0, x_ {1}, \ ldots, x_ {k}) & = & f (x_ {1}, \ ldots, x_ {k}) & {\ text {e}} \\ h (S (y), x_ {1}, \ ldots, x_ {k}) & = & g (S (y), h (y, x_ {1}, \ ldots, x_ {k }), x_ {1}, \ ldots, x_ {k})) \ end {array}}}$

Eles provaram que a função predecessora ainda pode ser definida e, portanto, que a recursão primitiva "fraca" também define as funções recursivas primitivas.

Conversão de predicados em funções numéricas

Em alguns ambientes, é natural considerar funções recursivas primitivas que tomam como entradas tuplas que misturam números com valores verdade (ou seja, t para verdadeiro ef para falso), ou que produzem valores verdade como saídas. Isso pode ser feito identificando os valores verdade com números de qualquer maneira fixa. Por exemplo, é comum identificar o valor verdade t com o número 1 e o valor verdade f com o número 0. Uma vez feita essa identificação, a função característica de um conjunto A , que sempre retorna 1 ou 0, pode ser visto como um predicado que diz se um número é no conjunto a . Essa identificação de predicados com funções numéricas será assumida para o restante deste artigo.

Definição de linguagem de computador

Um exemplo de linguagem de programação recursiva primitiva é aquela que contém operadores aritméticos básicos (por exemplo, + e -, ou ADD e SUBTRAIR), condicionais e comparação (IF-THEN, EQUALS, LESS-THAN) e loops limitados, como o básico loop for , onde existe um limite superior conhecido ou calculável para todos os loops (FOR i FROM 1 TO n, com nem i nem n modificável pelo corpo do loop). Nenhuma estrutura de controle de maior generalidade, como loops while ou IF-THEN mais GOTO , é admitida em uma linguagem recursiva primitiva.

A linguagem LOOP , apresentada em um artigo de 1967 por Albert R. Meyer e Dennis M. Ritchie , é essa linguagem. Seu poder de computação coincide com as funções recursivas primitivas. Uma variante da linguagem LOOP é o BlooP de Douglas Hofstadter em Gödel, Escher, Bach . Adicionar loops ilimitados (WHILE, GOTO) torna a linguagem geral recursiva e completa de Turing , como todas as linguagens de programação de computador do mundo real.

A definição de funções recursivas primitivas implica que seu cálculo é interrompido em cada entrada (após um número finito de etapas). Por outro lado, o problema da parada é indecidível para funções recursivas gerais, mesmo que sejam totais . Ou seja, existem programas que param a cada entrada, mas para os quais isso não pode ser verificado por um algoritmo.

Exemplos

A maioria das funções teóricas dos números definíveis usando recursão em uma única variável são recursivas primitivas. Os exemplos básicos incluem as funções de adição e subtração truncada .

Adição

Intuitivamente, a adição pode ser definida recursivamente com as regras:

${\ displaystyle \ operatorname {add} (0, x) = x}$,

${\ displaystyle \ operatorname {add} (n + 1, x) = \ operatorname {add} (n, x) +1}$

Para ajustar isso em uma definição recursiva primitiva estrita, defina:

${\ displaystyle \ operatorname {add} (0, x) = P_ {1} ^ {1} (x),}$

${\ displaystyle \ operatorname {add} (S (n), x) = S (P_ {2} ^ {3} (n, \ operatorname {add} (n, x), x))}$

Aqui S ( n ) é "o sucessor de n " (ou seja, n +1), P ₁ ¹ é a função de identidade e P ₂ ³ é a função de projeção que recebe 3 argumentos e retorna o segundo. Funções de f e g exigidas pela definição anterior da operação recursão primitiva são respectivamente desempenhado pela P ₁ ¹ e a composição de S e P ₂ ³ .

Subtração

Como as funções recursivas primitivas usam números naturais em vez de inteiros, e os números naturais não são fechados sob subtração, uma função de subtração truncada (também chamada de "subtração adequada") é estudada neste contexto. Esta função de subtração limitada sub ( a , b ) [ou b ∸ a ] retorna b - a se for não negativo e retorna 0 caso contrário.

A função predecessora atua como o oposto da função sucessora e é recursivamente definida pelas regras:

pred (0) = 0,

pred ( n + 1) = n .

Essas regras podem ser convertidas em uma definição mais formal por recursão primitiva:

pred (0) = 0,

pred (S ( n )) = P ₁ ² ( n , pred ( n )).

A função de subtração limitada é definível a partir da função predecessora de maneira análoga à forma como a adição é definida a partir do sucessor:

sub (0, x ) = P ₁ ¹ ( x ),

sub (S ( n ), x ) = pred ( P ₂ ³ ( n , sub ( n , x ), x )).

Aqui sub ( a , b ) corresponde a b ∸ a ; por uma questão de simplicidade, a ordem dos argumentos foi alterada da definição "padrão" para se ajustar aos requisitos de recursão primitiva. Isso poderia ser facilmente corrigido usando composição com projeções adequadas.

Outras operações em números naturais

Os testes de exponenciação e primalidade são recursivos primitivos. Dadas as funções recursivas primitivas e , f , g e h , uma função que retorna o valor de g quando e ≤ f e o valor de h, caso contrário, é recursiva primitiva.

Operações em números inteiros e racionais

Usando a numeração de Gödel , as funções recursivas primitivas podem ser estendidas para operar em outros objetos, como números inteiros e racionais . Se os inteiros são codificados por números de Gödel de uma forma padrão, as operações aritméticas incluindo adição, subtração e multiplicação são todas recursivas primitivas. Da mesma forma, se os racionais são representados por números de Gödel, então as operações de campo são todas recursivas primitivas.

Use na aritmética de Peano de primeira ordem

Na aritmética de Peano de primeira ordem , existem infinitamente muitas variáveis ​​(símbolos 0-ários), mas nenhum símbolo não lógico k-ário com k> 0 diferente de S, +, * e ≤. Assim, para definir funções recursivas primitivas, é necessário usar o seguinte truque de Gödel.

Usando uma numeração de Gödel para sequências , por exemplo a função β de Gödel , qualquer sequência finita de números pode ser codificada por um único número. Tal número pode, portanto, representar a função recursiva primitiva até um determinado n.

Seja h uma função de recursão primitiva 1-ária definida por:

${\ displaystyle h (0) = C}$

${\ displaystyle h (n + 1) = g (n, h (n))}$

onde C é uma constante eg é uma função já definida.

Usando a função β de Gödel, para qualquer sequência de números naturais (k ₀ , k ₁ , ..., k _n ), existem números naturais b e c tais que, para cada i ≤ n, β (b, c, i) = k _eu . Podemos, portanto, usar a seguinte fórmula para definir h ; mais precisamente, m = h ( n ) é uma abreviação para o seguinte:

${\ displaystyle \ exists b: \ exists c: \ beta (b, c, 0) = C \ land \ forall i: (i <n) \ rightarrow (\ beta (b, c, i + 1) = g ( i, \ beta (b, c, i))) \ land (m = \ beta (b, c, n))}$

e o igualar ag , sendo já definido, é na verdade uma abreviação para alguma outra fórmula já definida (como é β, cuja fórmula é dada aqui ).

A generalização para qualquer função de recursão primitiva k-ária é trivial.

Relação com funções recursivas

A classe mais ampla de funções recursivas parciais é definida pela introdução de um operador de pesquisa ilimitado . A utilização deste operador pode resultar em uma função parcial , ou seja, uma relação com no máximo um valor para cada argumento, mas não necessariamente possui qualquer valor para nenhum argumento (ver domínio ). Uma definição equivalente afirma que uma função recursiva parcial é aquela que pode ser calculada por uma máquina de Turing . Uma função recursiva total é uma função recursiva parcial definida para cada entrada.

Cada função recursiva primitiva é recursiva total, mas nem todas as funções recursivas totais são recursivas primitivas. A função de Ackermann A ( m , n ) é um exemplo bem conhecido de uma função recursiva total (na verdade, total provável), que não é recursiva primitiva. Há uma caracterização das funções recursivas primitivas como um subconjunto das funções recursivas totais usando a função de Ackermann. Esta caracterização afirma que uma função é recursiva primitiva se e somente se houver um número natural m tal que a função pode ser calculada por uma máquina de Turing que sempre para dentro de A ( m , n ) ou menos etapas, onde n é a soma de os argumentos da função recursiva primitiva.

Uma propriedade importante das funções recursivas primitivas é que elas são um subconjunto recursivamente enumerável do conjunto de todas as funções recursivas totais (que não são recursivamente enumeráveis). Isso significa que há uma única função computável f ( m , n ) que enumera as funções recursivas primitivas, a saber:

• Para cada função recursiva primitiva g , existe um m tal que g ( n ) = f ( m , n ) para todo n , e
• Para cada m , a função h ( n ) = f ( m , n ) é recursiva primitiva.

f pode ser explicitamente construído repetindo iterativamente todas as maneiras possíveis de criar funções recursivas primitivas. Portanto, é comprovadamente total. Pode-se usar um argumento de diagonalização para mostrar que f não é primitivo recursivo em si: se fosse assim, também seria h ( n ) = f ( n , n ) +1. Mas se isso é igual a alguma função recursiva primitiva, existe um m tal que h ( n ) = f ( m , n ) para todo n , e então h ( m ) = f ( m , m ), levando à contradição.

No entanto, o conjunto de funções recursivas primitivas não é o maior subconjunto recursivamente enumerável do conjunto de todas as funções recursivas totais. Por exemplo, o conjunto de funções comprovadamente totais (na aritmética de Peano) também é recursivamente enumerável, já que se pode enumerar todas as provas da teoria. Embora todas as funções recursivas primitivas sejam comprovadamente totais, o inverso não é verdadeiro.

Limitações

Funções recursivas primitivas tendem a corresponder muito de perto com nossa intuição do que uma função computável deve ser. Certamente as funções iniciais são computáveis ​​intuitivamente (em sua própria simplicidade), e as duas operações pelas quais se pode criar novas funções recursivas primitivas também são muito diretas. No entanto, o conjunto de funções recursivas primitivas não inclui todas as funções computáveis ​​totais possíveis - isso pode ser visto com uma variante do argumento diagonal de Cantor . Este argumento fornece uma função computável total que não é recursiva primitiva. Um esboço da prova é o seguinte:

Este argumento pode ser aplicado a qualquer classe de funções computáveis ​​(totais) que podem ser enumeradas desta forma, conforme explicado no artigo Máquina que sempre pára . Observe, entretanto, que as funções computáveis parciais (aquelas que não precisam ser definidas para todos os argumentos) podem ser explicitamente enumeradas, por exemplo, enumerando as codificações da máquina de Turing.

Outros exemplos de funções recursivas totais, mas não recursivas primitivas, são conhecidos:

• A função que leva m para Ackermann ( m , m ) é uma função recursiva total unária que não é recursiva primitiva.
• O teorema de Paris-Harrington envolve uma função recursiva total que não é recursiva primitiva.
• A função do Sudão
• A função Goodstein

Algumas funções recursivas primitivas comuns

Os exemplos e definições a seguir são de Kleene (1952), pp. 223-231 - muitos aparecem com provas. A maioria também aparece com nomes semelhantes, como provas ou exemplos, em Boolos-Burgess-Jeffrey 2002, pp. 63-70; eles adicionam o logaritmo lo (x, y) ou lg (x, y) dependendo da derivação exata.

A seguir, observamos que as funções recursivas primitivas podem ser de quatro tipos:

1. funções para abreviar: "funções teóricas dos números" de {0, 1, 2, ...} a {0, 1, 2, ...},
2. predicados : de {0, 1, 2, ...} a valores verdadeiros {t = verdadeiro, f = falso},
3. conectivos proposicionais : de valores de verdade {t, f} para valores de verdade {t, f},
4. representando funções : de valores de verdade {t, f} a {0, 1, 2, ...}. Muitas vezes, um predicado requer uma função de representação para converter a saída do predicado {t, f} em {0, 1} (observe que a ordem de "t" para "0" e "f" para "1" corresponde a ~ sg () definido abaixo). Por definição, uma função φ ( x ) é uma "função representativa" do predicado P ( x ) se φ assume apenas os valores 0 e 1 e produz 0 quando P é verdadeiro ".

No seguinte, a marca "'", por exemplo, a', é a marca primitiva que significa "o sucessor de", geralmente considerado como "+1", por exemplo, a +1 = _def a '. As funções 16-20 e #G são de particular interesse no que diz respeito à conversão de predicados recursivos primitivos em sua forma "aritmética" expressa como números de Gödel e extraí-los de sua forma .

1. Adição: a + b
2. Multiplicação: a × b
3. Exponenciação: a ^b
4. Fatorial a! : 0! = 1, a '! = a! × a '
5. pred (a): (Predecessor ou decremento): Se a> 0 então a-1 mais 0
6. Subtração adequada a ∸ b: Se a ≥ b então ab else 0
7. Mínimo (a ₁ , ... a _n )
8. Máximo (a ₁ , ... a _n )
9. Diferença absoluta: | ab | = _def (a ∸ b) + (b ∸ a)
10. ~ sg (a): NÃO [signum (a)]: Se a = 0, então 1 mais 0
11. sg (a): signum (a): Se a = 0, então 0 else 1
12. a | b: (a divide b): Se b = k × a para algum k, então 0 else 1
13. Restante (a, b): o restante se b não divide a "uniformemente". Também chamado de MOD (a, b)
14. a = b: sg | a - b | (A convenção de Kleene era representar verdadeiro por 0 e falso por 1; atualmente, especialmente em computadores, a convenção mais comum é o inverso, ou seja, representar verdadeiro por 1 e falso por 0, o que equivale a transformar sg em ~ sg aqui e em o próximo item)
15. a <b: sg (a '∸ b)
16. Pr (a): a é um número primo Pr (a) = _def a> 1 & NÃO (existe c) _{1 <c <a} [c | a]
17. p _i : o i + 1 º número primo
18. (a) _i : expoente de p _i em a: o único x tal que p _i ^x | a & NOT (p _i ^{x '} | a)
19. lh (a): o "comprimento" ou número de expoentes não desaparecidos em um
20. lo (a, b): (logaritmo de a na base b): Se a, b> 1, então o maior x tal que b ^x | outro 0

A seguir, a abreviatura x = _def x ₁ , ... x _n ; subscritos podem ser aplicados se o significado exigir.

• #A: Uma função φ definível explicitamente a partir das funções Ψ e constantes q ₁ , ... q _n é primitiva recursiva em Ψ.
• #B: A soma finita Σ _{y <z} ψ ( x , y) e o produto Π _{y <z} ψ ( x , y) são recursivas primitivas em ψ.
• #C: Um predicado P obtido substituindo as funções χ ₁ , ..., χ _m pelas respectivas variáveis ​​de um predicado Q é primitivo recursivo em χ ₁ , ..., χ _m , Q.
• #D: Os seguintes predicados são primitivos recursivos em Q e R:

• NOT_Q ( x ).
• Q OU R: Q ( x ) VR ( x ),
• Q AND R: Q ( x ) & R ( x ),
• Q IMPLICA R: Q ( x ) → R ( x )
• Q é equivalente a R: Q ( x ) ≡ R ( x )

• #E: Os seguintes predicados são primitivos recursivos no predicado R:

• (Ey) _{y <z} R ( x , y) onde (Ey) _{y <z} denota "existe pelo menos um y que é menor que z tal que"
• (y) _{y <z} R ( x , y) onde (y) _{y <z} denota "para todo y menor que z é verdade que"
• µy _{y <z} R ( x , y). O operador μy _{y <z} R ( x , y) é uma forma limitada do chamado operador de minimização ou mu : Definido como "o menor valor de y menor que z tal que R ( x , y) seja verdadeiro; ou z se esse valor não existir. "

• #F: Definição por casos: A função definida assim, onde Q ₁ , ..., Q _m são predicados mutuamente exclusivos (ou "ψ ( x ) deve ter o valor dado pela primeira cláusula que se aplica), é recursiva primitiva em φ ₁ , ..., Q ₁ , ... Q _m :

φ ( x ) =

• φ ₁ ( x ) se Q ₁ ( x ) for verdadeiro,
• . . . . . . . . . . . . . . . . . . .
• φ _m ( x ) se Q _m ( x ) for verdadeiro
• φ _{m + 1} ( x ) caso contrário

• #G: Se φ satisfaz a equação:

φ (y, x ) = χ (y, CURSO-φ (y; x ₂ , ... x _n ), x ₂ , ... x _n então φ é primitivo recursivo em χ. O valor CURSO-φ (y ; x _{2 an} ) da função de curso de valores codifica a sequência de valores φ (0, x _{2 an} ), ..., φ (y-1, x _{2 an} ) da função original.

Formas recursivas primitivas adicionais

Algumas formas adicionais de recursão também definem funções que são de fato recursivas primitivas. As definições nessas formas podem ser mais fáceis de encontrar ou mais naturais para leitura ou escrita. A recursão do curso de valores define funções recursivas primitivas. Algumas formas de recursão mútua também definem funções recursivas primitivas.

As funções que podem ser programadas na linguagem de programação LOOP são exatamente as funções recursivas primitivas. Isso dá uma caracterização diferente do poder dessas funções. A principal limitação da linguagem LOOP, em comparação com uma linguagem Turing-completa , é que na linguagem LOOP o número de vezes que cada loop será executado é especificado antes de o loop começar a ser executado.

Resultados de finitismo e consistência

As funções recursivas primitivas estão intimamente relacionadas ao finitismo matemático e são usadas em vários contextos na lógica matemática onde um sistema particularmente construtivo é desejado. A aritmética recursiva primitiva (PRA), um sistema de axioma formal para os números naturais e as funções recursivas primitivas sobre eles, é freqüentemente usada para esse propósito.

PRA é muito mais fraco do que a aritmética de Peano , que não é um sistema finitístico. No entanto, muitos resultados na teoria dos números e na teoria da prova podem ser provados na PRA. Por exemplo, o teorema da incompletude de Gödel pode ser formalizado em PRA, dando o seguinte teorema:

Se T é uma teoria da aritmética satisfazendo certas hipóteses, com Gödel frase G _T , então PRA comprova a Con implicação ( T ) → G _T .

Da mesma forma, muitos dos resultados sintáticos na teoria da prova podem ser provados em PRA, o que implica que existem funções recursivas primitivas que realizam as correspondentes transformações sintáticas das provas.

Na teoria da prova e na teoria dos conjuntos , existe um interesse nas provas de consistência finitística , isto é, nas provas de consistência que são finitisticamente aceitáveis. Tais uma prova estabelece que a consistência de uma teoria T implica a consistência de uma teoria S através da produção de uma função recursiva primitiva que pode transformar qualquer prova de uma inconsistência de S para uma prova de uma inconsistência de T . Uma condição suficiente para que uma prova de consistência seja finita é a capacidade de formalizá-la no PRA. Por exemplo, muitos resultados de consistência na teoria de conjuntos que são obtidos por forçamento podem ser reformulados como provas sintáticas que podem ser formalizadas em PRA.

História

As definições recursivas foram usadas mais ou menos formalmente na matemática antes, mas a construção da recursão primitiva remonta ao teorema 126 de Richard Dedekind de seu Was sind und was sollen die Zahlen? (1888). Este trabalho foi o primeiro a dar uma prova de que uma certa construção recursiva define uma função única.

A aritmética recursiva primitiva foi proposta pela primeira vez por Thoralf Skolem em 1923.

A terminologia atual foi cunhada por Rózsa Péter (1934) após Ackermann ter provado em 1928 que a função que hoje leva seu nome não era recursiva primitiva, evento que levou à necessidade de renomear o que até então se chamava simplesmente funções recursivas.

Veja também

• Hierarquia de Grzegorczyk
• Recursão (ciência da computação)
• Funcional recursivo primitivo
• Recursão dupla
• Função de conjunto recursivo primitivo
• Função ordinal recursiva primitiva

Notas

Referências

• Brainerd, WS, Landweber, LH (1974), Theory of Computation , Wiley, ISBN  0-471-09585-0
• Fischer, Michael J .; Fischer, Robert P .; Beigel, Richard (novembro de 1989). "Recursão primitiva sem predecessor implícito" . Notícias ACM SIGACT . 20 (4): 87–91. doi : 10.1145 / 74074.74089 .
• Robert I. Soare , Recursively Enumerable Sets and Degrees , Springer-Verlag, 1987. ISBN  0-387-15299-7
• Stephen Kleene (1952) Introdução à Metamatemática , North-Holland Publishing Company, Nova York, 11ª reimpressão 1971: (notas da 2ª edição adicionadas na 6ª reimpressão). No Capítulo XI. Funções Recursivas Gerais §57
• George Boolos , John Burgess , Richard Jeffrey (2002), Computabilidade e Lógica: Quarta Edição , Cambridge University Press, Cambridge, Reino Unido. Cf pp. 70–71.
• Robert I. Soare 1995 Computability and Recursion http://www.people.cs.uchicago.edu/~soare/History/compute.pdf
• Daniel Severin 2008, Funções recursivas primitivas unárias , J. Symbolic Logic Volume 73, Edição 4, pp. 1122–1138 arXiv projecteuclid