La minimización de circuitos es el problema para minimizar el tamaño de un circuito dado. ¿Hay algo similar para los programas generales?
En particular mi pregunta es:
¿Existen algoritmos para minimizar el número de instrucciones para un programa dado? Sé que es un problema indecidible, pero no estoy buscando una solución que devuelva algo óptimo.
Si bien uno puede aplicar transformaciones de compilador preexistentes para lograr esto, estoy buscando algo donde no tenga que definir un conjunto de transformaciones y algoritmos muy estrechos para buscarlos de antemano.
Editar: La otra pregunta que tengo es si uno puede tener un cálculo que sea sólido y completo que nos permita explorar todo el espacio de esos programas semánticamente equivalentes o si eso no es posible.
Respuestas:
Existe un algoritmo ingenuo para programas con entradas de tamaño acotado: enumere todos los programas en orden de longitud creciente (o tiempo de ejecución, que es una función acotada de la longitud). Si puede probar que el programa es equivalente al original, deténgase; de lo contrario sigue buscando.
Este algoritmo es sólido. Para que se complete, debe poder demostrar que todos los programas rechazados no son equivalentes al original. Esto es posible en modelos de máquina finita, siempre que tenga un límite para el tamaño de entrada.
Tenga en cuenta que cuando el tiempo de ejecución del programa depende de la entrada, puede que no haya una solución óptima. Si busca, por ejemplo, un límite en el peor de los casos, muy rápidamente se encontrará con equivalencias indecidibles cuando cuantifique todas las entradas ilimitadas posibles, y con problemas imposibles de resolver si las entradas están limitadas.
Hace una década, "Denali: un superoptimizador dirigido por objetivos" por Rajeev Joshi, Greg Nelson y Keith Randall pudo encontrar programas óptimos de aproximadamente 5 instrucciones de máquina. No he visto resultados más recientes.
fuente