Go to:
Logótipo
Você está em: Start > Publications > View > On the rate of decrease in logical depth
Map of Premises
Principal
Publication

On the rate of decrease in logical depth

Title
On the rate of decrease in logical depth
Type
Article in International Scientific Journal
Year
2017
Authors
Vitanyi, PMB
(Author)
Other
The person does not belong to the institution. The person does not belong to the institution. The person does not belong to the institution. Without AUTHENTICUS Without ORCID
Journal
Vol. 702
Pages: 60-64
ISSN: 0304-3975
Publisher: Elsevier
Other information
Authenticus ID: P-00N-84S
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.
Language: English
Type (Professor's evaluation): Scientific
No. of pages: 5
Documents
We could not find any documents associated to the publication.
Related Publications

Of the same journal

Weak linearization of the lambda calculus (2005)
Article in International Scientific Journal
Alves, S; Florido, M
Turing machines and bimachines (2008)
Article in International Scientific Journal
John Rhodes; Pedro V. Silva
Turing machines and bimachines (2008)
Article in International Scientific Journal
Rhodes, J; Pedro V. Silva
The k-word problem over DRH (2017)
Article in International Scientific Journal
Célia Borlido
The homomorphism problem for trace monoids (2003)
Article in International Scientific Journal
Pedro V. Silva

See all (37)

Recommend this page Top
Copyright 1996-2025 © Faculdade de Medicina Dentária da Universidade do Porto  I Terms and Conditions  I Acessibility  I Index A-Z  I Guest Book
Page created on: 2025-07-07 at 17:15:38 | Acceptable Use Policy | Data Protection Policy | Complaint Portal