Recursão do curso de valores - Course-of-values recursion

Na teoria da computabilidade , a recursão do curso de valores é uma técnica para definir funções teóricas dos números por recursão . Em uma definição de uma função f por recursão de curso de valores, o valor de f ( n ) é calculado a partir da sequência . ${\ displaystyle \ langle f (0), f (1), \ ldots, f (n-1) \ rangle}$

O fato de que tais definições podem ser convertidas em definições usando uma forma mais simples de recursão é freqüentemente usado para provar que funções definidas por recursão de curso de valores são recursivas primitivas . Ao contrário da recursão de curso de valores, na recursão primitiva o cálculo de um valor de uma função requer apenas o valor anterior; por exemplo, para uma função recursiva primitiva 1-ária g, o valor de g ( n +1) é calculado apenas a partir de g ( n ) e n .

Definição e exemplos

A função fatorial n ! é recursivamente definido pelas regras

${\ displaystyle 0! = 1,}$

${\ displaystyle (n + 1)! = n! (n + 1).}$

Esta recursão é uma recursão primitiva porque calcula o próximo valor ( n +1)! da função com base no valor de n e no valor anterior n ! da função. Por outro lado, a função de Fib ( n ), que retorna a n th número de Fibonacci , está definido com as equações recursivas

${\ displaystyle Fib (0) = 0,}$

${\ displaystyle Fib (1) = 1,}$

${\ displaystyle Fib (n + 2) = Fib (n + 1) + Fib (n).}$

Para calcular Fib ( n +2), os dois últimos valores da função Fib são necessários. Finalmente, considere a função g definida com as equações de recursão

${\ displaystyle g (0) = 0,}$

${\ displaystyle g (n + 1) = \ sum _ {i = 0} ^ {n} g (i) ^ {ni}.}$

Para calcular g ( n +1) usando essas equações, todos os valores anteriores de g devem ser calculados; nenhum número finito fixo de valores anteriores é suficiente em geral para o cálculo de g . As funções Fib eg são exemplos de funções definidas por recursão de curso de valores.

Em geral, uma função f é definida por recursão de curso de valores se houver uma função recursiva primitiva fixa h tal que para todo n ,

${\ displaystyle f (n) = h (n, \ langle f (0), f (1), \ ldots, f (n-1) \ rangle)}$

onde é um número de Gödel que codifica a sequência indicada. Em particular ${\ displaystyle \ langle f (0), f (1), \ ldots, f (n-1) \ rangle}$

${\ displaystyle f (0) = h (0, \ langle \ rangle)}$

fornece o valor inicial da recursão. A função h pode testar seu primeiro argumento para fornecer valores iniciais explícitos, por exemplo, para Fib, pode-se usar a função definida por

${\ displaystyle h (n, s) = {\ begin {cases} n & {\ text {if}} n <2 \\ s [n-2] + s [n-1] & {\ text {if}} n \ geq 2 \ end {casos}}}$

onde s [ i ] denota extração do elemento i de uma sequência codificada s ; isso é facilmente visto como uma função recursiva primitiva (assumindo que uma numeração de Gödel apropriada seja usada).

Equivalência para recursão primitiva

Para converter uma definição por recursão de curso de valores em uma recursão primitiva, uma função auxiliar (auxiliar) é usada. Suponha que alguém queira ter

${\ displaystyle f (n) = h (n, \ langle f (0), f (1), \ ldots, f (n-1) \ rangle)}$.

Para definir f usando recursão primitiva, primeiro defina a função de curso de valores auxiliar que deve satisfazer

${\ displaystyle {\ bar {f}} (n) = \ langle f (0), f (1), \ ldots, f (n-1) \ rangle}$

onde o lado direito é considerado uma numeração de Gödel para sequências .

Assim, codifica os primeiros n valores de f . A função pode ser definida por recursão primitiva porque é obtida anexando ao novo elemento : ${\ displaystyle {\ bar {f}} (n)}$${\ displaystyle {\ bar {f}}}$${\ displaystyle {\ bar {f}} (n + 1)}$${\ displaystyle {\ bar {f}} (n)}$${\ displaystyle h (n, {\ bar {f}} (n))}$

${\ displaystyle {\ bar {f}} (0) = \ langle \ rangle}$,

${\ displaystyle {\ bar {f}} (n + 1) = {\ mathit {append}} (n, {\ bar {f}} (n), h (n, {\ bar {f}} (n ))),}$

onde append ( n , s , x ) calcula, sempre que s codifica uma sequência de comprimento n , uma nova sequência t de comprimento n + 1 tal que t [ n ] = x e t [ i ] = s [ i ] para todos os i < n . Esta é uma função recursiva primitiva, sob a suposição de uma numeração de Gödel apropriada; h é considerado primitivo recursivo para começar. Assim, a relação de recursão pode ser escrita como recursão primitiva:

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

onde g é ele próprio recursivo primitivo, sendo a composição de duas dessas funções:

${\ displaystyle g (i, j) = {\ mathit {append}} (i, j, h (i, j)),}$

Dada , a função original f pode ser definida por , o que mostra que também é uma função recursiva primitiva. ${\ displaystyle {\ bar {f}}}$${\ displaystyle f (n) = {\ bar {f}} (n + 1) [n]}$

Aplicação a funções recursivas primitivas

No contexto de funções recursivas primitivas , é conveniente ter um meio de representar sequências finitas de números naturais como números naturais únicos. Um desses métodos, a codificação de Gödel , representa uma sequência de inteiros positivos como ${\ displaystyle \ langle n_ {0}, n_ {1}, n_ {2}, \ ldots, n_ {k} \ rangle}$

${\ displaystyle \ prod _ {i = 0} ^ {k} p_ {i} ^ {n_ {i}}}$,

onde p _i representa o i ésimo. Pode-se mostrar que, com esta representação, as operações ordinárias em sequências são todas recursivas primitivas. Essas operações incluem

• Determinando o comprimento de uma sequência,
• Extrair um elemento de uma sequência dado seu índice,
• Concatenando duas sequências.

Usando esta representação de sequências, pode-se ver que se h ( m ) é recursiva primitiva, então a função

${\ displaystyle f (n) = h (\ langle f (0), f (1), f (2), \ ldots, f (n-1) \ rangle)}$.

também é recursivo primitivo.

Quando a sequência pode incluir zeros, ela é representada como ${\ displaystyle \ langle n_ {0}, n_ {1}, n_ {2}, \ ldots, n_ {k} \ rangle}$

${\ displaystyle \ prod _ {i = 0} ^ {k} p_ {i} ^ {(n_ {i} +1)}}$,

o que permite distinguir os códigos das sequências e . ${\ displaystyle \ langle 0 \ rangle}$${\ displaystyle \ langle 0,0 \ rangle}$

Limitações

Nem toda definição recursiva pode ser transformada em uma definição recursiva primitiva. Um exemplo conhecido é a função de Ackermann , que tem a forma A ( m , n ) e provavelmente não é recursiva primitiva.

Na verdade, cada novo valor A ( m +1, n ) depende da sequência de valores previamente definidos A ( i , j ), mas os i -s e j -s para os quais os valores devem ser incluídos nesta sequência dependem deles mesmos anteriormente valores calculados da função; a saber ( i , j ) = ( m , A ( m +1, n )). Assim, não se pode codificar a sequência de valores computada anteriormente de uma maneira recursiva primitiva da maneira sugerida acima (ou de nenhuma maneira, visto que essa função não é recursiva primitiva).

Referências

• Hinman, PG, 2006, Fundamentals of Mathematical Logic , AK Peters.
• Odifreddi, PG, 1989, Teoria da Recursão Clássica , Holanda do Norte; segunda edição, 1999.