On the number of infinite sequences with trivial initial segment complexity. (English) Zbl 1235.68086
Summary: The sequences which have trivial prefix-free initial segment complexity are known as \(K\)-trivial sets, and form a cumulative hierarchy of length \(\omega \). We show that the problem of finding the number of \(K\)-trivial sets in the various levels of the hierarchy is \(\varDelta^0_3\). This answers a question of Downey, Miller and Yu [R. G. Downey and D. R. Hirschfeldt, Algorithmic randomness and complexity. Theory and Applications of Computability. New York, NY: Springer (2010; Zbl 1221.68005), Section 10.1.4; A. Nies, Computability and randomness. Oxford Logic Guides 51. Oxford: Oxford University Press (2009; Zbl 1169.03034), Problem 5.2.16].
We also show the same for the hierarchy of the low for \(K\) sequences, which are the ones that (when used as oracles) do not give a shorter initial segment complexity compared to the computable oracles. In both cases the classification \(\varDelta^0_3\) is sharp.
We also show the same for the hierarchy of the low for \(K\) sequences, which are the ones that (when used as oracles) do not give a shorter initial segment complexity compared to the computable oracles. In both cases the classification \(\varDelta^0_3\) is sharp.
MSC:
| 68Q30 | Algorithmic information theory (Kolmogorov complexity, etc.) |
| 68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |
References:
| [1] | Arslanov, Marat M., On some generalizations of the fixed-point theorem, Soviet Mathematics, 25, 1-10 (1981) · Zbl 0523.03029 |
| [2] | Martijn Baartse, George Barmpalias, On the gap between trivial and nontrivial initial segment prefix-free complexity. Submitted, 2010.; Martijn Baartse, George Barmpalias, On the gap between trivial and nontrivial initial segment prefix-free complexity. Submitted, 2010. · Zbl 1261.68075 |
| [3] | Barmpalias, George; Vlek, C. S., Kolmogorov complexity of initial segments of sequences and arithmetical definability, Theoretical Computer Science, 412, 41, :5656-5667 (2011) · Zbl 1235.68087 |
| [4] | Chaitin, Gregory J., A theory of program size formally identical to information theory, Journal of the Association for Computing Machinery, 22, 329-340 (1975) · Zbl 0309.68045 |
| [5] | Chaitin, G., Information-theoretical characterizations of recursive infinite strings, Theoretical Computer Science, 2, 45-48 (1976) · Zbl 0328.02029 |
| [6] | Csima, Barbara F.; Montalbán, Antonio, A minimal pair of \(K\)-degrees, Proceedings of the American Mathematical Society, 134, 5, 1499-1502 (2006), electronic · Zbl 1147.03025 |
| [7] | Downey, Rod; Hirshfeldt, Denis, Algorithmic Randomness and Complexity (2010), Springer · Zbl 1221.68005 |
| [8] | Downey, Rod G.; Hirschfeldt, Denis R.; Nies, André; Stephan, Frank, Trivial reals, (Proceedings of the 7th and 8th Asian Logic Conferences (2003), Singapore Univ. Press), 103-131 · Zbl 1044.03027 |
| [9] | Ershov, Yuri L., A certain hierarchy of sets, Algebra i Logika, 7, 1, 47-74 (1968) · Zbl 0216.00901 |
| [10] | Jockusch, Carl G.; Soare, Robert I., \( \Pi_1^0\) classes and degrees of theories, Transactions of the American Mathematical Society, 173, 33-56 (1972) · Zbl 0262.02041 |
| [11] | Bjørn Kjos-Hanssen, Wolfgang Merkle, Frank Stephan, Kolmogorov complexity and the recursion theorem, in: STACS, 2006, pp. 149-161.; Bjørn Kjos-Hanssen, Wolfgang Merkle, Frank Stephan, Kolmogorov complexity and the recursion theorem, in: STACS, 2006, pp. 149-161. · Zbl 1137.03026 |
| [12] | Kjos-Hanssen, Bjørn; Merkle, Wolfgang; Stephan, Frank, Kolmogorov complexity and the recursion theorem, Transactions of the American Mathematical Society, 363 (2011) · Zbl 1236.03032 |
| [13] | Kučera, Antonín; Terwijn, Sebastiaan A., Lowness for the class of random sets, Journal of Symbolic Logic, 64, 4, 1396-1402 (1999) · Zbl 0954.68080 |
| [14] | Levin, L. A., Laws of information conservation (nongrowth) and aspects of the foundation of probability theory, Problems of Information Transmission, 10, 206-210 (1974) |
| [15] | Li, M.; Vitányi, P., (An Introduction to Kolmogorov Complexity and its Applications. An Introduction to Kolmogorov Complexity and its Applications, Graduate Texts in Computer Science (1997), Springer-Verlag: Springer-Verlag New York) · Zbl 0866.68051 |
| [16] | Nies, André, Lowness properties and randomness, Advances in Mathematics, 197, 1, 274-305 (2005) · Zbl 1141.03017 |
| [17] | Nies, André, Computability and Randomness (2009), Oxford University Press · Zbl 1169.03034 |
| [18] | Solomonoff, R. J., A formal theory of inductive inference. I, Information and Control, 7, 1-22 (1964) · Zbl 0258.68045 |
| [19] | R. Solovay, Handwritten manuscript related to Chaitin’s work. IBM Thomas J. Watson Research Center, Yorktown Heights, NY, 215 p., 1975.; R. Solovay, Handwritten manuscript related to Chaitin’s work. IBM Thomas J. Watson Research Center, Yorktown Heights, NY, 215 p., 1975. |
| [20] | Shore, Richard; Slaman, Theodore, Working below a low \({}_2\) recursively enumerable degree, Archive for Mathematical Logic, 29, 201-211 (1990) · Zbl 0693.03027 |
| [21] | D. Zambella, On sequences with simple initial segments. ILLC technical report ML 1990-05, Univ. Amsterdam, 1990.; D. Zambella, On sequences with simple initial segments. ILLC technical report ML 1990-05, Univ. Amsterdam, 1990. |
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.
