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.


1 Answer 1


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.

  • 1
    $\begingroup$ thanks, nice simple counterexample. $\endgroup$ Jul 12, 2020 at 20:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.