- #1
nomadreid
Gold Member
- 1,670
- 204
First, this is not the same question as
https://www.physicsforums.com/threads/goedel-numbering-decoding.484898/
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?)
https://www.physicsforums.com/threads/goedel-numbering-decoding.484898/
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?)