Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Gödel numbering for sequences

  1. Nov 26, 2014 #1


    User Avatar
    Gold Member

    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. jcsd
  3. Dec 1, 2014 #2
    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?
  4. Dec 1, 2014 #3


    Staff: Mentor

    I moved this thread from the Computer Science/Programming section to here. I think this forum section is a better fit.
  5. Dec 1, 2014 #4


    User Avatar
    Gold Member

    Thanks for the actions, Greg Bernhardt and Mark 44. Let me state the question a bit better, including correcting a couple of mistakes in my original post.
    In showing the existence of an effective Gödel numbering for sequences, Wikipedia:
    in one direction: it takes a known sequence (a1,...an) and establishes a coding procedure which ends up with the Gödel number a ( no problem so far).

    Then, to show that a decoding procedure β exists so that β(a,i) = ai : here's where it gets a bit confusing.
    [1] First it finds m such that m is divisible by all the non-zero indices, and then:
    [2] constructs a sequence of pairwise coprime numbers mi
    [3] using the CRT (Chinese Remainder Theorem] it shows that, using a pairing function π, that π(x0,m) = a, whereby x0 satisfies the system of equations x0 ≡ aimod mi, so that rem(x0,mi) = ai.
    By now I am totally lost. Therefore I presume that I have laid out the general argument incorrectly. Could someone either correct this or direct me to a web site which lays out the argument a bit more clearly than Wikipedia does? (Yes, I know I can "just" google it, but I didn't come up with anything.)
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook