HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

Can a RAM calculate its own Gödel number?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
cannumbergödelitsowncalculateram

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#59410, answer score: 17

Revisions (0)

No revisions yet.