Hostname: page-component-cd9895bd7-jkksz Total loading time: 0 Render date: 2024-12-22T15:03:31.788Z Has data issue: false hasContentIssue false
  • English
  • Français

Shift-complex sequences

Published online by Cambridge University Press:  05 September 2014

Mushfeq Khan
Mushfeq Khan*
Affiliation:
Department of Mathematics, University of Wisconsin, Madison, WI 53706-1388, USA E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

A Martin-Löf random sequence is an infinite binary sequence with the property that every initial segment σ has prefix-free Kolmogorov complexity K(σ) at least ∣σ∣ − c, for some constant c ϵ ω. Informally, initial segments of Martin-Löf randoms are highly complex in the sense that they are not compressible by more than a constant number of bits. However, all Martin-Löf randoms necessarily have contiguous substrings of arbitrarily low complexity. If we demand that all substrings of a sequence be uniformly complex, then we arrive at the notion of shift-complex sequences. In this paper, we collect some of the existing results on these sequences and contribute two new ones. Rumyantsev showed that the measure of oracles that compute shift-complex sequences is zero. We strengthen this result by proving that the Martin-Löf random sequences that do not compute shift-complex sequences are exactly the incomplete ones, in other words, the ones that do not compute the halting problem. In order to do so, we make use of the characterization by Franklin and Ng of the class of incomplete Martin-Löf randoms via a notion of randomness called difference randomness. Turning to the power of shift-complex sequences as oracles, we show that there are shift-complex sequences that do not compute Martin-Löf random (or even Kurtz random) sequences.

Keywords

68Q3003D3203D28Kolmogorov complexitysubshiftsMartin-Löf randomness
Type
Articles
Information
Bulletin of Symbolic Logic , Volume 19 , Issue 2 , June 2013 , pp. 199 - 215
Copyright
Copyright © Association for Symbolic Logic 2013

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

[1] Cenzer, Douglas and Hinman, Peter G., Degrees of difficulty of generalized r.e. separating classes, Archive for Mathematical Logic, vol. 46 (2008), no. 7-8, pp. 629–647.Google Scholar
[2] Conidis, Chris, A real of strictly positive effective packing dimension that does not compute a real of effective packing dimension one, The Journal of Symbolic Logic, vol. 77 (2012), no. 2, pp. 447–474.CrossRefGoogle Scholar
[3] Downey, Rodney G. and Hirschfeldt, Denis R., Algorithmic randomness and complexity, Theory and Applications of Computability, Springer, 2010.CrossRefGoogle Scholar
[4] Durand, Bruno, Levin, Leonid A., and Shen, Alexander, Complex tilings, The Journal of Symbolic Logic, vol. 73 (2008), no. 2, pp. 593–613.CrossRefGoogle Scholar
[5] Fortnow, Lance, Hitchcock, John M., Pavan, A., Vinodchandran, N. V., and Wang, Feng-Ming, Extracting Kolmogorov complexity with applications to dimension zero-one laws. Information and Computation, vol. 209 (2011), no. 4, pp. 627–636.CrossRefGoogle Scholar
[6] Franklin, Johanna N. Y. and Ng, Keng Meng, Difference randomness, Proceedings of the American Mathematical Society, vol. 139 (2011), no. 1, pp. 345–360.CrossRefGoogle Scholar
[7] Greenberg, Noam and Miller, Joseph S., Diagonally non-recursive functions and effective Hausdorff dimension, The Bulletin of the London Mathematical Society, vol. 43 (2011), no. 4, pp. 636–654.CrossRefGoogle Scholar
[8] Hirschfeldt, Denis and Kach, Asher, Shift complex sequences, Talk presented at the AMS Eastern Sectional Meeting, 2012.Google Scholar
[9] Khan, Mushfeq and Miller, Joseph S., Bushy tree forcing, in preparation.Google Scholar
[10] Miller, Joseph S., Two notes on subshifts, Proceedings of the American Mathematical Society, vol. 140 (2012), no. 5, pp. 1617–1622.CrossRefGoogle Scholar
[11] Nies, André, Computability and randomness, Oxford Logic Guides, vol. 51, Oxford University Press, Oxford, 2009.CrossRefGoogle Scholar
[12] Rumyantsev, A. Yu. and Ushakov, M. A., Forbidden substrings, Kolmogorov complexity and almost periodic sequences, STACS 2006 (Durand, Bruno and Thomas, Wolfgang, editors), Lecture Notes in Computer Science, vol. 3884, Springer, 2006, pp. 396–407.CrossRefGoogle Scholar
[13] Rumyantsev, Andrey Yu., Everywhere complex sequences and the probabilistic method, STACS 2011 (Schwentick, Thomas and Dürr, Christoph, editors), Leibniz International Proceedings in Informatics (LIPIcs), vol. 9, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2011, pp. 464–471.Google Scholar
[14] Stephan, Frank, Martin-Löf random and PA-complete sets, Logic Colloquium '02 (Chatzidakis, Zoé Maria, Koepke, Peter, and Pohlers, Wolfram, editors), Lecture Notes in Logic, vol 27, Association for Symbolic Logic, La Jolla, CA, 2006, pp. 342–348.Google Scholar