×

Descriptive complexity of computable sequences revisited. (English) Zbl 1443.68075

Consider the following two complexities of an infinite computable binary sequence \(\alpha\): \(C^{0'}(\alpha)\) is the minimal length of a program with oracle \(0'\) that prints \(\alpha\), and \(M_{\infty}(\alpha)\) is \(\limsup C(\alpha 1:n|n)\), where \(\alpha 1:n\) denotes the length-\(n\) prefix of \(\alpha\) and C\((x|y)\) stands for conditional Kolmogorov complexity. The paper proves the following two results: \(C^{0'}(\alpha)\le M_{\infty}(\alpha)+O(1)\) and \(M_{\infty}(\alpha)\) is not bounded by any computable function of \(C^{0'}(\alpha)\), even on the domain of computable sequences. They answer two questions left open in [B. Durand et al., Theor. Comput. Sci. 271, No. 1–2, 47–58 (2002; Zbl 0982.68074)].

MSC:

68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
68Q19 Descriptive complexity and finite models

Citations:

Zbl 0982.68074
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Chaitin, G. J., On the length of programs for computing finite binary sequences: statistical considerations, J. ACM, 16, 145-159 (1969) · Zbl 0187.28303
[2] Durand, B.; Shen, A.; Vereshchagin, N., Descriptive complexity of computable sequences, Theor. Comput. Sci., 171, 47-58 (2001) · Zbl 0982.68074
[3] Kolmogorov, A. N., Three approaches to the quantitative definition of information, Probl. Inf. Transm., 1, 1, 1-7 (1965)
[4] Li, M.; Vitányi, P., An Introduction to Kolmogorov Complexity and Its Applications (1997), Springer Verlag · Zbl 0866.68051
[5] Loveland, D. W., A variant of Kolmogorov concept of complexity, Inf. Control, 15, 510-526 (1969) · Zbl 0188.52101
[6] Odifreddi, P., Classical Recursion Theory (1989), North-Holland · Zbl 0931.03057
[7] Shen, A.; Uspensky, V. A.; Vereshchagin, N., Kolmogorov Complexity and Algorithmic Randomness (2017), American Mathematical Society · Zbl 1435.68015
[8] Solomonoff, R. J., A formal theory of inductive inference, Inf. Control, 7, 1-22, 224-254 (1964), part 1 and part 2 · Zbl 0259.68038
[9] Uspensky, V. A.; Shen, A. Kh., Relations between varieties of Kolmogorov complexities, Math. Syst. Theory, 29, 271-292 (1996) · Zbl 0849.68059
[10] Vereshchagin, N., Kolmogorov complexity conditional to large integers, Theor. Comput. Sci., 271, 59-67 (2002) · Zbl 0982.68077
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.