Recursión de curso de valores

En la teoría de la computabilidad , la recursión de curso de valores es una técnica para definir funciones de la teoría de números mediante recursión . En una definición de una función f mediante recursión de curso de valores, el valor de f ( n ) se calcula a partir de la secuencia${\displaystyle \langle f(0),f(1),\ldots,f(n-1)\rangle }$.

El hecho de que tales definiciones puedan convertirse en definiciones utilizando una forma más simple de recursión se usa a menudo para demostrar que las funciones definidas por recursión de curso de valores son recursivas primitivas . A diferencia de la recursión de curso de valores, en la recursión primitiva el cálculo de un valor de una función requiere solo el valor anterior; por ejemplo, para una función recursiva primitiva 1-aria g, el valor de g ( n +1) se calcula solo a partir de g ( n ) y n .

La función factorial n ! se define recursivamente mediante las reglas

${\displaystyle 0!=1,}$

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

Esta recursión es una recursión primitiva porque calcula el siguiente valor ( n + 1)! de la función basándose en el valor de n y el valor anterior n ! de la función. Por otro lado, la función Fib( n ), que devuelve el n -ésimo número de Fibonacci , se define con las ecuaciones de recursión.

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

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

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

Para calcular Fib( n +2), se requieren los dos últimos valores de la función Fib. Finalmente, consideremos la función g definida con las ecuaciones de recurrencia.

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

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

Para calcular g ( n +1) usando estas ecuaciones, se deben calcular todos los valores anteriores de g ; en general, no basta con un número fijo y finito de valores anteriores para el cálculo de g . Las funciones Fib y g son ejemplos de funciones definidas por recursión de valores.

En general, una función f se define mediante recursión de curso de valores si existe una función recursiva primitiva fija h tal que para todo n ,

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

dónde${\displaystyle \langle f(0),f(1),\ldots,f(n-1)\rangle }$es un número de Gödel que codifica la secuencia indicada. En particular

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

proporciona el valor inicial de la recursión. La función h podría probar su primer argumento para proporcionar valores iniciales explícitos, por ejemplo, para Fib se podría usar la función definida por

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

donde s [ i ] denota la extracción del elemento i de una secuencia codificada s ; esto se ve fácilmente como una función recursiva primitiva (suponiendo que se utiliza una numeración de Gödel apropiada).

Para convertir una definición mediante recursión de curso de valores en una recursión primitiva, se utiliza una función auxiliar (de apoyo). Supongamos que se desea tener

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

Para definir f usando recursión primitiva, primero defina la función auxiliar de curso de valores que debe satisfacer

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

donde el lado derecho se considera una numeración de Gödel para secuencias .

De este modo${\displaystyle {\bar {f}}(n)}$codifica los primeros n valores de f . La función${\displaystyle {\bar {f}}}$puede definirse mediante recursión primitiva porque${\displaystyle {\bar {f}}(n+1)}$se obtiene al agregar a${\displaystyle {\bar {f}}(n)}$el nuevo elemento${\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))),}$

donde append ( n , s , x ) calcula, siempre que s codifica una secuencia de longitud n , una nueva secuencia t de longitud n + 1 tal que t [ n ] = x y t [ i ] = s [ i ] para todo i < n . Esta es una función recursiva primitiva, bajo el supuesto de una numeración de Gödel apropiada; se supone que h es recursiva primitiva desde el principio. Por lo tanto, la relación de recursión se puede escribir como recursión primitiva:

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

donde g es en sí misma recursiva primitiva, siendo la composición de dos de estas funciones:

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

Dado${\displaystyle {\bar {f}}}$, la función original f puede definirse por${\displaystyle f(n)={\bar {f}}(n+1)[n]}$, lo que demuestra que también es una función recursiva primitiva.

En el contexto de las funciones recursivas primitivas , es conveniente tener un medio para representar secuencias finitas de números naturales como números naturales individuales. Un método de este tipo, la codificación de Gödel , representa una secuencia de enteros positivos.${\displaystyle \langle n_{0},n_{1},n_{2},\ldots ,n_{k}\rangle }$como

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

donde p _i representa el i -ésimo número primo . Se puede demostrar que, con esta representación, todas las operaciones ordinarias sobre secuencias son recursivas primitivas. Estas operaciones incluyen:

• Determinar la longitud de una secuencia,
• Extraer un elemento de una secuencia dado su índice,
• Concatenación de dos secuencias.

Utilizando esta representación de secuencias, se puede ver que si h ( m ) es recursiva primitiva, entonces la función

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

También es recursivo primitivo.

Cuando la secuencia${\displaystyle \langle n_{0},n_{1},n_{2},\ldots ,n_{k}\rangle }$Se permite incluir ceros, en su lugar se representa como

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

lo que permite distinguir los códigos de las secuencias${\displaystyle \langle 0\rangle }$y${\displaystyle \langle 0,0\rangle }$.

No toda definición recursiva puede transformarse en una definición recursiva primitiva. Un ejemplo conocido es la función de Ackermann , que tiene la forma A ( m , n ) y se demuestra que no es recursiva primitiva.

En efecto, cada nuevo valor A ( m +1, n +1) depende de la secuencia de valores previamente definidos A ( i , j ), pero los valores i y j para los que A ( i , j ) debe incluirse en esta secuencia dependen a su vez de valores previamente calculados de la función; es decir, ( i , j ) = ( m , A ( m +1, n )). Por lo tanto, no se puede codificar la secuencia de valores previamente calculada de forma recursiva primitiva como se sugirió anteriormente (ni de ninguna otra forma, ya que resulta que esta función no es recursiva primitiva).

• Hinman, PG, 2006, Fundamentos de lógica matemática , AK Peters.
• Odifreddi, PG , 1989, Teoría clásica de la recursión , North Holland; segunda edición, 1999.