Randomness and recursive enumerability

Citation
A. Kucera et Ta. Slaman, Randomness and recursive enumerability, SIAM J COMP, 31(1), 2001, pp. 199-211
Citations number
20
Categorie Soggetti
Computer Science & Engineering
Journal title
SIAM JOURNAL ON COMPUTING
ISSN journal
00975397 → ACNP
Volume
31
Issue
1
Year of publication
2001
Pages
199 - 211
Database
ISI
SICI code
0097-5397(20010729)31:1<199:RARE>2.0.ZU;2-D
Abstract
One recursively enumerable real alpha dominates another one beta if there a re nondecreasing recursive sequences of rational numbers (a[n] : n is an el ement of omega) approximating alpha and (b[n] : n is an element of omega) a pproximating beta and a positive constant C such that for all n, C (alpha - a[n]) greater than or equal to (beta -b[n]). See [ R. M. Solovay, Draft of a Paper ( or Series of Papers) on Chaitin's Work, manuscript, IBM Thomas J. Watson Research Center, Yorktown Heights, NY, 1974, p. 215] and [G. J. Cha itin, IBM J. Res. Develop., 21 (1977), pp. 350-359]. We show that every rec ursively enumerable random real dominates all other recursively enumerable reals. We conclude that the recursively enumerable random reals are exactly the Omega -numbers [ G. J. Chaitin, IBM J. Res. Develop., 21 ( 1977), pp. 350-359]. Second, we show that the sets in a universal Martin-Lof test for randomness have random measure, and every recursively enumerable random num ber is the sum of the measures represented in a universal Martin-Lof test.