En el libro de Andrew W. Appel, Modern Compiler Implementation in ML , dice en el capítulo 17 que la teoría de la computabilidad muestra que siempre será posible inventar nuevas transformaciones optimizadoras y procede a demostrar que un compilador completamente optimizador resolverá el problema de detención: un programa Q que no produce salida y nunca se detiene se puede reemplazar fácilmente por su representación óptima, Opt (Q) , que es "L: goto L". Por lo tanto, un compilador completamente optimizado puede resolver el problema de detención.
Entonces mi pregunta es esta: ¿Existe un compilador completamente optimizado para terminar programas? Mis únicos pensamientos son los siguientes: aunque se garantiza que un programa finalizará, aún puede ser arbitrariamente complejo, y para cualquier compilador de optimización concreto, C, uno podría construir un programa que tome C como entrada y de alguna manera produzca un programa peor. algún tipo de caja de esquina.
Además, ¿cuáles son las implicaciones de restringirnos a la terminación de programas?
fuente
Respuestas:
Supongo que está interesado en la optimización del tiempo de ejecución. Como he escrito en mi comentario, eso no especifica suficientemente el objetivo: ¿una optimización reduce el tiempo de ejecución en cualquier entrada, cada entrada, todas las entradas del peor de los casos o incluso en promedio ?
Mostraré que todos ellos son imposibles. La prueba se extiende a la optimización de la duración del programa.
Recuerde que el siguiente problema no es computable:
Tenga en cuenta además que, dada una gramática sin contexto , podemos codificar, por ejemplo, el algoritmo CYK para esa gramática; denotar este algoritmo por C Y K G . Observamos que C Y K G termina para todas las entradas (desde Σ ∗ ).G CYKG CYKG Σ∗
Ahora suponga que hay un optimizador que, dado un algoritmo A que siempre termina , genera un algoritmo equivalente al resultado que es óptimo con respecto al tiempo de ejecución. Claramente,Opt A
y así hemos construido un decisor para un problema incontestable, contradiciendo la suposición.
fuente