On the rate of decrease in logical depth

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

Autores

antunes, l (Autor) FCUP; souto, a (Autor) Outra; Vitanyi, PMB (Autor) Outra

Revista

Título: Theoretical Computer Science

Vol. 702

Páginas: 60-64

ISSN: 0304-3975

Editora: Elsevier

Indexação

ISI Web of Knowledge - 2 Citações

Scopus - 1 Citação

Outras Informações

ID Authenticus: P-00N-84S

DOI: 10.1016/j.tcs.2017.08.012

Abstract (EN): The logical depth with significance b of a string x is the shortest running time of a program for x that can be compressed by at most b bits. Another definition is based on algorithmic probability. We give a simple new proof for the known relation between the two definitions. We also prove the following: Given a string we can consider the maximal decrease in logical depth when the significance parameter increases by 1. There exists a sequence of strings of lengths n = 1,2,..., such that this maximal decrease as a function of n rises faster than any computable function but not as fast as the Busy Beaver function. This holds also for the computation times of the shortest programs of these strings.

Idioma: Inglês

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

Nº de páginas: 5