3 ms·
But doesn't Gödel numbering imply some sort of uniqueness, i.e. that each algorithm is only present once? Otherwise, wouldn't any language assigning a valid me
by kqr 3y ago
But doesn't Gödel numbering imply some sort of uniqueness, i.e. that each algorithm is only present once?
Otherwise, wouldn't any language assigning a valid meaning to any sequence of 0 and 1 be a Gödel numbering, even if only by saying that "an unrecognised sequence is a noop"?
- tromp 3y agoYes, in order to be decodable it must be an injective mapping.
- DougBTX 3y agoNo, an algorithm may be written in many ways, each of which would encode to a different Gödel number. > To encode an entire formula, which is a sequence of symbols, Gödel used the following system. Given a sequence (x_1, x_2, x_3, ..., x_n) of positive integers, the Gödel encoding of the sequence is the product of the first n primes raised to their corresponding values in the sequence https://en.wikipedia.org/wiki/Gödel_numbering https://en.wikipedia.org/wiki/Gödel_numbering