Teorema del aumento de velocidad de Blum

En Teoría de la complejidad computacional el teorema del aumento de velocidad de Blum, dado primero por Manuel Blum en 1967, es un teorema importante sobre la complejidad de funciones computables.

Cada función computable tiene un número infinito de representaciones en cierto lenguaje de programación. En la teoría de algoritmos, uno suele tener que encontrar el programa con la menor complejidad por una función computable dada y una medida de complejidad. El teorema del aumento de velocidad de Blum dice que por cualquier medida de complejidad hay funciones computables que no tienen un programa mínimo.

Véase también

• Teorema del aumento de velocidad