Question

Question: Is a compiler a kind of Gödel numbering program?

Wikipedia tells us that a compiler is: "In computing, a compiler is a computer program that translates computer code written in one programming language (the source language) into another language (the target language)". https://en.wikipedia.org/wiki/Compiler

Also wikipedia tells us: "a Gödel numbering is a function that assigns to each symbol and well-formed formula of some formal language a unique natural number, called its Gödel number". https://en.wikipedia.org/wiki/G%C3%B6del_numbering

Work done: My intuition says yes. Here is my line of thought: a programming language is a formal language. Every program is a well-formed formula and a compiler assigns each symbol of this formula to a binary representation of a number that the computer can read. (detail: a computer is a universal Turing machine, so it can perform arithmetic)

But, I don't know the details of how compilers work, so I came here to ask if my reasoning is correct.

Was it helpful?

Solution

No. Consider the following two C functions:

int f(int a) {
    return a * 2;
}

int g(int a) {
    return a + a;
}

If we're being a bit liberal here, both are "well-formed formula of some formal language". Yet most C compilers with optimization turned on will compile these two functions to the exact same code. This violates the uniqueness of a Gödel numbering.

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top