12
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ By the way, palsch, here's a cool Numberphile video about your user icon. :-) $\endgroup$ – David Richerby Jun 9 '16 at 9:30
  • 1
    $\begingroup$ @DavidRicherb These are not only pixels but the Ulam spiral. I programmed this some time ago for my math teacher. Purple pixels are prime twins, red ones are other primes and the orange pixel in the middle is 1. :-) $\endgroup$ – palsch Jun 9 '16 at 14:05
  • 1
    $\begingroup$ Nice! So here's a Numberphile video that's literally about your user icon! :-D $\endgroup$ – David Richerby Jun 9 '16 at 14:31
17
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can you be sure to run this program in the limited memory of the ram? I suppose here RAM means random access memory... $\endgroup$ – Per Alexandersson Jun 8 '16 at 22:39
  • 6
    $\begingroup$ @PerAlexandersson No, it refers to a Random-Access Machine, a Turing-powerful model of computation. $\endgroup$ – David Richerby Jun 8 '16 at 23:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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