- Mayoración
-
Una función f (de orden 1) mayora a una g (de orden n) si y sólo si:
Notación:
Contenido
Teoremas referidos a la mayoración
- Toda función recursiva primitiva está mayorada por la función de Ackermann.
- Recordemos las propiedades de la función de Ackermann:
(1)
b ,\; f_{k}(a) > f_{k}(b)" border="0"> (2)
x" border="0"> (3)
f_{k}(x)" border="0"> (4)
- Recordemos las propiedades de la función de Ackermann:
Lemas
Lema (A)
Las funciones recursivas base está mayoradas por f0 Sea X = x1,x2,..,xn
Demostración:
Lema (B)
Si
entonces
Demostración:
Si
entonces
Entonces,
Usando la hipótesis y fk es creciente (2).
Por definición de función potencia:
Aplicando (4) varias veces ...
Por definición:
Por lo tanto,
- Toda función recursiva primitiva está mayorada por la función de Ackermann.
Wikimedia foundation. 2010.