Recursión de curso de valores

Técnica para definir funciones teóricas de números mediante recursión

En teoría de la computabilidad , la recursión de curso de valores es una técnica para definir funciones de 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 dichas definiciones se puedan convertir en definiciones utilizando una forma más simple de recursión se utiliza a menudo para demostrar que las funciones definidas por la 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 .

Definición y ejemplos

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 º 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, considere la función g definida con las ecuaciones de recursión

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

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

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

En general, una función f se define por recursión de curso de valores si hay 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 )}$

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

${\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 utilizar la función 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{cases}}}$

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

Equivalencia con la recursión primitiva

Para convertir una definición por recursión de curso de valores en una recursión primitiva, se utiliza una función auxiliar (auxiliar). 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 toma como una numeración de Gödel para secuencias .

De esta forma se codifican los primeros n valores de f . La función se puede definir por recursión primitiva porque se obtiene añadiendo al nuevo 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))),}$

donde append ( n , s , x ) calcula, siempre que s codifique 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í mismo recursivo primitivo, siendo la composición de dos funciones de este tipo:

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

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

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 individuales. Uno de esos métodos, la codificación de Gödel , representa una secuencia de números enteros positivos como ${\displaystyle \langle n_{0},n_{1},n_{2},\ldots ,n_{k}\rangle }$

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

donde p _i representa el primo i . Se puede demostrar que, con esta representación, las operaciones ordinarias sobre sucesiones 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 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 se permite que la secuencia incluya ceros, se representa como ${\displaystyle \langle n_{0},n_{1},n_{2},\ldots ,n_{k}\rangle }$

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

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

Limitaciones

No todas las definiciones recursivas se pueden transformar en definiciones recursivas primitivas. Un ejemplo conocido es la función de Ackermann , que tiene la forma A ( m , n ) y es demostrable que no es recursiva primitiva.

De hecho, cada nuevo valor A ( m +1, n ) depende de la secuencia de valores previamente definidos A ( i , j ), pero los i -s y j -s para los cuales los valores deben incluirse en esta secuencia dependen ellos mismos 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 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 la lógica matemática , AK Peters.
• Odifreddi, PG , 1989, Teoría de la recursión clásica , Holanda Septentrional; segunda edición, 1999.