¿Es un compilador un tipo de programa de numeración de Gödel?
-
29-09-2020 - |
Pregunta
Pregunta: es un compilador un tipo de programa de numeración de Gödel?
Wikipedia nos dice que un compilador es: "En computación, un compilador es un programa de computadora que traduce el código informático escrito en un lenguaje de programación (el idioma de origen) en otro idioma (el idioma de destino)". https://en.wikipedia.org/wiki/compiler
También nos dice Wikipedia: "Una numeración de Gödel es una función que asigna a cada símbolo y una fórmula bien formada de un lenguaje formal un número natural único, llamado su número de Gödel". https://en.wikipedia.org/wiki/g%c3%b6del_numbering
trabajo realizado : Mi intuición dice que sí. Aquí está mi línea de pensamiento: un lenguaje de programación es un lenguaje formal. Cada programa es una fórmula bien formada y un compilador asigna cada símbolo de esta fórmula a una representación binaria de un número que la computadora puede leer. (Detalle: una computadora es una máquina de turaje universal, por lo que puede realizar aritmética)
Pero, no sé los detalles de cómo funcionan los compiladores, así que vine aquí para preguntar si mi razonamiento es correcto.
Solución
no.Considere las siguientes dos funciones C:
int f(int a) {
return a * 2;
}
int g(int a) {
return a + a;
}
Si estamos siendo un poco liberales aquí, ambos son "fórmulas bien formadas de algún idioma formal".Sin embargo, la mayoría de los compiladores C con optimización activada, compilarán estas dos funciones al mismo código exacto.Esto viola la singularidad de una numeración de Gödel.