Are binary codings universal? (Q960456)

Summary: It is common sense to notice that one needs fewer digits to code numbers in ternary than in binary; new names are about \(\log _32\) times shorter. Is this trade-off a consequence of the special coding scheme? The answer is negative. More generally, we argue that the answer to the question, stated in the title and formulated to the first author by C. Rackhoff, is in fact negative. The conclusion will be achieved by studying the role of the size of the alphabet in constructing instantaneous codes for all natural numbers, and defining random strings and sequences. We show that there is no optimal instantaneous code for all positive integers, and the binary is the worst possible. Codes over a fixed alphabet can be indefinitely improved themselves, but only ``slightly''; in contrast, changing the size of the alphabet determines a significant, not linear, improvement. The key relation describing the above phenomenon can be expressed in terms of Chaitin complexity: changing the size of the coding alphabet from \(q\) to \(Q\), \(2 \le q<Q\), results in an improvement of the complexity by a factor of \(\log _Qq\). As a consequence, a string avoiding consistently a fixed letter is not random. In binary, this corresponds to a trivial situation. In the nonbinary case the distinction is relevant: more than \(3.2^n\) ternary strings of length \(n\) are not random (many of these strings are binary random). This phenomenon is even sharper for infinite sequences.