@KripkePlatek It's simply an obvious way if you know prime factorization and want an infinite alphabet and don't know about computing.

If you know computing, you naturally think of how to get everything in a fixed alphabet, in fact binary, and so prime powers aren't natural anymore.

@JadeVanadium And that is one reason for not using that encoding, except for being able to say that each string has a unique code. In the end we still need Gödel's β-function... so we could have done that right from the beginning...

Having an intermediate representation that 'looks nice' does only that; looks nice.

@KripkePlatek Sure, and if you want an efficient encoding you could use 00 as separator, and have every symbol in the sequence represented by a string of digit pairs where each pair is 10 or 11. It is efficient in many useful ways, especially if you use TC: (1) you can search for a substring trivially; (2) its length is asymptotically optimal because it's O(log(c)) per symbol where c is the alphabet size; (3) it is binary;

(4) after applying Gödel's β to interpret TC in arithmetic, the resulting code can be described using O(1) times the original number of bits.

→ 15 messages moved to Basic Mathematics

→ 31 messages moved to Basic Mathematics