Sophistication and logical depth revisited
Fouad B. Chedid · 2010
This paper revisits the notion of the sophistication of a string as adapted for finite strings based on prefix Kolmogorov complexity by Antunes and Fortnow. We propose a variant of sophistication that depends on the coarse graining (level of detail) at which the string is described. Then, we use the idea behind the self-dissimilarity complexity measure of Wolpert and Macready to propose new ways for computing the maximal sophistication of a string and identifying absolutely nonstochastic strings. Also, we propose new measures for approximating the maximal sophistication of a finite string and the smallest amount of time required by a program to uncover all regularities in a string.