Sophistication vs Logical Depth
Antunes, L.
; Bauwens, B.
;
Souto, A.
; Teixeira, A.T.
Theory of Computing Systems Vol. 1, Nº 1, pp. 1 - 1, March, 2016.
ISSN (print): 1433-0490
ISSN (online): 1432-4350
Scimago Journal Ranking: 0,51 (in 2016)
Digital Object Identifier: 10.1007/s00224-016-9672-6
Download Full text PDF ( 365 KBs)
Downloaded 1 time
Abstract
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
