×

zbMATH — the first resource for mathematics

Lowness for Demuth randomness. (English) Zbl 1268.03053
Ambos-Spies, Klaus (ed.) et al., Mathematical theory and computational practice. 5th conference on computability in Europe, CiE 2009, Heidelberg, Germany, July 19–24, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-03072-7/pbk). Lecture Notes in Computer Science 5635, 154-166 (2009).
Summary: We show that every real low for Demuth randomness is of hyperimmune-free degree.
For the entire collection see [Zbl 1192.68004].

MSC:
03D32 Algorithmic randomness and dimension
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Barmpalias, G., Downey, R., Greenberg, N.: K-trivial degrees and the jump-traceability hierarchy. Proceedings of the American Mathematical Society (to appear) · Zbl 1165.03024 · doi:10.1090/S0002-9939-09-09761-5
[2] Barmpalias, G., Lewis, A., Ng, K.M.: The importance of \(\Pi^0_1\) -classes in effective randomness (submitted) · Zbl 1184.03039
[3] Barmpalias, G., Lewis, A., Stephan, F.: \(\Pi^0_1\) classes, LR degrees and Turing degrees. Annals of Pure and Applied Logic
[4] Bedregal, B., Nies, A.: Lowness properties of reals and hyper-immunity. In: WoLLIC 2003. Electronic Lecture Notes in Theoretical Computer Science, vol. 84 (2003) · Zbl 1264.03093
[5] Bickford, M., Mills, C.: Lowness properties of r.e. sets. Theoretical Computer Science (typewritten unpublished manuscript)
[6] Cholak, P., Downey, R., Greenberg, N.: Strong jump-traceability I: The computably enumerable case. Advances in Mathematics 217, 2045–2074 (2008) · Zbl 1134.03026 · doi:10.1016/j.aim.2007.09.008
[7] Demuth, O.: Remarks on the structure of tt-degrees based on constructive measure theory. Commentationes Mathematicae Universitatis Carolinae 29(2), 233–247 (1988) · Zbl 0646.03039
[8] Downey, R., Greenberg, N.: Strong jump-traceability II: The general case (in preparation) · Zbl 1273.03141
[9] Downey, R., Greenberg, N., Mihailović, N., Nies, A.: Lowness for computable machines. In: Computational Prospects of Infinity. Lecture Notes Series of the Institute for Mathematical Sciences, NUS, vol. 15, pp. 79–86 (2008) · Zbl 1175.03025 · doi:10.1142/9789812796554_0005
[10] Downey, R., Hirschfeldt, D., Nies, A., Stephan, F.: Trivial reals. In: Proceedings of the 7th and 8th Asian Logic Conferences, pp. 103–131. World Scientific, Singapore (2003) · Zbl 1044.03027 · doi:10.1142/9789812705815_0005
[11] Downey, R., Jockusch, C., Stob, M.: Array nonrecursive sets and multiple permitting arguments. Recursion Theory Week 1432, 141–174 (1990) · Zbl 0713.03020 · doi:10.1007/BFb0086116
[12] Downey, R., Ng, K.M.: Splitting into degrees with low computational strength (in preparation) · Zbl 06880852
[13] Figueira, S., Nies, A., Stephan, F.: Lowness properties and approximations of the jump. In: Proceedings of the Twelfth Workshop of Logic, Language, Information and Computation (WoLLIC 2005). Electronic Lecture Notes in Theoretical Computer Science, vol. 143, pp. 45–57 (2006) · Zbl 1137.03025 · doi:10.1016/j.entcs.2005.05.025
[14] Franklin, J., Stephan, F.: Schnorr trivial sets and truth-table reducibility. Technical Report TRA3/08, School of Computing, National University of Singapore (2008) · Zbl 1193.03073
[15] Greenberg, N., Miller, J.: Lowness for Kurtz randomness. Journal of Symbolic Logic (to appear) · Zbl 1168.03033 · doi:10.2178/jsl/1243948333
[16] Hirschfeldt, D., Nies, A., Stephan, F.: Using random sets as oracles (to appear) · Zbl 1128.03036
[17] Kjos-Hanssen, B., Nies, A.: Superhighness (to appear)
[18] Kjos-Hanssen, B., Nies, A., Stephan, F.: Lowness for the class of Schnorr random sets. Notre Dame Journal of Formal Logic 35(3), 647–657 (2005) · Zbl 1095.68043
[19] Ng, K.M.: Ph.D Thesis (in preparation)
[20] Ng, K.M.: Strong jump traceability and beyond (submitted) · Zbl 1220.03044
[21] Ng, K.M.: On strongly jump traceable reals. Annals of Pure and Applied Logic 154, 51–69 (2008) · Zbl 1140.03017 · doi:10.1016/j.apal.2007.11.014
[22] Nies, A.: On a uniformity in degree structures. In: Complexity, Logic and Recursion Theory. Lecture Notes in Pure and Applied Mathematics, February 1997, pp. 261–276 (1997) · Zbl 0883.03027
[23] Nies, A.: Reals which compute little. CDMTCS Research Report 202, The University of Auckland (2002) · Zbl 1107.03047
[24] Nies, A.: Lowness properties and randomness. Advances in Mathematics 197, 274–305 (2005) · Zbl 1141.03017 · doi:10.1016/j.aim.2004.10.006
[25] Nies, A.: Computability And Randomness. Oxford University Press, Oxford (2006) (to appear) · Zbl 1169.03033
[26] Slaman, T., Solovay, R.: When oracles do not help. In: Fourth Annual Conference on Computational Learning Theory, pp. 379–383 (1971)
[27] Stephan, F., Liang, Y.: Lowness for weakly 1-generic and Kurtz-random. In: Cai, J.-Y., Cooper, S.B., Li, A. (eds.) TAMC 2006. LNCS, vol. 3959, pp. 756–764. Springer, Heidelberg (2006) · Zbl 1178.03052 · doi:10.1007/11750321_72
[28] Terwijn, S., Zambella, D.: Algorithmic randomness and lowness. Journal of Symbolic Logic 66, 1199–1205 (2001) · Zbl 0990.03033 · doi:10.2307/2695101
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.