Sophistication as randomness deficiency

• Type: Article in International Conference Proceedings Book
• Date: 2013

Authors

Mota, F (Author) Other; Aaronson, S (Author) Other; antunes, l (Author) FCUP; souto, a (Author) Other

Conference proceedings International

Title: Descriptional Complexity of Formal Systems

Pages: 172-181

DCFS

Indexing

Scopus - 5 Citations

Other information

Authenticus ID: P-008-E9G

DOI: 10.1007/978-3-642-39310-5_17

Abstract (EN): The sophistication of a string measures how much structural information it contains. We introduce naive sophistication, a variant of sophistication based on randomness deficiency. 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 Vitányi, 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. © 2013 Springer-Verlag.

Language: English

Type (Professor's evaluation): Scientific