Hacker News Reader

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"?

View on HN

No, 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

Yes, in order to be decodable it must be an injective mapping.

Reply on news.ycombinator.com