En la teoría de la computabilidad , la recursividad del curso de valores es una técnica para definir funciones de la teoría de números por recursividad . En una definición de una función f mediante la recursividad del curso de valores, el valor de f ( n ) se calcula a partir de la secuencia.
El hecho de que tales definiciones se puedan convertir en definiciones usando una forma más simple de recursividad se usa a menudo para demostrar que las funciones definidas por la recursividad del curso de valores son recursivas primitivas . Contrariamente a la recursividad del curso de valores, en la recursión primitiva el cálculo de un valor de una función requiere sólo 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 .
Definición y ejemplos
La función factorial n ! está definido de forma recursiva por las reglas
¡Esta recursión es una recursividad primitiva porque calcula el siguiente valor ( n +1)! de la función basada 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
Para calcular Fib ( n +2), se requieren los dos últimos valores de la función Fib. Finalmente, considere la función g definida con las ecuaciones de recursión
Para calcular g ( n +1) usando estas ecuaciones, se deben calcular todos los valores anteriores de g ; ningún número finito fijo de valores previos es suficiente en general para el cálculo de g . Las funciones Fib yg son ejemplos de funciones definidas por la recursividad del curso de valores.
En general, una función f se define mediante la recursividad del curso de valores si hay una función recursiva primitiva fija h tal que para todo n ,
dónde es un número de Gödel que codifica la secuencia indicada. En particular
proporciona el valor inicial de la recursividad. La función h podría probar su primer argumento para proporcionar valores iniciales explícitos, por ejemplo para Fib uno podría usar la función definida por
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 (asumiendo que se usa una numeración de Gödel apropiada).
Equivalencia a la recursividad primitiva
Para convertir una definición por recursividad de curso de valores en una recursividad primitiva, se utiliza una función auxiliar (ayudante). Supongamos que uno quiere tener
- .
Para definir f usando la recursividad primitiva, primero defina la función auxiliar de curso de valores que debería satisfacer
donde el lado derecho se toma como una numeración de Gödel para secuencias .
Por lo tanto codifica los primeros n valores de f . La función se puede definir por recursividad primitiva porque se obtiene añadiendo a el nuevo elemento :
- ,
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 . Ésta es una función recursiva primitiva, bajo el supuesto de una numeración de Gödel apropiada; Para empezar, se asume que h es primitiva recursiva. Por tanto, la relación de recursividad se puede escribir como recursividad primitiva:
donde g es en sí mismo primitivo recursivo, siendo la composición de dos de tales funciones:
Dado , la función original f se puede definir por, lo que muestra que también es una función recursiva primitiva.
Aplicación a funciones recursivas primitivas
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 únicos. Uno de esos métodos, la codificación de Gödel , representa una secuencia de números enteros positivos como
- ,
donde p i represento el i- ésimo primo. Se puede demostrar que, con esta representación, las operaciones ordinarias sobre secuencias son todas recursivas primitivas. Estas operaciones incluyen
- Determinar la longitud de una secuencia,
- Extraer un elemento de una secuencia dado su índice,
- Concatenando dos secuencias.
Usando esta representación de secuencias, se puede ver que si h ( m ) es primitiva recursiva, entonces la función
- .
también es primitivo recursivo.
Cuando la secuencia se permite incluir ceros, en su lugar se representa como
- ,
que permite distinguir los códigos de las secuencias y .
Limitaciones
No todas las definiciones recursivas pueden transformarse en una definición recursiva primitiva. Un ejemplo conocido es la función de Ackermann , que es de la forma A ( m , n ) y probablemente no es recursiva primitiva.
De hecho, cada nuevo valor A ( m +1, n ) depende de la secuencia de valores A ( i , j ) previamente definidos , pero las i -s y j -s cuyos valores deben incluirse en esta secuencia dependen de ellos mismos previamente. valores calculados de la función; a saber ( i , j ) = ( m , A ( m +1, n )). Por lo tanto, no se puede codificar la secuencia de valores calculada previamente de una manera recursiva primitiva de la manera sugerida anteriormente (o en absoluto, ya que resulta que esta función no es recursiva primitiva).
Referencias
- Hinman, PG, 2006, Fundamentos de lógica matemática , AK Peters.
- Odifreddi, PG, 1989, Teoría de la recursividad clásica , Holanda del Norte; segunda edición, 1999.