×

Unified characterizations of lowness properties via Kolmogorov complexity. (English) Zbl 1338.03083

Summary: Consider a randomness notion \({\mathcal{C}}\). A uniform test in the sense of \({\mathcal{C}}\) is a total computable procedure that each oracle \(X\) produces a test relative to \(X\) in the sense of \({\mathcal{C}}\). We say that a binary sequence \(Y\) is \({\mathcal{C}}\)-random uniformly relative to \(X\) if \(Y\) passes all uniform \({\mathcal{C}}\) tests relative to \(X\). Suppose now we have a pair of randomness notions \({\mathcal{C}}\) and \({\mathcal{D}}\) where \({\mathcal{C} \subseteq \mathcal{D}}\), for instance Martin-Löf randomness and Schnorr randomness. Several authors have characterized classes of the form Low(\({\mathcal{C}, \mathcal{D}}\)) which consist of the oracles \(X\) that are so feeble that \({\mathcal{C} \subseteq \mathcal{D}^X}\). Our goal is to do the same when the randomness notion \({\mathcal{D}}\) is relativized uniformly: denote by \(\mathrm{Low}^\star(\mathcal{C},\mathcal{D})\) the class of oracles \(X\) such that every \({\mathcal{C}}\)-random is uniformly \({\mathcal{D}}\)-random relative to \(X\). (1) We show that \({X\in \mathrm{Low} ^\star}\) (MLR, SR) if and only if \(X\) is c.e. tt-traceable if and only if \(X\) is anticomplex if and only if \(X\) is Martin-Löf packing measure zero with respect to all computable dimension functions. (2) We also show that \({X\in \mathrm{Low}^\star}\) (SR, WR) if and only if \(X\) is computably i.o. tt-traceable if and only if \(X\) is not totally complex if and only if \(X\) is Schnorr Hausdorff measure zero with respect to all computable dimension functions.

MSC:

03D32 Algorithmic randomness and dimension
68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Barmpalias G., Downey R., Ng K.M.: Jump inversions inside effectively closed sets and applications to randomness. J. Symb. Logic 76(2), 491-518 (2011) · Zbl 1248.03065 · doi:10.2178/jsl/1305810761
[2] Bienvenu L., Miller J.S.: Randomness and lowness notions via open covers. Ann. Pure Appl. Logic 163, 506-518 (2012) · Zbl 1250.03067 · doi:10.1016/j.apal.2011.06.009
[3] Binns S.: Small \[{\Pi^0_1}\] Π10 classes. Arch. Math. Logic 45(4), 393-410 (2006) · Zbl 1147.03024 · doi:10.1007/s00153-005-0319-6
[4] Binns S.: Hyperimmunity in \[{{2}^{\mathbb{N}}}2N\]. Notre Dame J. Form. Log. 48(2), 293-316 (2007) · Zbl 1139.03029 · doi:10.1305/ndjfl/1179323269
[5] Binns \[S.: {\Pi^0_1}\] Π10 classes with complex elements. J. Symb. Logic 73(4), 1341-1353 (2008) · Zbl 1155.03032 · doi:10.2178/jsl/1230396923
[6] Binns S., Kjos-Hanssen B.: Finding paths through narrow and wide trees. J. Symb. Logic 74(1), 349-360 (2009) · Zbl 1161.03035 · doi:10.2178/jsl/1231082316
[7] Brattka, V.: Computability over topological structures. In: Cooper, S.B., Goncharov, S.S. (eds.) Computability and Models, pp. 93-136. Kluwer, New York (2003) · Zbl 1201.03039
[8] Brattka, V., Hertling, P., Weihrauch, K.: A tutorial on computable analysis. In: Cooper, S.B., Löwe, B., Sorbi, A. (eds.) New Computational Paradigms, pp. 425-491. Springer, Berlin (2008) · Zbl 1145.03037
[9] Calude, C.S., Coles, R.J.: Program-size complexity of initial segments and domination relation reducibility. In: Karhumäki, J., Hauer, H., Păun, G., Rozenberg, G. (eds.) Jewels and Forever, pp. 225-237. Springer, Berlin (1999) · Zbl 0945.68080
[10] Chaitin G.J.: Nonrecursive infinite strings with simple initial segments. IBM J. Res. Dev. 21, 350-359 (1977) · Zbl 0362.94035 · doi:10.1147/rd.214.0350
[11] Diamondstone, D., Kjos-Hanssen, B.: Members of random closed sets. In: Mathematical Theory and Computational Practice, pp. 144-153. Springer, Berlin (2009) · Zbl 1233.03049
[12] Downey R., Griffiths E., LaForte G.: On Schnorr and computable randomness, martingales, and machines. MLQ Math. Log. Q. 50(6), 613-627 (2004) · Zbl 1062.68064 · doi:10.1002/malq.200310121
[13] Downey R., Hirschfeldt D.R.: Algorithmic Randomness and Complexity. Springer, Berlin (2010) · Zbl 1221.68005
[14] Downey R., Nies A., Weber R., Yu L.: Lowness and \[{\Pi^0_2}\] Π20 nullsets. J. Symb. Logic 71(3), 1044-1052 (2006) · Zbl 1112.03040 · doi:10.2178/jsl/1154698590
[15] Downey R.G., Griffiths E.J.: Schnorr randomness. J. Symb. Logic 69(2), 533-554 (2004) · Zbl 1072.03025 · doi:10.2178/jsl/1082418542
[16] Downey, R.G., Hirschfeldt, D.R., Nies, A., Stephan, F.: Trivial reals. In: Downey, R.G., Ding, D., Tung, S.P., Qiu, Y.H., Yasugi, M. (eds.) Proceedings of the 7th and 8th Asian Logic Conferences, pp. 103-131. Singapore University Press and World Scientific, Singapore (2003) · Zbl 1044.03027
[17] Downey, R.G., Merkle, W., Reimann, J.: Schnorr dimension. In: Barry Cooper, S. et al. (ed.) New Computational Paradigms, First Conference on Computability in Europe, CiE 2005, Lecture Notes in Comput. Sci., vol. 3526, pp. 96-105. Springer, Berlin (2005) · Zbl 1113.03331
[18] Franklin J., Greenberg N., Stephan F., Wu G.: Anti-complex sets and reducibilities with tiny use. J. Symb. Logic 78(4), 1307-1327 (2013) · Zbl 1307.03025 · doi:10.2178/jsl.7804170
[19] Franklin J., Stephan F.: Van Lambalgen’s theorem and high degrees. Notre Dame J. Form. Log. 52(2), 173-185 (2011) · Zbl 1223.03024 · doi:10.1215/00294527-1306181
[20] Franklin J.N.Y.: Hyperimmune-free degrees and Schnorr triviality. J. Symb. Logic 73(3), 999-1008 (2008) · Zbl 1181.03045 · doi:10.2178/jsl/1230396761
[21] Franklin J.N.Y.: Schnorr trivial reals: a construction. Arch. Math. Log. 46(7-8), 665-678 (2008) · Zbl 1142.03020 · doi:10.1007/s00153-007-0061-3
[22] Franklin, J.N.Y.: Lowness and highness properties for randomness notions. In: Arai, T. et al. (ed.) Proceedings of the 10th Asian Logic Conference, pp. 124-151. World Scientific, Singapore (2010) · Zbl 1193.03072
[23] Franklin J.N.Y.: Schnorr triviality and genericity. J. Symb. Logic 75(1), 191-207 (2010) · Zbl 1184.03040 · doi:10.2178/jsl/1264433915
[24] Franklin J.N.Y., Stephan F.: Schnorr trivial sets and truth-table reducibility. J. Symb. Logic 75(2), 501-521 (2010) · Zbl 1193.03073 · doi:10.2178/jsl/1268917492
[25] Greenberg N., Miller J.S.: Lowness for Kurtz randomness. J. Symb. Logic 74, 665-678 (2009) · Zbl 1168.03033 · doi:10.2178/jsl/1243948333
[26] Higuchi K., Kihara T.: On effectively closed sets of effective strong measure zero. Ann. Pure Appl. Logic 165(9), 1445-1469 (2014) · Zbl 1351.03033 · doi:10.1016/j.apal.2014.04.013
[27] Hirschfeldt D., Nies A., Stephan F.: Using random sets as oracles. J. Lond. Math. Soc. 75, 610-622 (2007) · Zbl 1128.03036 · doi:10.1112/jlms/jdm041
[28] Hölzl, R., Merkle, W.: Traceable sets. Theoret. Comput. Sci. 323, 301-315 (2010) · Zbl 1198.68155
[29] Kanovich M.I.: On the complexity of enumeration and decision of predicates. Sov. Math. Dokl. 11, 17-20 (1970) · Zbl 0255.02049
[30] Kihara T., Miyabe K.: Uniform Kurtz randomness. J. Log. Comput. 24(4), 863-882 (2014) · Zbl 1338.03082 · doi:10.1093/logcom/ext054
[31] Kjos-Hanssen B., Merkle W., Stephan F.: Kolmogorov complexity and the recursion theorem Trans. Am. Math. Soc. 363(10), 5465-5480 (2011) · Zbl 1236.03032 · doi:10.1090/S0002-9947-2011-05306-7
[32] Kjos-Hanssen B., Miller J.S., Solomon D.R.: Lowness notions, measure, and domination. J. Lond. Math. Soc. 85(3), 869-888 (2012) · Zbl 1262.03068 · doi:10.1112/jlms/jdr072
[33] Kjos-Hanssen B., Nies A.: Superhighness. Notre Dame J. Form. Log. 50, 445-452 (2009) · Zbl 1204.03041 · doi:10.1215/00294527-2009-020
[34] Kjos-Hanssen B., Nies A., Stephan F.: Lowness for the class of Schnorr random reals. SIAM J. Comput. 35(3), 647-657 (2005) · Zbl 1095.68043 · doi:10.1137/S0097539704446323
[35] Kučera A.: On relative randomness. Ann. Pure Appl. Logic 63, 61-67 (1993) · Zbl 0788.68068 · doi:10.1016/0168-0072(93)90209-V
[36] Kučera A., Terwijn S.: Lowness for the class of random sets. J. Symb. Logic 64, 1396-1402 (1999) · Zbl 0954.68080 · doi:10.2307/2586785
[37] Merkle W., Miller J., Nies A., Reimann J., Stephan F.: Kolmogorov-Loveland randomness and stochasticity. Ann. Pure Appl. Logic 138(1-3), 183-210 (2006) · Zbl 1097.03041 · doi:10.1016/j.apal.2005.06.011
[38] Miyabe, K.: Schnorr triviality and its equivalent notions. Theory Comput. Syst. (to appear) · Zbl 1336.03048
[39] Miyabe K.: Truth-table Schnorr randomness and truth-table reducible randomness. MLQ Math. Log. Q. 57(3), 323-338 (2011) · Zbl 1220.03043 · doi:10.1002/malq.200910128
[40] Miyabe, K., Rute, J.: Van Lambalgen’s theorem for uniformly relative Schnorr and computable randomness. In: Proceedings of the Twelfth Asian Logic Conference, pp. 251-270 (2013) · Zbl 1364.03062
[41] Nies A.: Lowness properties and randomness. Adv. Math. 197, 274-305 (2005) · Zbl 1141.03017 · doi:10.1016/j.aim.2004.10.006
[42] Nies A.: Computability and Randomness. Oxford University Press, USA (2009) · Zbl 1169.03034 · doi:10.1093/acprof:oso/9780199230761.001.0001
[43] Nies A., Stephan F., Terwijn S.: Randomness, relativization and Turing degrees. J. Symb. Logic 70, 515-535 (2005) · Zbl 1090.03013 · doi:10.2178/jsl/1120224726
[44] Odifreddi, P.: Classical Recursion Theory, vol. 1. North-Holland, Amsterdam (1990) · Zbl 0931.03057
[45] Odifreddi, P.: Classical Recursion Theory, vol. 2. North-Holland, Amsterdam (1999) · Zbl 0931.03057
[46] Pawlikowski J.: A characterization of strong measure zero sets. Israel J. Math. 93(1), 171-183 (1996) · Zbl 0857.28001 · doi:10.1007/BF02761100
[47] Reimann, J.: Computability and Fractal Dimension. Ph.D. Thesis, Universität Heidelberg (2004) · Zbl 1080.03031
[48] Soare R.I.: Recursively Enumerable Sets and Degrees. Perspectives in Mathematical Logic. Springer, Berlin (1987)
[49] Solovay, R.: Draft of Paper (or Series of Papers) on Chaitin’s Work. Unpublished Notes (1975), p. 215 · Zbl 0990.03033
[50] Stephan F., Yu L.: Lowness for weakly 1-generic and Kurtz-random. Lect. Notes Comput. Sci. 3959, 756-764 (2006) · Zbl 1178.03052 · doi:10.1007/11750321_72
[51] Terwijn S.A., Zambella D.: Computational randomness and lowness. J. Symb. Logic 66(3), 1199-1205 (2001) · Zbl 0990.03033 · doi:10.2307/2695101
[52] van Lambalgen, M.: Random Sequences. Ph.D. Thesis, University of Amsterdam (1987) · Zbl 0628.60001
[53] Weihrauch K.: Computable Analysis: An Introduction. Springer, Berlin (2000) · Zbl 0956.68056
[54] Weihrauch K., Grubba T.: Elementary computable topology. J. UCS 15(6), 1381-1422 (2009) · Zbl 1201.03039
[55] Yu L.: When van Lambalgen’s theorem fails. Proc. Am. Math. Soc. 135(3), 861-864 (2007) · Zbl 1110.03027 · doi:10.1090/S0002-9939-06-08541-8
[56] Zambella, D.: On Sequences with Simple Initial Segments. Tech. rep., Univ. Amsterdam (1990). ILLC Technical Report ML 1990-05 · Zbl 1250.03067
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.