Are binary codings universal?
type: Item
instance of: scholarly article
title: Are binary codings universal?
zbMATH Open document ID: 1455.68073
author: Cristian Calcude
author: C. Câmpeanu
published in: Complexity
publication date: 2008-12-21T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q30
zbMATH DE Number: 5475571
zbMATH Keywords: instantaneous codes
zbMATH Keywords: Chaitin complexity
zbMATH Keywords: random strings
zbMATH Keywords: random sequences
MaRDI profile type: Publication
full work available at URL: cplx.6130010512
OpenAlex ID: W2082730258
DOI: 10.1002/CPLX.6130010512
description: scientific article; zbMATH DE number 5475571