De Wikipedia, la enciclopedia libre
Ir a navegaciónSaltar a buscar

En la teoría de la computabilidad , la teoría de la complejidad computacional y la teoría de la prueba , la jerarquía de Hardy , llamada así por GH Hardy , es una familia de funciones indexadas ordinales h α :  N  →  N (donde N es el conjunto de números naturales , {0, 1,. ..}). Está relacionado con la jerarquía de rápido crecimiento y la jerarquía de crecimiento lento . La jerarquía se describió por primera vez en el artículo de Hardy de 1904, "Un teorema sobre los números cardinales infinitos".

Definición

Sea μ un ordinal contable grande tal que se asigne una secuencia fundamental a cada ordinal límite menor que μ. La jerarquía de Hardy de funciones h α :  N  →  N , para α  <  μ , se define de la siguiente manera:

  • si α es un ordinal límite.

Aquí α [ n ] denota el n- ésimo elemento de la secuencia fundamental asignado al ordinal límite  α . Una elección estandarizada de secuencia fundamental para todo  α  ≤  ε 0 se describe en el artículo sobre la jerarquía de rápido crecimiento .

Caicedo (2007) define una jerarquía de funciones de Hardy modificada utilizando las secuencias fundamentales estándar, pero con α [ n +1] (en lugar de α [ n ]) en la tercera línea de la definición anterior.

Relación con la jerarquía de rápido crecimiento

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 . Por tanto, para cualquier α <ε 0 , h α crece mucho más lentamente que f α . Sin embargo, la jerarquía de Hardy "se pone al día" con 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 )

Referencias