Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR11-132 | 22nd November 2011 13:52

Oscillation-free Chaitin $h$-random sequences

RSS-Feed




Revision #1
Authors: Ludwig Staiger
Accepted on: 22nd November 2011 13:52
Downloads: 2370
Keywords: 


Abstract:

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.



Changes to previous version:

Slightly revised Proposition 1 and improved proof of Theorem 3


Paper:

TR11-132 | 2nd September 2011 13:22

Oscillation-free Chaitin $h$-random sequences





TR11-132
Authors: Ludwig Staiger
Publication: 4th October 2011 11:42
Downloads: 3164
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint