Sophistication as Randomness Deciency
; Aaronson, Scott Aaronson
; Antunes, L.
Sophistication as Randomness Deciency, 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 deciency. 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.