2020/02/16 by Charles Alexandre Bédard, Bédard, Charles Alexandre
Computer Science · Mathematics · #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.2002.06709
44 pages, 5 figures
arxiv created 2020/02/16 · arxiv updated 2020/02/18
Logical depth and sophistication are two quantitative measures of the non-trivial organization of an object. Although apparently different, these measures have been proven equivalent, when the logical depth is renormalized by the busy beaver function. In this article, the measures are relativized to auxiliary information and re-compared to one another. The ability of auxiliary information to solve the halting problem introduces a distortion between the measures. Finally, similar to algorithmic complexity, sophistication and logical depth (renormalized) each offer a relation between their expression of (x, y), (x) and (y | x).