Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-18T05:30:38.107Z Has data issue: false hasContentIssue false
  • English
  • Français

BEING LOW ALONG A SEQUENCE AND ELSEWHERE

Published online by Cambridge University Press:  25 January 2019

WOLFGANG MERKLE  and
LIANG YU
WOLFGANG MERKLE
Affiliation:
INSTITUTE OF COMPUTER SCIENCE HEIDELBERG UNIVERSITY IM NEUENHEIMER FELD 205, 69120 HEIDELBERG GERMANYE-mail: [email protected]
LIANG YU
Affiliation:
DEPARTMENT OF MATHEMATICS NANJING UNIVERSITY JIANGSU PROVINCE 210093 P. R. OF CHINAE-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Let an oracle be called low for prefix-free complexity on a set in case access to the oracle improves the prefix-free complexities of the members of the set at most by an additive constant. Let an oracle be called weakly low for prefix-free complexity on a set in case the oracle is low for prefix-free complexity on an infinite subset of the given set. Furthermore, let an oracle be called low and weakly for prefix-free complexity along a sequence in case the oracle is low and weakly low, respectively, for prefix-free complexity on the set of initial segments of the sequence. Our two main results are the following characterizations. An oracle is low for prefix-free complexity if and only if it is low for prefix-free complexity along some sequences if and only if it is low for prefix-free complexity along all sequences. An oracle is weakly low for prefix-free complexity if and only if it is weakly low for prefix-free complexity along some sequence if and only if it is weakly low for prefix-free complexity along almost all sequences. As a tool for proving these results, we show that prefix-free complexity differs from its expected value with respect to an oracle chosen uniformly at random at most by an additive constant, and that similar results hold for related notions such as a priori probability. Furthermore, we demonstrate that on every infinite set almost all oracles are weakly low but are not low for prefix-free complexity, while by Shoenfield absoluteness there is an infinite set on which uncountably many oracles are low for prefix-free complexity. Finally, we obtain no-gap results, introduce weakly low reducibility, or WLK-reducibility for short, and show that all its degrees except the greatest one are countable.

Keywords

03D2803D3003D3268Q30Kolmogorov complexityrandomnesslowness
Type
Articles
Information
The Journal of Symbolic Logic , Volume 84 , Issue 2 , June 2019 , pp. 497 - 516
Copyright
Copyright © The Association for Symbolic Logic 2019 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Barmpalias, G., Private communication, June 2015.Google Scholar
Bartoszynski, T. and Judah, H., Set Theory: On the Structure of the Real Line, A K Peters/CRC Press, Wellesley, MA, 1995.10.1201/9781439863466CrossRefGoogle Scholar
Bienvenu, L. and Downey, R.. Kolmogorov complexity and Solovay functions. In STACS 2009, LIPIcs. Leibniz International Proceedings in Informatics, vol. 3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Wadern, 2009, pp. 147–158.Google Scholar
Bienvenu, L., Downey, R., Nies, A., and Merkle, W., Solovay functions and their applications in algorithmic randomness. Journal of Computer and System Sciences, vol. 81 (2015), pp. 1575–1591.10.1016/j.jcss.2015.04.004CrossRefGoogle Scholar
Downey, R. G. and Hirschfeldt, D. R.. Algorithmic Randomness and Complexity. Theory and Applications of Computability. Springer, New York, 2010.10.1007/978-0-387-68441-3CrossRefGoogle Scholar
Gács, P., Every sequence is reducible to a random one. Information and Control, vol. 70 (1986), no. 2–3, pp. 186–192.10.1016/S0019-9958(86)80004-3CrossRefGoogle Scholar
Harrington, L., Marker, D., and Shelah, S., Borel orderings. Transactions of the American Mathematical Society, vol. 310 (1988), no. 1, pp. 293–302.10.1090/S0002-9947-1988-0965754-3CrossRefGoogle Scholar
Jech, T., Set Theory, Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2003.Google Scholar
Kjos-Hanssen, B., Miller, J. S., and Solomon, R., Lowness notions, measure and domination. Journal of the London Mathematical Society, Second Series, vol. 85 (2012), no. 3, pp. 869–888.10.1112/jlms/jdr072CrossRefGoogle Scholar
Kučera, A., Measure, ${\rm{\Pi }}_1^0$-classes and complete extensions of PA, Recursion Theory Week (Oberwolfach, 1984), Lecture Notes in Mathematics, vol. 1141, Springer, Berlin, 1985, pp. 245–259.10.1007/BFb0076224CrossRefGoogle Scholar
Kunen, K., Set Theory, North Holland, Amsterdam, 1992.Google Scholar
Li, M. and Vitányi, P., An Introduction to Kolmogorov Complexity and Its Applications, third ed., Springer, New York, 2008.10.1007/978-0-387-49820-1CrossRefGoogle Scholar
Miller, J. S., Every 2-random real is Kolmogorov random, this Journal, vol. 69 (2004), no. 3, pp. 907–913.Google Scholar
Miller, J. S., The K-degrees, low for K-degrees and weakly low for K-sets. Notre Dame Journal of Formal Logic , vol. 50 (2010), no. 4, pp. 381–391.10.1215/00294527-2009-017CrossRefGoogle Scholar
Miller, J. S. and Yu, L., On initial segment complexity and degrees of randomness. Transactions of the American Mathematical Society, vol. 360 (2008), no. 6, pp. 3193–3210.10.1090/S0002-9947-08-04395-XCrossRefGoogle Scholar
Nies, A., Lowness properties and randomness. Advances of Mathematics, vol. 197 (2005), pp. 274–305.10.1016/j.aim.2004.10.006CrossRefGoogle Scholar
Nies, A., Computability and Randomness, Oxford University Press, Oxford, 2009.10.1093/acprof:oso/9780199230761.001.0001CrossRefGoogle Scholar
Nies, A., Stephan, F., and Terwijn, S. A., Randomness, relativization and Turing degrees, this Journal, vol. 70 (2005), pp. 515–535.Google Scholar
Rudin, W., Real and Complex Analysis, McGraw-Hill, New York, 1987.Google Scholar