Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

share|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. –  Arthur Fischer Nov 29 '12 at 10:04
add comment

1 Answer

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|improve this answer
add comment

Your Answer

 
discard

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.