En la teoría de la computabilidad , la teoría de la complejidad computacional y la teoría de la prueba , una jerarquía de rápido crecimiento (también llamada jerarquía de Grzegorczyk extendida ) es una familia indexada ordinal de funciones rápidamente crecientes f α : N → N (donde N es el conjunto de números naturales { 0, 1, ...} y α van hasta algunos grandes ordinales contables ). Un ejemplo principal es la jerarquía de Wainer , o jerarquía de Löb-Wainer , que es una extensión de todo α < ε 0. Dichas jerarquías proporcionan una forma natural de clasificar funciones computables de acuerdo con la tasa de crecimiento y la complejidad computacional .
Definición
Sea μ un ordinal contable grande tal que a cada ordinal límite α <μ se le asigna una secuencia fundamental (una secuencia estrictamente creciente de ordinales cuyo supremo es α). Una jerarquía de funciones de rápido crecimiento f α : N → N , para α <μ, se define de la siguiente manera:
- si α es un ordinal límite.
Aquí f α n ( n ) = f α ( f α (... ( f α ( n )) ...)) denota la n- ésima iteración de f α aplicada an , y α [ n ] denota la n- ésima elemento de la secuencia fundamental asignado al ordinal límite α. (Una definición alternativa toma el número de iteraciones como n +1, en lugar de n , en la segunda línea de arriba).
La parte inicial de esta jerarquía, que comprende las funciones f α con índice finito (es decir, α <ω), a menudo se denomina jerarquía de Grzegorczyk debido a su estrecha relación con la jerarquía de Grzegorczyk ; tenga en cuenta, sin embargo, que la primera es aquí una familia indexada de funciones f n , mientras que la última es una familia indexada de conjuntos de funciones. (Consulte Puntos de interés a continuación).
Generalizando la definición anterior aún más, una jerarquía iteración rápido se obtiene tomando f 0 a ser cualquier función creciente g: N → N .
Para los ordinales límite no mayores que ε 0 , existe una definición natural sencilla de las secuencias fundamentales (consulte la jerarquía de Wainer a continuación), pero más allá de ε 0 la definición es mucho más complicada. Sin embargo, esto es posible mucho más allá del ordinal de Feferman-Schütte, Γ 0 , hasta al menos el ordinal de Bachmann-Howard . Usando funciones psi de Buchholz, uno puede extender esta definición fácilmente al ordinal de iterado transfinitamente-comprensión (ver Jerarquía analítica ).
Se cree que es poco probable una extensión completamente especificada más allá de los ordinales recursivos ; por ejemplo, Prӧmel et al. [1991] (p. 348) nótese que en tal intento "incluso surgirían problemas en la notación ordinal".
La jerarquía de Wainer
La jerarquía de Wainer es la jerarquía particular de funciones f α (α ≤ ε 0 ) de rápido crecimiento que se obtiene al definir las secuencias fundamentales de la siguiente manera [Gallier 1991] [Prӧmel, et al., 1991]:
Para los ordinales límite λ < ε 0 , escritos en forma normal de Cantor ,
- si λ = ω α 1 + ... + ω α k − 1 + ω α k para α 1 ≥ ... ≥ α k − 1 ≥ α k , entonces λ [ n ] = ω α 1 + ... + ω α k − 1 + ω α k [ n ],
- si λ = ω α + 1 , entonces λ [ n ] = ω α n ,
- si λ = ω α para un límite ordinal α, entonces λ [ n ] = ω α [ n ] ,
y
- si λ = ε 0 , tome λ [0] = 0 y λ [ n + 1] = ω λ [ n ] como en [Gallier 1991]; alternativamente, tome la misma secuencia excepto que comienza con λ [0] = 1 como en [Prӧmel, et al., 1991].
Para n > 0, la versión alternativa tiene un ω adicional en la torre exponencial resultante, es decir, λ [ n ] = ω ω . . . ω con n omegas.
Algunos autores utilizan definiciones ligeramente diferentes (p. Ej., Ω α + 1 [ n ] = ω α ( n + 1 ), en lugar de ω α n ), y algunos definen esta jerarquía solo para α <ε 0 (excluyendo así f ε 0 de La jerarquía).
Para continuar más allá de ε 0 , consulte las secuencias fundamentales de la jerarquía de Veblen .
Puntos de interés
A continuación, se muestran algunos puntos de interés relevantes sobre las jerarquías de rápido crecimiento:
- Cada f α es una función total . Si las secuencias fundamentales son computables (por ejemplo, como en la jerarquía de Wainer), entonces cada f α es una función computable total .
- En la jerarquía de Wainer, f α está dominada por f β si α <β. (Para dos funciones cualesquiera f , g : N → N , se dice que f domina g si f ( n )> g ( n ) para todas las n suficientemente grandes ). La misma propiedad se cumple en cualquier jerarquía de rápido crecimiento con secuencias fundamentales que satisfagan la llamada propiedad de Bachmann . (Esta propiedad es válida para la mayoría de los ordenamientos de pozos naturales). [Se necesita aclaración ]
- En la jerarquía de Grzegorczyk, cada función recursiva primitiva está dominada por algún f α con α <ω. Por tanto, en la jerarquía de Wainer, cada función recursiva primitiva está dominada por f ω , que es una variante de la función de Ackermann .
- Para n ≥ 3, el conjuntoen la jerarquía de Grzegorczyk se compone solo de aquellas funciones de múltiples argumentos totales que, para argumentos suficientemente grandes, son computables dentro del tiempo limitado por alguna iteración fija f n -1 k evaluada en el argumento máximo.
- En la jerarquía de Wainer, cada f α con α < ε 0 es computable y probablemente total en la aritmética de Peano .
- Cada función computable que es demostrablemente total en la aritmética de Peano está dominada por algún f α con α < ε 0 en la jerarquía de Wainer. Por tanto, f ε 0 en la jerarquía de Wainer no es demostrablemente total en la aritmética de Peano.
- La función de Goodstein tiene aproximadamente la misma tasa de crecimiento ( es decir, cada una está dominada por alguna iteración fija de la otra) que f ε 0 en la jerarquía de Wainer, dominando cada f α para la cual α < ε 0 , y por lo tanto no es demostrablemente total en Peano Aritmética.
- En la jerarquía de Wainer, si α <β < ε 0 , entonces f β domina todas las funciones computables dentro del tiempo y el espacio delimitadas por algunas iteraciones fijas f α k .
- La función TREE de Friedman domina f Γ 0 en una jerarquía de rápido crecimiento descrita por Gallier (1991).
- La jerarquía de Wainer de funciones f α y la jerarquía de Hardy de funciones h α están relacionadas por f α = h ω α para todo α <ε 0 . La jerarquía de Hardy "alcanza" a la jerarquía de Wainer en α = ε 0 , de modo que f ε 0 y h ε 0 tienen la misma tasa de crecimiento, en el sentido de que f ε 0 ( n -1) ≤ h ε 0 ( n ) ≤ f ε 0 ( n +1) para todo n ≥ 1. (Gallier 1991)
- Girard (1981) y Cichon y Wainer (1983) mostraron que la jerarquía de funciones g α de crecimiento lento alcanza la misma tasa de crecimiento que la función f ε 0 en la jerarquía de Wainer cuando α es el ordinal de Bachmann-Howard . Girard (1981) mostró además que la jerarquía de crecimiento lento g α alcanza la misma tasa de crecimiento que f α (en una jerarquía de crecimiento rápido particular) cuando α es el ordinal de la teoría ID <ω de iteraciones finitas arbitrarias de una definición inductiva . (Wainer 1989)
Funciones en jerarquías de rápido crecimiento
Las funciones en niveles finitos (α <ω) de cualquier jerarquía de rápido crecimiento coinciden con las de la jerarquía de Grzegorczyk: (usando hiperoperación )
- f 0 ( n ) = n + 1 = 2 [1] n - 1
- f 1 ( norte ) = f 0 norte ( norte ) = norte + norte = 2 norte = 2 [2] norte
- f 2 ( n ) = f 1 n ( n ) = 2 n · n > 2 n = 2 [3] n para n ≥ 2
- f k +1 ( n ) = f k norte ( n )> (2 [ k + 1]) n norte ≥ 2 [ k + 2] n para n ≥ 2, k <ω.
Más allá de los niveles finitos están las funciones de la jerarquía de Wainer (ω ≤ α ≤ ε 0 ):
- f ω ( n ) = f n ( n )> 2 [ n + 1] n > 2 [ n ] ( n + 3) - 3 = A ( n , n ) para n ≥ 4, donde A es la función de Ackermann ( de la cual f ω es una versión unaria).
- f ω + 1 ( n ) = f ω n ( n ) ≥ f n [ n + 2] n ( n ) para todo n > 0, donde n [ n + 2] n es el n- ésimo número de Ackermann .
- f ω + 1 (64)> f ω 64 (6)> Número de Graham (= g 64 en la secuencia definida por g 0 = 4, g k +1 = 3 [ g k + 2] 3). Esto se sigue observando f ω ( n )> 2 [ n + 1] n > 3 [ n ] 3 + 2, y por lo tanto f ω ( g k + 2)> g k +1 + 2.
- f ε 0 ( n ) es la primera función en la jerarquía de Wainer que domina la función de Goodstein .
Referencias
- Buchholz, W .; Wainer, SS (1987). "Funciones probables computables y la jerarquía de rápido crecimiento". Logic and Combinatorics , editado por S. Simpson, Contemporary Mathematics, Vol. 65, AMS, 179-198.
- Cichon, EA; Wainer, SS (1983), "El crecimiento lento y las jerarquías de Grzegorczyk", The Journal of Symbolic Logic , 48 (2): 399–408, doi : 10.2307 / 2273557 , ISSN 0022-4812 , MR 0704094
- Gallier, Jean H. (1991), "¿Qué tiene de especial el teorema de Kruskal y el ordinal Γ 0 ? Una revisión de algunos resultados en la teoría de la prueba" , Ann. Pure Appl. Lógica , 53 (3): 199–260, doi : 10.1016 / 0168-0072 (91) 90022-E , MR 1129778[ enlace muerto permanente ] PDF: [1] . (En particular la Sección 12, págs. 59-64, "Un vistazo a las jerarquías de funciones de crecimiento rápido y lento".)
- Girard, Jean-Yves (1981), "Π 1 2 -logic. I. Dilators", Annals of Mathematical Logic , 21 (2): 75-219, doi : 10.1016 / 0003-4843 (81) 90016-4 , ISSN 0003-4843 , MR 0656793
- Löb, MH; Wainer, SS (1970), "Jerarquías de funciones teóricas de números", Arch. Matemáticas. Logik , 13. Corrección, Arch. Matemáticas. Logik , 14, 1971. Parte I doi : 10.1007 / BF01967649 , Parte 2 doi : 10.1007 / BF01973616 , Correcciones doi : 10.1007 / BF01991855 .
- Prömel, HJ; Thumser, W .; Voigt, B. "Funciones de crecimiento rápido basadas en los teoremas de Ramsey", Matemáticas discretas , v.95 n.1-3, p. 341-358, diciembre de 1991 doi : 10.1016 / 0012-365X (91) 90346-4 .
- Wainer, SS (1989). "Crecimiento lento versus crecimiento rápido". Revista de lógica simbólica . 54 (2): 608–614. JSTOR 2274873 .