Función recursiva general

En lógica matemática e informática , una función recursiva general , función recursiva parcial o función μ-recursiva es una función parcial de números naturales a números naturales que es "computable" en un sentido intuitivo, así como en uno formal . Si la función es total , también se la llama función recursiva total (a veces abreviada como función recursiva ). ^{[ 1 ]} En la teoría de la computabilidad , se demuestra que las funciones μ-recursivas son precisamente las funciones que pueden ser computadas por máquinas de Turing ^{[ 2 ] [ 4 ]} (este es uno de los teoremas que apoya la tesis de Church-Turing ). Las funciones μ-recursivas están estrechamente relacionadas con las funciones recursivas primitivas , y su definición inductiva (a continuación) se basa en la de las funciones recursivas primitivas. Sin embargo, no toda función recursiva total es una función recursiva primitiva ; el ejemplo más famoso es la función de Ackermann .

Otras clases equivalentes de funciones son las funciones del cálculo lambda y las funciones que pueden ser calculadas por algoritmos de Markov .

El subconjunto de todas las funciones recursivas totales con valores en {0,1} se conoce en la teoría de la complejidad computacional como la clase de complejidad R.

Las funciones μ-recursivas (o funciones recursivas generales ) son funciones parciales que toman tuplas finitas de números naturales y devuelven un único número natural. Son la clase más pequeña de funciones parciales que incluye las funciones iniciales y es cerrada bajo composición, recursión primitiva y el operador de minimización μ .

La clase más pequeña de funciones, que incluye las funciones iniciales y es cerrada bajo composición y recursión primitiva (es decir, sin minimización), es la clase de funciones recursivas primitivas . Si bien todas las funciones recursivas primitivas son totales, esto no se cumple para las funciones recursivas parciales; por ejemplo, la minimización de la función sucesora no está definida. Las funciones recursivas primitivas son un subconjunto de las funciones recursivas totales, que a su vez son un subconjunto de las funciones recursivas parciales. Por ejemplo, se puede demostrar que la función de Ackermann es totalmente recursiva y no primitiva.

Funciones primitivas o "básicas":

1. Funciones constantes C ^k _n : Para cada número natural n y cada k

   ${\displaystyle C_{n}^{k}(x_{1},\ldots ,x_{k})\ {\stackrel {\mathrm {def} }{=}}\ n}$

   Las definiciones alternativas utilizan en su lugar una función cero como función primitiva que siempre devuelve cero, y construyen las funciones constantes a partir de la función cero, la función sucesora y el operador de composición .

2. Función sucesora S:

   ${\displaystyle S(x)\ {\stackrel {\mathrm {def} }{=}}\ x+1\,}$

3. Función de proyección${\displaystyle P_{i}^{k}}$(también llamada función identidad ): Para todos los números naturales${\displaystyle i,k}$de tal manera que${\displaystyle 1\leq i\leq k}$:

   ${\displaystyle P_{i}^{k}(x_{1},\ldots ,x_{k})\ {\stackrel {\mathrm {def} }{=}}\ x_{i}\,.}$

Operadores (el dominio de una función definida por un operador es el conjunto de valores de los argumentos tales que cada aplicación de la función que deba realizarse durante el cálculo proporciona un resultado bien definido):

1. operador de composición${\displaystyle \circ \,}$(también llamado operador de sustitución ): Dada una función m -aria${\displaystyle h(x_{1},\ldots ,x_{m})\,}$y m funciones k -arias${\displaystyle g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k})}$:

   ${\displaystyle h\circ (g_{1},\ldots ,g_{m})\ {\stackrel {\mathrm {def} }{=}}\ f,\quad {\text{where}}\quad f(x_{1},\ldots ,x_{k})=h(g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k})).}$

   Esto significa que${\displaystyle f(x_{1},\ldots ,x_{k})}$se define solo si${\displaystyle g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k}),}$y${\displaystyle h(g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k}))}$están todos definidos.

2. Operador de recursión primitiva ρ : Dada la función k -aria${\displaystyle g(x_{1},\ldots ,x_{k})\,}$y función k +2 -aria${\displaystyle h(y,z,x_{1},\ldots ,x_{k})\,}$:

   ${\displaystyle {\begin{aligned}\rho (g,h)&\ {\stackrel {\mathrm {def} }{=}}\ f\quad {\text{where the }}k+1{\text{-ary function }}f{\text{ is defined by}}\\f(0,x_{1},\ldots ,x_{k})&=g(x_{1},\ldots ,x_{k})\\f(S(y),x_{1},\ldots ,x_{k})&=h(y,f(y,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k})\,.\end{aligned}}}$

   Esto significa que${\displaystyle f(y,x_{1},\ldots ,x_{k})}$se define solo si${\displaystyle g(x_{1},\ldots ,x_{k})}$y${\displaystyle h(z,f(z,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k})}$están definidos para todos${\displaystyle z<y.}$

3. Operador de minimización μ : Dada una función ( k +1)-aria${\displaystyle f(y,x_{1},\ldots ,x_{k})\,}$, la función k -aria${\displaystyle \mu (f)}$se define por:

   ${\displaystyle {\begin{aligned}\mu (f)(x_{1},\ldots ,x_{k})=z{\stackrel {\mathrm {def} }{\iff }}\ f(i,x_{1},\ldots ,x_{k})&>0\quad {\text{for}}\quad i=0,\ldots ,z-1\quad {\text{and}}\\f(z,x_{1},\ldots ,x_{k})&=0\quad \end{aligned}}}$

Intuitivamente, la minimización busca —comenzando la búsqueda desde 0 y avanzando hacia arriba— el argumento más pequeño que hace que la función devuelva cero; si no existe tal argumento, o si se encuentra un argumento para el cual f no está definido, entonces la búsqueda nunca termina y${\displaystyle \mu (f)}$no está definido para el argumento${\displaystyle (x_{1},\ldots ,x_{k}).}$

Si bien algunos libros de texto utilizan el operador μ tal como se define aquí, ^{[ 5 ] [ 6 ]} otros ^{[ 7 ] [ 8 ]} exigen que el operador μ se aplique solo a funciones totales f . Aunque esto restringe el operador μ en comparación con la definición dada aquí, la clase de funciones μ-recursivas permanece igual, lo cual se deduce del teorema de la forma normal de Kleene (véase más adelante ). ^{[ 5 ] [ 6 ]} La única diferencia es que se vuelve indecidible si una definición de función específica define una función μ-recursiva, ya que es indecidible si una función computable (es decir, μ-recursiva) es total. ^{[ 7 ]}

La fuerte relación de igualdad${\displaystyle \simeq }$se puede utilizar para comparar funciones μ-recursivas parciales. Esto se define para todas las funciones parciales f y g de modo que

${\displaystyle f(x_{1},\ldots ,x_{k})\simeq g(x_{1},\ldots ,x_{l})}$

Se cumple si y solo si, para cualquier elección de argumentos, ambas funciones están definidas y sus valores son iguales, o bien ambas funciones no están definidas.

Ejemplos que no involucran el operador de minimización se pueden encontrar en Función recursiva primitiva#Ejemplos .

Los siguientes ejemplos tienen como único objetivo demostrar el uso del operador de minimización; también podrían definirse sin él, aunque de una manera más compleja, ya que todos son recursivos primitivos.

Los siguientes ejemplos definen funciones recursivas generales que no son recursivas primitivas; por lo tanto, no pueden evitar el uso del operador de minimización.

Una función recursiva general se denomina función recursiva total si está definida para cada entrada o, equivalentemente, si puede ser calculada por una máquina de Turing total . No existe una forma computacional de determinar si una función recursiva general dada es total; véase el problema de la parada .

En la equivalencia de modelos de computabilidad , se establece un paralelismo entre las máquinas de Turing que no terminan para ciertas entradas y un resultado indefinido para esa entrada en la función recursiva parcial correspondiente. El operador de búsqueda no acotado no puede definirse mediante las reglas de la recursión primitiva, ya que estas no proporcionan un mecanismo para los "bucles infinitos" (valores indefinidos).

Un teorema de forma normal debido a Kleene dice que para cada k existen funciones recursivas primitivas.${\displaystyle U(y)\!}$y${\displaystyle T(y,e,x_{1},\ldots ,x_{k})\!}$de tal manera que para cualquier función μ-recursiva${\displaystyle f(x_{1},\ldots ,x_{k})\!}$con k variables libres existe un e tal que

${\displaystyle f(x_{1},\ldots ,x_{k})\simeq U(\mu (T)(e,x_{1},\ldots ,x_{k}))}$.

El número e se denomina índice o número de Gödel para la función f . ^{[ 10 ] : 52–53} Una consecuencia de este resultado es que cualquier función μ-recursiva puede definirse utilizando una única instancia del operador μ aplicada a una función recursiva primitiva (total).

Minsky observa el${\displaystyle U}$La definición anterior es, en esencia, el equivalente μ-recursivo de la máquina de Turing universal :

Construir U es escribir la definición de una función recursiva general U ( n , x ) que interpreta correctamente el número n y calcula la función apropiada de x . Construir U directamente implicaría esencialmente la misma cantidad de esfuerzo, y esencialmente las mismas ideas , que hemos invertido en la construcción de la máquina de Turing universal ^{[ 11 ]}

En la literatura se utilizan varios simbolismos diferentes. Una ventaja de usar el simbolismo es que la derivación de una función mediante el "anidamiento" de operadores uno dentro del otro es más fácil de escribir de forma compacta. A continuación, la cadena de parámetros${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$se abrevia como${\displaystyle x}$:

• Función constante : Kleene utiliza "${\displaystyle C_{q}^{n}(x)=q}$" y Boolos-Burgess-Jeffrey (2002) (BBJ) utilizan la abreviatura "${\displaystyle \mathrm {const} ^{n}(x)=n}$":

p.ej${\displaystyle C_{13}^{7}(r,s,t,u,v,w,x)=13}$

p.ej${\displaystyle \mathrm {const} ^{13}(r,s,t,u,v,w,x)=13}$

• Función sucesora : Kleene utiliza${\displaystyle x'}$y${\displaystyle S}$para "Sucesor". Como "sucesor" se considera primitivo, la mayoría de los textos usan el apóstrofo de la siguiente manera:

${\displaystyle S(a)=a+1;{\overset {\mathrm {def} }{=}};a'}$, dónde

${\displaystyle 1{\overset {\mathrm {def} }{=}}0'}$,

${\displaystyle 2{\overset {\mathrm {def} }{=}}0''}$, etc.

• Función identidad : Kleene (1952) utiliza${\displaystyle U_{i}^{n}}$para indicar la función identidad sobre las variables${\displaystyle x_{i}}$; BBJ utiliza la función identidad${\displaystyle \mathrm {id} _{i}^{n}}$sobre las variables${\displaystyle x_{1}}$a${\displaystyle x_{n}}$:

${\displaystyle U_{i}^{n}(x)=\mathrm {id} _{i}^{n}(x)=x_{i}}$

p.ej${\displaystyle U_{3}^{7}(r,s,t,u,v,w,x)=\mathrm {id} _{3}^{7}(r,s,t,u,v,w,x)=t}$

• Operador de composición (sustitución) : Kleene utiliza una negrita.${\displaystyle \mathbf {S} _{m}^{n}}$(no confundir con su${\displaystyle S}$para "sucesor"!). El superíndice${\displaystyle m}$se refiere a la${\displaystyle m^{th}}$función${\displaystyle f_{m}}$, mientras que el subíndice${\displaystyle n}$se refiere a la${\displaystyle n^{th}}$variable${\displaystyle x_{n}}$:

Si se nos da

${\displaystyle h(x)=g(f_{1}(x),\ldots ,f_{m}(x))}$

entonces

${\displaystyle h(x)=\mathbf {S} _{m}^{n}(g,f_{1},\ldots ,f_{m})}$

De manera similar, pero sin los subíndices ni los superíndices, BBJ escribe:

${\displaystyle h(x')=Cg,f_{1},\ldots ,f_{m}}$

• Recursión primitiva : Kleene utiliza el símbolo${\displaystyle R^{n}({\text{base step}},{\text{induction step}})}$donde n indica el número de variables; BBJ utiliza${\displaystyle \Pr({\text{base step}},{\text{induction step}})(x)}$. Dado:

• paso base:${\displaystyle h(0,x)=f(x)}$
• Paso de inducción:${\displaystyle h(y+1,x)=g(y,h(y,x),x)}$

Ejemplo: definición de recursión primitiva de${\displaystyle a+b}$

• paso base:${\displaystyle f(0,a)=a=U_{1}^{1}(a)}$U ¹ ₁ (a)
• Paso de inducción:${\displaystyle f(b',a)=(f(b,a))'=g(b,f(b,a),a)=g(b,c,a)=c'=S(U_{2}^{3}(b,c,a))}$

${\displaystyle R^{2}\left(U_{1}^{1}(a),;S(U_{2}^{3}(b,c,a))\right)}$

${\displaystyle \Pr \left(U_{1}^{1}(a),;S(U_{2}^{3}(b,c,a))\right)}$

Ejemplo : Kleene da un ejemplo de cómo realizar la derivación recursiva de${\displaystyle f(b,a)=b+a}$(nótese la inversión de variables)${\displaystyle a}$y${\displaystyle b}$). Empieza con${\displaystyle 3}$funciones iniciales

1. ${\displaystyle S(a)=a'}$
2. ${\displaystyle U_{1}^{1}(a)=a}$
3. ${\displaystyle U_{2}^{3}(b,c,a)=c}$
4. ${\displaystyle g(b,c,a)=S(U_{2}^{3}(b,c,a))=c'}$
5. paso base:${\displaystyle h(0,a)=U_{1}^{1}(a)}$

Paso de inducción:${\displaystyle h(b',a)=g(b,h(b,a),a)}$

Él llega a:

${\displaystyle a+b=R^{2}\left(U_{1}^{1},;S_{1}^{3}(S,U_{2}^{3})\right)}$

• Número de Fibonacci
• Función McCarthy 91

• Teoría de la recursión
• Recursión
• Recursión (informática)

• Entrada de la Enciclopedia de Filosofía de Stanford
• Un compilador para transformar una función recursiva en una máquina de Turing equivalente.