Función recursiva elemental

El término elemental fue introducido originalmente por László Kalmár en el contexto de la teoría de la computabilidad . ^{[ 1 ] [ 2 ]} Definió la clase de funciones recursivas elementales ( "funciones elementales de Kalmár" ) como un subconjunto de las funciones recursivas primitivas , específicamente, aquellas que pueden calcularse utilizando un conjunto limitado de operaciones como composición, sumas acotadas y productos acotados. ^{[ 3 ]} Estas funciones no crecen más rápido que una torre de exponenciación de altura fija (por ejemplo,${\displaystyle O(2^{2^{n}})}$). No todas las funciones recursivas primitivas son elementales; por ejemplo, la tetración crece demasiado rápido para ser incluida en la clase elemental. Las funciones recursivas elementales corresponden a la clase${\displaystyle {\mathcal {E}}^{3}}$de la jerarquía Grzegorczyk . ^{[ 4 ]}

En la teoría de la complejidad computacional , el término ELEMENTARIO se refiere a una clase de problemas de decisión que se pueden resolver en tiempo elemental, es decir, dentro de un tiempo limitado por un número fijo de exponenciales. Formalmente:

${\displaystyle {\mathsf {ELEMENTARY}}=\bigcup _{k\in \mathbb {N} }{\text{DTIME}}(\exp ^{k}(n^{c}))}$

dónde${\displaystyle \exp ^{k}(n)}$denota una torre exponencial de k niveles (por ejemplo,${\displaystyle 2^{2^{\cdot ^{\cdot ^{n}}}}}$).

Aunque el nombre proviene del mismo origen histórico, la clase de complejidad ELEMENTARY se ocupa de problemas de decisión y del tiempo de ejecución de la máquina de Turing, en lugar de funciones completas.

Las definiciones de funciones recursivas elementales son las mismas que para las funciones recursivas primitivas , excepto que la recursión primitiva se reemplaza por suma acotada y producto acotado. ^{[ 1 ] [ 3 ] [ 5 ]} Todas las funciones operan sobre los números naturales . Las funciones básicas, todas ellas recursivas elementales, son:

1. Función cero . Devuelve cero:${\displaystyle f(x)=0}$.
2. Función sucesora :${\displaystyle f(x)=x+1}$A menudo esto se denota por${\displaystyle S}$, como en${\displaystyle S(x)}$Mediante la aplicación repetida de una función sucesora, se puede lograr la suma.
3. Funciones de proyección : se utilizan para ignorar argumentos. Por ejemplo,${\displaystyle f(a,b)=a}$es una función de proyección.
4. Función de resta :${\displaystyle f(x,y)=\max(xy,0)}$Esta función se utiliza para definir condicionales e iteraciones.

A partir de estas funciones básicas, podemos construir otras funciones recursivas elementales.

1. Composición : aplicar valores de alguna función recursiva elemental como argumento a otra función recursiva elemental. La función${\displaystyle f}$definida como la composición${\displaystyle f(x_{1},\ldots ,x_{n})=h{\bigl (}g_{1}(x_{1},\ldots ,x_{n}),\ldots ,g_{m}(x_{1},\ldots ,x_{n}){\bigr )}}$es recursivo elemental si${\displaystyle h}$es recursivo elemental y cada${\displaystyle g_{i}}$es recursivo elemental.
2. Suma acotada :${\displaystyle f(m,x_{1},\ldots ,x_{n})=\sum \limits _{i=0}^{m}g(i,x_{1},\ldots ,x_{n})}$es recursivo elemental si${\displaystyle g}$es recursivo elemental.
3. Producto acotado :${\displaystyle f(m,x_{1},\ldots ,x_{n})=\prod \limits _{i=0}^{m}g(i,x_{1},\ldots ,x_{n})}$es recursivo elemental si${\displaystyle g}$es recursivo elemental.

En el contexto de la teoría de la computabilidad, la superposición es un método para construir nuevas funciones a partir de funciones existentes mediante composición funcional . Permite que las salidas de una o más funciones sirvan como entradas para otra función.

De forma más formal, supongamos:

• ${\displaystyle f(x_{1},\dots ,x_{k})}$es un${\displaystyle k}$función -aria y
• ${\displaystyle g_{1}(x_{1},\dots ,x_{n}),\dots ,g_{k}(x_{1},\dots ,x_{n})}$son${\displaystyle n}$funciones -arias.

Entonces, la superposición de estas funciones produce una nueva${\displaystyle n}$Función -aria:

${\displaystyle h(x_{1},\dots ,x_{n})=f(g_{1}(x_{1},\dots ,x_{n}),\dots ,g_{k}(x_{1},\dots ,x_{n}))}$.

La clase de funciones recursivas elementales coincide con el cierre bajo superposición de las funciones de proyección y uno de los siguientes conjuntos de funciones iniciales:

• ${\displaystyle \{n+m,\;n\mathbin {\dot {-}} m,\;\lfloor n/m\rfloor ,\;2^{n}\}}$^{[ 6 ]}
• ${\displaystyle \{n+m,\;n\mathbin {\dot {-}} m,\;\lfloor n/m\rfloor ,\;nm,\;n^{m}\}}$^{[ 7 ]}
• ${\displaystyle \{n+m,\;n{\bmod {m}},\;n^{2},\;2^{n}\}}$^{[ 8 ]}
• ${\displaystyle \{n+m,\;n{\bmod {m}},\;2^{n}\}}$^{[ 9 ]}

dónde${\displaystyle n\mathbin {\dot {-}} m=\max(nm,0)}$denota resta truncada ( monus ).

En 2025 Mihai Prunescu, Lorenzo Sauras-Altuzarra y Joseph M. Shunia demostraron que la clase de funciones elementales de Kalmár se puede generar inductivamente a partir de la suma (${\displaystyle n+m}$), resto entero (${\displaystyle n{\bmod {m}}}$) y exponenciación en base dos (${\displaystyle 2^{n}}$), mejorando los resultados previos de Mazzanti ^{[ 7 ]} y Marchenkov. ^{[ 8 ]} Además, demostraron que la base de sustitución definida por estas tres operaciones es mínima. ^{[ 10 ]} Una cuestión abierta es si${\displaystyle \{n+m,\;\lfloor n/m\rfloor ,\;2^{n}\}}$es una base alternativa.

Ejemplo 1

Dejar $${\displaystyle f(a,b)=a{\bmod {b}},\quad g_{1}(n)=2^{n+n},\quad g_{2}(n)=2^{n}+n\,.}$$ Luego la función $${\displaystyle h(n)=f(g_{1}(n),g_{2}(n))=2^{n+n}{\bmod {(}}2^{n}+n)}$$ define la función cuadrada${\displaystyle h(n)=n^{2}}$por superposición únicamente. ^{[ 11 ]} Esto muestra cómo funciones como el cuadrado pueden expresarse utilizando únicamente suma, resto entero y exponenciación en base dos a través de superposición, sin requerir recursión explícita .

Ejemplo 2

Otro ejemplo de una función recursiva elemental es la delta de Kronecker.$${\displaystyle \delta _{ij}=2^{(2^{i}{\bmod {(}}2^{j}+1))+(2^{j}{\bmod {(}}2^{i}+1)){\bmod {(}}2^{i}+2^{j})}{\bmod {2}}\,,}$$ lo cual satisface${\displaystyle \delta _{ij}=1}$si${\displaystyle i=j}$y${\displaystyle 0}$de lo contrario.

Otros ejemplos

${\displaystyle x\mathbin {\dot {-}} y=((2^{x+y}+x){\bmod {(}}2^{x+y}+y)){\bmod {(}}2^{x+y}+x)}$. ^{[ 12 ]}

${\displaystyle 2xy=(x+y)^{2}\mathbin {\dot {-}} (x^{2}+y^{2})}$. ^{[ 13 ]}

${\displaystyle \lfloor x/y\rfloor =(2(x+1)(x\mathbin {\dot {-}} (x{\bmod {y}}))){\bmod {(}}2(x+1)y\mathbin {\dot {-}} 1)}$. ^{[ 14 ]}

${\displaystyle xy=\lfloor 2xy/2\rfloor }$. ^{[ 15 ]}

${\displaystyle x^{y}=2^{(xy+x+1)y}{\bmod {(}}2^{xy+x+1}\mathbin {\dot {-}} x)}$. ^{[ 16 ]}

Las funciones recursivas elementales inferiores siguen las definiciones anteriores, excepto que no se permite el producto acotado. ^{[ 3 ]} Es decir, una función recursiva elemental inferior debe ser una función cero, sucesora o de proyección, una composición de otras funciones recursivas elementales inferiores o la suma acotada de otra función recursiva elemental inferior.

Las funciones recursivas elementales inferiores también se conocen como funciones elementales de Skolem. ^{[ 17 ] [ 18 ]}

Mientras que las funciones recursivas elementales tienen un crecimiento potencialmente superior al exponencial, las funciones recursivas elementales de menor orden tienen un crecimiento polinómico.

La clase de funciones elementales inferiores tiene una descripción en términos de composición de funciones simples análoga a la que tenemos para las funciones elementales. ^{[ 18 ] [ 19 ]} Es decir, una función acotada polinomialmente es elemental inferior si y solo si puede expresarse usando una composición de las siguientes funciones: proyecciones,${\displaystyle n+1}$,${\displaystyle nm}$,${\displaystyle n\mathbin {\dot {-}} m}$,${\displaystyle n\wedge m}$,${\displaystyle \lfloor n/m\rfloor }$, una función exponencial (${\displaystyle 2^{n}}$o${\displaystyle n^{m}}$) con la siguiente restricción en la estructura de las fórmulas: la fórmula no puede tener más de dos pisos con respecto a un exponente (por ejemplo,${\displaystyle xy(z+1)}$tiene 1 piso,${\displaystyle (x+y)^{yz+x}+z^{x+1}}$tiene 2 plantas,${\displaystyle 2^{2^{x}}}$tiene 3 plantas). Aquí${\displaystyle n\wedge m}$es una operación AND bit a bit de n y m .

• ELEMENTAL
• aritmética de funciones elementales
• Función recursiva primitiva
• Jerarquía de Grzegorczyk
• BUCLE (lenguaje de programación)
• EXPERIENCIA