Siguiente: Complejidades condicionales Un nivel arriba: Presentación de la teoría Anterior: Observación

Observaciones

1.

En la clase de funciones computables-Turing existe una función S que absorbe a todas:

$$\forall T\in\{\mbox{\rm Recursivas}\}\;\exists c_{S,T}:\;K_S(x)\leq K_T(x) + c_{S,T}\;\forall x.$$

Tal S corresponde a una función universal. Así pues, las funciones universales son óptimas.

2.

Cualesquiera dos funciones óptimas son equivalentes, es decir, si S,T son dos funciones óptimas

$$\exists c_{S,T}:\;\vert K_S(x)- K_T(x)\vert\leq c_{S,T}.$$