Sophistication vs Logical Depth

• Tipo: Artigo em Revista Científica Internacional
• Data: 2017

Autores

antunes, l (Autor) FCUP; Bauwens, B (Autor) Outra; souto, a (Autor) Outra; teixeira, a (Autor) Outra

Revista

Título: Theory of Computing Systems

Vol. 60

Páginas: 280-298

ISSN: 1432-4350

Editora: Springer Nature

Indexação

ISI Web of Knowledge - 2 Citações

Scopus - 3 Citações

Outras Informações

ID Authenticus: P-00G-6EP

DOI: 10.1007/s00224-016-9672-6

Abstract (EN): Sophistication and logical depth are two measures that express how complicated the structure in a string is. Sophistication is defined as the minimal complexity of a computable function that defines a two-part description for the string that is shortest within some precision; the second can be defined as the minimal computation time of a program that is shortest within some precision. We show that the Busy Beaver function of the sophistication of a string exceeds its logical depth with logarithmically bigger precision, and that logical depth exceeds the Busy Beaver function of sophistication with logarithmically bigger precision. We also show that sophistication is unstable in its precision: constant variations can change its value by a linear term in the length of the string.

Idioma: Inglês

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

Nº de páginas: 19