top | item 37202553

(no title)

sdfsdfsfds | 2 years ago

The standard theoretical technique for encoding a list of numbers as a single number is Gödel encoding. It can be applied as many times as you like—e.g. to encode a list of lists of numbers, or a list of lists of lists of numbers. https://en.wikipedia.org/wiki/G%C3%B6del_numbering

discuss

order

felixhandte|2 years ago

Sure, but Gödel encoding is pretty much purely a theoretical exercise. I'm not sure anyone anywhere has ever practically manipulated Gödel-encoded expressions in a useful way. His original scheme also has the problem that prime factorization is rather computationally challenging--it is after all the basis of the RSA cryptosystem.

Whereas Arithmetic encoding is actually practical, extensively used, and a direct analogue to the stick.

sdfsdfsfds|2 years ago

I'm aware of arithmetic encoding and it is definitely the most compelling example of encoding arbitrary data with a single number. On the other hand, there is a lot more to arithmetic coding than the ability to encode lists of numbers—all the considerations involving the context of each symbol, which are essential to the process of compression. I just felt that it might be helpful to give an example which didn't implicate all that complex compression apparatus.