Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-13T11:01:13.734Z 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: merkle@math.uni-heidelberg.de
LIANG YU
Affiliation:
DEPARTMENT OF MATHEMATICS NANJING UNIVERSITY JIANGSU PROVINCE 210093 P. R. OF CHINAE-mail: yuliang.nju@gmail.com
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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

Information

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 

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.CrossRefGoogle 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.CrossRefGoogle Scholar
Downey, R. G. and Hirschfeldt, D. R.. Algorithmic Randomness and Complexity. Theory and Applications of Computability. Springer, New York, 2010.CrossRefGoogle Scholar
Gács, P., Every sequence is reducible to a random one. Information and Control, vol. 70 (1986), no. 2–3, pp. 186–192.CrossRefGoogle Scholar
Harrington, L., Marker, D., and Shelah, S., Borel orderings. Transactions of the American Mathematical Society, vol. 310 (1988), no. 1, pp. 293–302.CrossRefGoogle 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.CrossRefGoogle 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.CrossRefGoogle 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.CrossRefGoogle 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.Google 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.CrossRefGoogle Scholar
Nies, A., Lowness properties and randomness. Advances of Mathematics, vol. 197 (2005), pp. 274–305.CrossRefGoogle Scholar
Nies, A., Computability and Randomness, Oxford University Press, Oxford, 2009.CrossRefGoogle 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