La jerarquía Grzegorczyk ( / ɡ r ɛ ɡ ɔr tʃ ə k / , pronunciación polaco: [ɡʐɛɡɔrt͡ʂɨk] ), el nombre del lógico polaco Andrzej Grzegorczyk , es una jerarquía de funciones utilizadas en teoría de la computabilidad (Wagner y Wechsung 1986: 43). Cada función en la jerarquía de Grzegorczyk es una función recursiva primitiva, y cada función recursiva primitiva aparece en la jerarquía en algún nivel. La jerarquía se ocupa de la velocidad a la que crecen los valores de las funciones; intuitivamente, las funciones en el nivel inferior de la jerarquía crecen más lentamente que las funciones en los niveles superiores.
Definición
Primero introducimos un conjunto infinito de funciones, denotado E i para algún número natural i . Definimos y . Es decir, E 0 es la función de suma y E 1 es una función unaria que eleva al cuadrado su argumento y suma dos. Entonces, para cada n mayor que 1, definimos, es decir, la x -ésima iteración de evaluado en 2.
A partir de estas funciones definimos la jerarquía de Grzegorczyk. , el n -ésimo conjunto de la jerarquía, contiene las siguientes funciones:
- E k para k < n
- la función cero ( Z ( x ) = 0);
- la función sucesora ( S ( x ) = x + 1);
- las funciones de proyección ();
- las composiciones (generalizadas) de funciones en el conjunto (si h , g 1 , g 2 , ... y g m están en, luego es también) [nota 1] ; y
- los resultados de la recursividad limitada (primitiva) aplicada a funciones en el conjunto, (si g , h y j están en y para todo t y, y además y , entonces f está entambién) [nota 1]
En otras palabras, es el cierre del set con respecto a la composición de funciones y recursividad limitada (como se definió anteriormente).
Propiedades
Estos conjuntos forman claramente la jerarquía
porque son cierres sobre el 'arena .
Son subconjuntos estrictos (Rose 1984; Gakwaya 1997). En otras palabras
porque la hiperoperación es en pero no en .
- incluye funciones como x +1, x +2, ...
- proporciona todas las funciones de suma, como x + y , 4 x , ...
- proporciona todas las funciones de multiplicación, como xy , x 4
- proporciona todas las funciones de exponenciación, como x y , 2 2 2 x , y es exactamente las funciones recursivas elementales .
- proporciona todas las funciones de tetración , etc.
En particular, tanto la función y la función característica del predicado del teorema de la forma normal de Kleene son definibles de tal manera que se encuentran al nivelde la jerarquía de Grzegorczyk. Esto implica en particular que cada conjunto recursivamente enumerable es enumerable por algunos-función.
Relación con funciones recursivas primitivas
La definición de es el mismo que el de las funciones recursivas primitivas , PR , excepto que la recursividad es limitada (para algunos j en) y las funciones están explícitamente incluidos en . Por tanto, la jerarquía de Grzegorczyk puede verse como una forma de limitar el poder de la recursividad primitiva a diferentes niveles.
De este hecho se desprende claramente que todas las funciones en cualquier nivel de la jerarquía de Grzegorczyk son funciones recursivas primitivas (es decir, ) y por lo tanto:
También se puede demostrar que todas las funciones recursivas primitivas están en algún nivel de la jerarquía (Rose 1984; Gakwaya 1997), por lo tanto
y los decorados particionar el conjunto de funciones recursivas primitivas, PR .
Extensiones
La jerarquía de Grzegorczyk se puede ampliar a ordinales transfinitos . Estas extensiones definen una jerarquía de rápido crecimiento . Para hacer esto, las funciones generadoras deben definirse de forma recursiva para los ordinales límite (tenga en cuenta que ya se han definido de forma recursiva para los ordinales sucesores mediante la relación ). Si existe una forma estándar de definir una secuencia fundamental , cuyo límite ordinal es, entonces se pueden definir las funciones generadoras . Sin embargo, esta definición depende de una forma estándar de definir la secuencia fundamental. Rose (1984) sugiere una forma estándar para todos los ordinales α < ε 0 .
La extensión original se debió a Martin Löb y Stan S. Wainer (1970) y a veces se la denomina jerarquía de Löb-Wainer .
Ver también
Notas
- ^ a b Aquírepresenta una tupla de entradas para f . La notaciónsignifica que f toma un número arbitrario de argumentos y si, luego . En la notación, el primer argumento, t , se especifica explícitamente y el resto como la tupla arbitraria. Por tanto, si, luego . Esta notación permite definir la composición y la recursividad limitada para funciones, f , de cualquier número de argumentos.
Referencias
- Brainerd, WS, Landweber, LH (1974), Teoría de la Computación , Wiley, ISBN 0-471-09585-0
- Cichon, EA; Wainer, SS (1983), "El crecimiento lento y las jerarquías de Grzegorczyk", Journal of Symbolic Logic , 48 (2): 399–408, doi : 10.2307 / 2273557 , ISSN 0022-4812 , MR 0704094
- Gakwaya, J.–S. (1997), una encuesta sobre la jerarquía de Grzegorczyk y su extensión a través del modelo de computabilidad BSS
- Grzegorczyk, A (1953). "Algunas clases de funciones recursivas" (PDF) . Rozprawy matematyczne . 4 : 1–45.
- Löb, MH; Wainer, SS (1970). "Jerarquías de funciones teóricas de números I, II: una corrección". Archiv für Mathische Logik und Grundlagenforschung . 14 : 198-199. doi : 10.1007 / bf01991855 .
- Rose, HE, Subrecursion: Funciones y jerarquías , Oxford University Press, 1984. ISBN 0-19-853189-3
- Wagner, K. y Wechsung, G. (1986), Computational Complexity , Mathematics and its Applications v. 21. ISBN 978-90-277-2146-4