Creating and sharing knowledge for telecommunications

Sophistication as Randomness De ciency

Mota, F. ; Aaronson, Scott Aaronson ; Antunes, L. ; Souto, A.

Sophistication as Randomness De ciency, Proc Workshop on Descriptional Complexity of Formal Systems - DCFS, London, Canada, Vol. ., pp. . - ., July, 2013.

Digital Object Identifier: 0

Download Full text PDF ( 269 KBs)


The sophistication of a string measures how much structural information it contains. We introduce naive sophistication, a variant of sophistication based on randomness de ciency. Naive sophistication measures the minimum number of bits needed to specify a set in which the string is a typical element. Thanks to Vereshchagin and Vitanyi, we know that sophistication and naive sophistication are equivalent up to low order terms. We use this to relate sophistication to lossy compression, and to derive an alternative formulation for busy beaver computational depth.