2013/01/18 by L. Antunes, Luís Antunes, A. Souto +9 · 1 citation
Computer Science · #Algorithms and Data Compression #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #cs.CC #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1301.4451
11 pages LaTeX; previous version was incorrect, this is a new version with almost the same results
openalex publication_date 2013/01/18 · arxiv created 2013/07/05 · arxiv updated 2013/07/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
For a finite binary string x its logical depth d for significance b is the shortest running time of a program for x of length K(x)+b. There is another definition of logical depth. We give a new proof that the two versions are close. There is an infinite sequence of strings of consecutive lengths such that for every string there is a b such that incrementing b by 1 makes the associated depths go from incomputable to computable. The maximal gap between depths resulting from incrementing appropriate b's by 1 is incomputable. The size of this gap is upper bounded by the Busy Beaver function. Both the upper and the lower bound hold for the depth with significance 0. As a consequence, the minimal computation time of the associated shortest programs rises faster than any computable function but not so fast as the Busy Beaver function.