Can a RAM calculate its own Gödel number?

Problem Detail: 

You can get the Gödel number of a RAM by making it a list of commands and making this list an integer.

So, what I thought is something like "The RAM that would return its own Gödel number (say, $x$) would have to have the information $x$ in it, so the integer would be greater than $x$, so it would not return its own Gödel number."

But then I noticed that for specific numbers you could do compressing, such as calculating $10^{9999}$ instead of writing 100000...000 in the code of the RAM. Probably the Gödel number would not be $10^{9999}$ though, but at least it could be.

Question: Is there a RAM that calculates its own Gödel number? Can there be such?

Asked By : palsch

Answered By : David Richerby

Consider the computable function $Q\colon \mathbb{N}\times\mathbb{N}\to\mathbb{N}$ given by $Q(x,y) = x$. By Kleene's second recursion theorem, there is some $p$ such that the program with Gödel number $p$ computes the function $f(y) = Q(p,y)=p$, i.e., a program which outputs $p$ for every input. This is exactly the program you're looking for: for any input, it outputs its own Gödel number.

Such a program is known as a quine, and they exist in any Turing-powerful model of computation.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/59410