# Gödel numbering for sequences

1. Nov 26, 2014

First, this is not the same question as
It concerns a different encoding procedure, hence a different decoding one.

My question concerns the argument in http://en.wikipedia.org/wiki/Gödel_numbering_for_sequences
for the existence of an effective decoding function β corresponding to the effective coding π for the Gödel number for sequences as given in that article : that is, given this procedure for generating the Gödel number from a sequence, and given the Godel number G of an unknown sequence (k1,...kn), to prove the existence of β such that for all for all 0<i<n, β(G,i) =ki.

Wikipedia leaves the " for all 0<i<n " implicit, so I will follow that abuse of notation as well:

If I understand that argument correctly:
First, we assume that we can choose misuch that
[*] mi>ai
[**] all mi are coprime to one another.
(This can even be done constructively.)

Then since we know that (k1,...kn) exists, we know that a least solution x to the congruences
x ≡ ai mod mi
exists. Call it X.
We can construct a recursive function rem(a,b) so that rem(a,b)=(a mod b), so since we know X exists, we know that a procedure rem(X,mi) = ai exists.

OK, something rankles. Apparently I am not laying down the outline correctly , because it sounds slightly circular to me. Can anyone tell me what is wrong in my summary?

(It would be nice if there were a constructive proof.....)

(Also: the construction of the miso as to fulfill [*] and [**] would seem to require rather huge numbers: if [*] is fulfilled, then one just takes m = lcm(1,..., n-1) and mi= (i+1)*m + 1. But the only way I can see to make sure that [*] is fulfilled is to set m = lcm(1,...n-1, G), where G is the given Gödel number of the sequence; this ends up with rather large mi, so would it still be effective?)

2. Dec 1, 2014

### Greg Bernhardt

Thanks for the post! This is an automated courtesy bump. Sorry you aren't generating responses at the moment. Do you have any further information, come to any new conclusions or is it possible to reword the post?

3. Dec 1, 2014

### Staff: Mentor

I moved this thread from the Computer Science/Programming section to here. I think this forum section is a better fit.

4. Dec 1, 2014