Hacker News new | past | comments | ask | show | jobs | submit login

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




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.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: