Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with prefix complexity:
TR01-083 | 29th October 2001
Nikolay Vereshchagin

An enumerable undecidable set with low prefix complexity: a simplified proof

Revisions: 1

We present a simplified proof of Solovay-Calude-Coles theorem
stating that there is an enumerable undecidable set with the
following property: prefix
complexity of its initial segment of length n is bounded by prefix
complexity of n (up to an additive constant).

more >>>

TR11-132 | 2nd September 2011
Ludwig Staiger

Oscillation-free Chaitin $h$-random sequences

Revisions: 1

The present paper generalises results by Tadaki [12] and Calude et al. [1] on oscillation-free partially random infinite strings. Moreover, it shows that oscillation-free partial Chaitin randomness can be separated from scillation-free partial strong Martin-L\"of randomness by $\Pi_{1}^{0}$-definable sets of infinite strings.

more >>>

ISSN 1433-8092 | Imprint