Sophistication as randomness deficiency

• Tipo: Artigo em Livro de Atas de Conferência Internacional
• Data: 2013

Autores

Mota, F (Autor) Outra; Aaronson, S (Autor) Outra; antunes, l (Autor) FCUP; souto, a (Autor) Outra

Ata de Conferência Internacional

Título: Descriptional Complexity of Formal Systems

Páginas: 172-181

DCFS

Indexação

Scopus - 5 Citações

Outras Informações

ID Authenticus: 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica