En la teoría de la complejidad computacional , la clase de complejidad ELEMENTARY de funciones recursivas elementales es la unión de las clases
El nombre fue acuñado por László Kalmár , en el contexto de funciones recursivas e indecidibilidad ; la mayoría de los problemas están lejos de ser elementales. Algunos problemas recursivos naturales se encuentran fuera de ELEMENTARY y, por lo tanto, no son ELEMENTALES . Más notablemente, hay problemas recursivos primitivos que no están en ELEMENTARY. Sabemos
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.
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 elementales recursivas, son:
- Función cero . Devuelve cero: f (x) = 0.
- 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 adición.
- Funciones de proyección : se utilizan para ignorar argumentos. Por ejemplo, f ( a , b ) = a es una función de proyección.
- 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.
- Composición : aplicar valores de alguna función recursiva elemental como argumento a otra función recursiva elemental. En f ( x 1 , ..., x n ) = h ( g 1 ( x 1 , ..., x n ), ..., g m ( x 1 , ..., x n )) es elemental recursivo si h es recursivo elemental y cada g i es recursivo elemental.
- Suma acotada :es elemental recursiva si g es elemental recursiva.
- Producto acotado :es elemental recursiva si g es elemental recursiva.
Base para ELEMENTAL
La clase de funciones elementales coincide con el cierre con respecto a la composición de las proyecciones y uno de los siguientes conjuntos de funciones: , , , dónde es la función de resta definida anteriormente. [1] [2]
Funciones recursivas elementales inferiores
Las funciones recursivas elementales inferiores siguen las definiciones anteriores, excepto que no se permite el producto acotado. Es decir, una función recursiva elemental inferior debe ser un cero, sucesor o función 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 más que un crecimiento 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 polinomios es elemental inferior si y solo si se puede expresar utilizando una composición de las siguientes funciones: proyecciones,, , , , , una función exponencial ( o ) 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, tiene 1 piso, tiene 2 pisos, tiene 3 plantas). Aquíes un AND bit a bit de n y 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 idioma en la clase de complejidad ELEMENTAL corresponde a una fórmula de orden superior que es verdadera para, y solo para, los elementos del idioma. Más precisamente,, donde ⋯ indica una torre de i exponenciaciones yes la clase de consultas que comienzan con cuantificadores existenciales de i- ésimo orden y luego una fórmula de ( i - 1) -ésimo orden.
Ver también
Notas
- ^ Mazzanti, S (2002). "Bases simples para clases de funciones recursivas primitivas". Trimestral de lógica matemática . 48 : 93-104. doi : 10.1002 / 1521-3870 (200201) 48: 1 <93 :: aid-malq93> 3.0.co; 2-8 .
- ^ SS Marchenkov, "Superposiciones de funciones aritméticas elementales", Revista de matemáticas aplicadas e industriales , septiembre de 2007, volumen 1, número 3, pp 351-360, doi : 10.1134 / S1990478907030106 .
- ^ Ju. Skolem , "Prueba de algunos teoremas sobre conjuntos recursivamente enumerables", Notre Dame Journal of Formal Logic , 1962, Volumen 3, Número 2, págs. 65-74, doi : 10.1305 / ndjfl / 1093957149 .
- ^ a b S. A. Volkov, "Sobre la clase de funciones elementales de Skolem", Journal of Applied and Industrial Mathematics , 2010, Volumen 4, Número 4, pp 588-599, doi : 10.1134 / S1990478910040149 .
- ^ Volkov, Sergey (2016). "Bases finitas con respecto a la superposición en clases de funciones elementales recursivas [disertación]". arXiv : 1611.04843 .
- ^ Lauri Hella y José María Turull-Torres (2006), "Consultas informáticas con lógicas 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, Subrecursion: Funciones y jerarquías , Oxford University Press , 1984. ISBN 0-19-853189-3