ELEMENTAL

En la teoría de la complejidad computacional , la clase de complejidad ELEMENTAL de funciones recursivas elementales es la unión de las clases

${\displaystyle {\begin{aligned}{\mathsf {ELEMENTARY}}&=\bigcup _{k\in \mathbb {N} }k{\mathsf {{\mbox{-}}EXP}}\\&={\mathsf {DTIME}}\left(2^{n}\right)\cup {\mathsf {DTIME}}\left(2^{2^{n}}\right)\cup {\mathsf {DTIME}}\left(2^{2^{2^{n}}}\right)\cup \cdots \end{aligned}}}$

El nombre fue acuñado por László Kalmár , en el contexto de funciones recursivas e indecidibilidad ; la mayoría de los problemas que plantea están lejos de ser elementales. Algunos problemas recursivos naturales se encuentran fuera de ELEMENTARY y, por tanto, son NONELEMENTARY . En particular, hay problemas recursivos primitivos que no están en ELEMENTARY. Sabemos

ELEMENTAL INFERIOR ⊊ EXPTIME ⊊ ELEMENTAL ⊊ PR ⊊ R

Mientras que ELEMENTARY contiene aplicaciones limitadas de exponenciación (por ejemplo, ), PR permite hiperoperadores más generales (por ejemplo, tetración ) que no están contenidos en ELEMENTARY. ${\displaystyle O(2^{2^{n}})}$

Definición

Las definiciones de funciones recursivas elementales son las mismas que para las funciones recursivas primitivas , excepto que la recursividad primitiva se reemplaza por suma acotada y producto acotado. Todas las funciones funcionan sobre los números naturales . Las funciones básicas, todas ellas recursivas elementales, son:

1. Función cero . Devuelve cero: f (x) = 0.
2. Función sucesora : f ( x ) = x + 1. A menudo, esto se denota por S , como en 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, f ( a , b ) = a es una función de proyección.
4. Función de resta : f ( x , y ) = x − y si y < x , o 0 si y ≥ x . 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. En f ( x ₁ , ..., x _n ) = h ( g ₁ ( x ₁ , ..., x _n ), ..., g _m ( x ₁ , ..., x _n )) es elemental recursivo si h es recursivo elemental y cada g _i es recursivo elemental.
2. Suma acotada : es recursiva elemental si g es recursiva elemental. ${\displaystyle f(m,x_{1},\ldots ,x_{n})=\sum \limits _{i=0}^{m}g(i,x_{1},\ldots ,x_{n})}$
3. Producto acotado : es recursivo elemental si g es recursivo elemental. ${\displaystyle f(m,x_{1},\ldots ,x_{n})=\prod \limits _{i=0}^{m}g(i,x_{1},\ldots ,x_{n})}$

Base para PRIMARIA

La clase de funciones elementales coincide con la clausura respecto de la composición de las proyecciones y uno de los siguientes conjuntos de funciones: , , , donde es la función de resta definida anteriormente. ^{[1] [2]} ${\displaystyle \{n+1,n\,{\stackrel {.}{-}}\,m,\lfloor n/m\rfloor ,n^{m}\}}$ ${\displaystyle \{n+m,n\,{\stackrel {.}{-}}\,m,\lfloor n/m\rfloor ,2^{n}\}}$ ${\displaystyle \{n+m,n^{2},n\,{\bmod {\,}}m,2^{n}\}}$ ${\displaystyle n\,{\stackrel {.}{-}}\,m=\max\{n-m,0\}}$

Funciones recursivas elementales inferiores

Las funciones recursivas elementales inferiores siguen las definiciones anteriores, excepto que el producto acotado no está permitido. 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. ^{[3] [4]}

Mientras que las funciones recursivas elementales tienen potencialmente un crecimiento más que exponencial, las funciones recursivas elementales inferiores tienen un crecimiento polinomial.

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. ^{[4] [5]} Es decir, una función acotada por un polinomio es elemental inferior si y solo si se puede expresar usando una composición de las siguientes funciones: proyecciones, , , , , una función exponencial ( o ) con la siguiente restricción de la estructura de las fórmulas: la fórmula no puede tener más de dos pisos respecto de un exponente (por ejemplo, tiene 1 piso, tiene 2 pisos, tiene 3 pisos). Aquí hay un AND bit a bit de n y m . ${\displaystyle n+1}$ ${\displaystyle nm}$ ${\displaystyle n\,{\stackrel {.}{-}}\,m}$ ${\displaystyle n\wedge m}$ ${\displaystyle \lfloor n/m\rfloor }$ ${\displaystyle 2^{n}}$ ${\displaystyle n^{m}}$ ${\displaystyle xy(z+1)}$ ${\displaystyle (x+y)^{yz+x}+z^{x+1}}$ ${\displaystyle 2^{2^{x}}}$ ${\displaystyle n\wedge m}$

Caracterización descriptiva

En complejidad descriptiva , ELEMENTARY es igual a la clase HO de lenguajes que pueden describirse mediante una fórmula de lógica de orden superior . ^[6] Esto significa que cada lenguaje en la clase de complejidad ELEMENTAL corresponde a una fórmula de orden superior que es verdadera para y solo para los elementos del lenguaje. Más precisamente, donde ⋯ indica una torre de i exponenciaciones y es la clase de consultas que comienzan con cuantificadores existenciales de i ésimo orden y luego una fórmula de ( i  − 1) ésimo orden. ${\displaystyle {\mathsf {NTIME}}\left(2^{2^{\cdots {2^{O(n)}}}}\right)=\exists {}{\mathsf {HO}}^{i}}$ ${\displaystyle \exists {}{\mathsf {HO}}^{i}}$

Ver también

• Aritmética de funciones elementales
• Función recursiva primitiva
• Jerarquía de Grzegorczyk
• TIEMPO EXPLICADO

Notas

1. Mazzanti, S (2002). "Bases sencillas para clases de funciones recursivas primitivas". Lógica Matemática Trimestral . 48 : 93-104. doi :10.1002/1521-3870(200201)48:1<93::aid-malq93>3.0.co;2-8.
2. SS Marchenkov, "Superposiciones de funciones aritméticas elementales", Journal of Applied and Industrial Mathematics , septiembre de 2007, volumen 1, número 3, págs. 351-360, doi :10.1134/S1990478907030106.
3. Th. Skolem , "Demostración de algunos teoremas en conjuntos recursivamente enumerables", Notre Dame Journal of Formal Logic , 1962, volumen 3, número 2, págs. 65-74, doi :10.1305/ndjfl/1093957149.
4. SA Volkov, "Sobre la clase de funciones elementales de Skolem", Journal of Applied and Industrial Mathematics , 2010, volumen 4, número 4, págs. 588-599, doi :10.1134/S1990478910040149.
5. Volkov, Sergey (2016). "Bases finitas con respecto a la superposición en clases de funciones recursivas elementales [tesis]". arXiv : 1611.04843 [cs.CC].
6. Lauri Hella y José María Turull-Torres (2006), "Computación de consultas con lógica de orden superior", Informática Teórica , 355 (2): 197–214, doi : 10.1016/j.tcs.2006.01.009 , ISSN  0304 -3975

Referencias

• Rose, HE, Subrecursión: funciones y jerarquías , Oxford University Press , 1984. ISBN 0-19-853189-3