En informática y matemáticas , un teorema de pleno empleo es un término utilizado, a menudo con humor, para referirse a un teorema que establece que ningún algoritmo puede realizar de manera óptima una tarea particular realizada por una determinada clase de profesionales. El nombre surge porque dicho teorema garantiza que existe un margen infinito para seguir descubriendo nuevas técnicas para mejorar la forma en que se realiza al menos alguna tarea específica.
Por ejemplo, el teorema de pleno empleo para los escritores de compiladores establece que no existe un compilador que optimice el tamaño demostrablemente perfecto, ya que tal prueba para el compilador tendría que detectar cálculos no terminantes y reducirlos a una instrucción infinita. bucle . Por lo tanto, la existencia de un compilador que optimice el tamaño demostrablemente perfecto implicaría una solución al problema de la detención , que no puede existir. Esto también implica que siempre puede haber un mejor compilador, ya que no puede existir la prueba de que uno tiene el mejor compilador. Por lo tanto, los escritores de compiladores siempre podrán especular que tienen algo que mejorar. Un ejemplo similar en informática práctica es la idea de que no hay comida gratis en la búsqueda y optimización , que establece que no puede existir ningún solucionador eficiente de propósito general y, por lo tanto, siempre habrá algún problema particular cuya solución más conocida podría mejorarse.
De manera similar, los teoremas de incompletitud de Gödel han sido llamados teoremas de pleno empleo para los matemáticos. Tareas como la escritura y detección de virus , el filtrado de spam y la ruptura de filtros también están sujetas al teorema de Rice .