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.....
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.....
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!