Definir un "problema" a ser un algoritmo aceptar un número natural y devolver 0 o 1 que devuelve 1 en al menos un n ∈ N . Cualquiera de tales n se llama una "solución" a A
Defina un "solucionador de problemas universal" como un algoritmo acepta un problema y devuelve una de sus soluciones. Por ejemplo, U puede funcionar haciendo un bucle sobre todos los números naturales y ejecutando su entrada en ellos hasta obtener 1 resultado (solo tiene que detenerse en una entrada válida)
Estoy interesado en explorar los límites de rendimiento en solucionadores de problemas universales
Dado que un solucionador de problemas universal y A un problema, denote t ( U , A ) el tiempo que le lleva a U producir resultados al aceptar la entrada A
Un solucionador de problemas universal se llama "eficiente" cuando para cualquier solucionador de problemas universal V , tenemos
Aquí depende de V pero no depende de A
¿Existen solucionadores de problemas universales eficientes?
EDITAR: Me di cuenta de que es posible cambiar las definiciones de "problema" y "solucionador de problemas universal" en algo un poco más elegante y esencialmente equivalente. Un "problema" es un algoritmo sin entrada que devuelve 0 o 1 (que se detiene). Un "solucionador de problemas universal" es un algoritmo que acepta un problema y devuelve su resultado. Es más o menos una máquina universal de Turing
La vieja definición puede reducirse a una nueva definición, ya que dado un problema en el sentido antiguo, podemos construir B un problema en el nuevo sentido que solo aplica el solucionador de problemas universal trivial del viejo sentido a A (el solucionador descrito en el texto anterior )
La nueva definición se puede reducir a la antigua, ya que dado un problema en el nuevo sentido, podemos construir A un problema en el antiguo sentido que solo calcula B y compara la entrada con el resultado
El ejemplo trivial de un solucionador de problemas universal de nuevo sentido es un algoritmo que simplemente ejecuta su entrada
fuente