Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have a question about Gödel numbering, it is trivial but I would like to know how can you know the length of an expression through its Gödel number. ¿?

I think you can use a recursive function but I'm not sure which.....

share|cite|improve this question
Note that there is no unique Gödel numbering. You would need to provide more information about the particular numbering you are concerned with, though I am pretty sure that all Gödel numberings you see in the wild have the property that $n \mapsto \mathrm{length}(n)$ is (primitive) recursive. – arjafi Nov 29 '12 at 10:04

But of course! After all, the whole point about Gödel numbers is that you can mechanically decode them. So given a Gödel number $g$ in any sensible system of coding, there is an effective procedure which takes $g$ and spits out the coded expression $e$; and then there is another effective procedure which takes $e$ and spits out its length $l$. So putting them together, you'll get an effective computation which takes $g$ and spits out the length $l$ of the expression it codes for (if any).

So, by Church's Thesis that effective procedures compute recursive functions, there has to be a (partial) recursive function $f\colon\mathbb{N} \rightharpoondown \mathbb{N}$ such that $f(g) = l$ when $g$ indeed numbers an expression in your favoured system of coding.

However, which recursive function this is will depend on your system of coding. But if you use a traditional powers-of-primes Gödel-numbering scheme, then things will be pretty simple. $f$ will be the primitive recursive function that takes a number $g$ and returns $l$ when the $l$-th prime is greatest prime factor of $g$. Exercise: give a primitive recursive definition of that function!

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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