Prefix and plain Kolmogorov complexity characterizations of 2-randomness: simple proofs

Duration: 33 mins 24 secs

Share this media item:

Embed this media item:

<iframe width="_width_" height="_height_" src="https://sms.cam.ac.uk/media/1273691/embed" frameborder="0" scrolling="no" allowfullscreen></iframe>

Choose size:

About this item

Available Formats

About this item

Description:	Bauwens, B (Universidade do Porto) Tuesday 03 July 2012, 17:00-17:30


Created:	2012-07-10 17:12
Collection:	Semantics and Syntax: A Legacy of Alan Turing
Publisher:	Isaac Newton Institute
Copyright:	Bauwens, B
Language:	eng (English)


Abstract:	Joseph Miller[1] and independently Andre Nies, Frank Stephan and Sebastian Terwijn[2] gave a complexity characterization of 2-random sequences in terms of plain Kolmogorov complexity C(⋅): they are sequences that have infinitely many initial segments with O(1)-maximal plain complexity (among the strings of the same length). Later Miller[3] (see also [4]) showed that prefix complexity K(⋅) can be also used in a similar way: a sequence is 2-random if and only if it has infinitely many initial segments with O(1)-maximal prefix complexity (which is n+K(n) for strings of length~n). The known proofs of these results are quite involved; we provide simple direct proofs for both of them. In [1] Miller also gave a quantitative version of the first result: the 0′-randomness deficiency of a sequence ω equals lim infn[n−C(ω1…ωn)]+O(1). (Our simplified proof also can be used to prove this quantitative version.) We show (and this seems to be a new result) that a similar quantitative result is true also for prefix complexity: 0′-randomness deficiency d0′(ω) equals also lim infn[n+K(n)−K(ω1…ωn)]+O(1). This completes the picture: d0′(ω)===supn[n−K0′(ω1…ωn)]+O(1)lim infn[n−C(ω1…ωn)]+O(1)lim infn[n+K(n)−K(ω1…ωn)]+O(1). [1] J.S. Miller. "Every 2-random real is Kolmogorov random." Journal of Symbolic Logic, 69(3):907–913, 2004. [2] A. Nies, F. Stephan, and S.A. Terwijn. "Randomness, relativization and turing degrees." The Journal of Symbolic Logic, 70(2), 2005. [3] J.S. Miller. "The K-degrees, low for K-degrees, and weakly low for K sets." Notre Dame Journal of Formal Logic, 50(4):381–391, 2009. [4] R.G. Downey and D.R. Hirschfeldt. "Algorithmic Randomness and Complexity." Theory and Applications of Computability. Springer, 2010.

Abstract:

Joseph Miller[1] and independently Andre Nies, Frank Stephan and Sebastian Terwijn[2] gave a complexity characterization of 2-random sequences in terms of plain Kolmogorov complexity C(⋅): they are sequences that have infinitely many initial segments with O(1)-maximal plain complexity (among the strings of the same length).
Later Miller[3] (see also [4]) showed that prefix complexity K(⋅) can be also used in a similar way: a sequence is 2-random if and only if it has infinitely many initial segments with O(1)-maximal prefix complexity (which is n+K(n) for strings of length~n).

The known proofs of these results are quite involved; we provide simple direct proofs for both of them.

In [1] Miller also gave a quantitative version of the first result: the 0′-randomness deficiency of a sequence ω equals lim infn[n−C(ω1…ωn)]+O(1). (Our simplified proof also can be used to prove this quantitative version.) We show (and this seems to be a new result) that a similar quantitative result is true also for prefix complexity: 0′-randomness deficiency d0′(ω) equals also lim infn[n+K(n)−K(ω1…ωn)]+O(1). This completes the picture:
d0′(ω)===supn[n−K0′(ω1…ωn)]+O(1)lim infn[n−C(ω1…ωn)]+O(1)lim infn[n+K(n)−K(ω1…ωn)]+O(1).

[1] J.S. Miller. "Every 2-random real is Kolmogorov random." Journal of Symbolic Logic, 69(3):907–913, 2004.

[2] A. Nies, F. Stephan, and S.A. Terwijn. "Randomness, relativization and turing degrees." The Journal of Symbolic Logic, 70(2), 2005.

[3] J.S. Miller. "The K-degrees, low for K-degrees, and weakly low for K sets." Notre Dame Journal of Formal Logic, 50(4):381–391, 2009.

[4] R.G. Downey and D.R. Hirschfeldt. "Algorithmic Randomness and Complexity." Theory and Applications of Computability. Springer, 2010.

Available Formats

Format	Quality	Bitrate	Size
MPEG-4 Video	640x360	1.84 Mbits/sec	463.28 MB	View	Download
WebM	640x360	786.93 kbits/sec	192.60 MB	View	Download
Flash Video	484x272	568.82 kbits/sec	139.15 MB	View	Download
iPod Video	480x270	506.24 kbits/sec	123.84 MB	View	Download
MP3	44100 Hz	125.0 kbits/sec	30.46 MB	Listen	Download
Auto *	(Allows browser to choose a format it supports)