Randomness and Recursive Enumerability
Randomness and Recursive Enumerability
复制标题
随机性和递归可枚举性
DOI：
10.1137/s0097539799357441
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
T. Slaman
中科院分区：
文献类型：
--
作者：
A. Kucera;T. Slaman
如果存在逼近 $\alpha$ 的有理数 $(a[n]:n\in\omega)$ 逼近 $\alpha$ 和逼近 $\beta$ 的 $(b[n]:n\in\omega)$ 的非递减递归序列以及一个正常数 C，使得对于所有 n，$C(\alpha-a[n])\geq(\beta-b[n])$，一个递归可枚举实数 $\alpha$ 支配另一个 $\beta$。参见[R. M. Solovay，关于 Chaitin 工作的论文（或系列论文）草稿，手稿，IBM Thomas J. Watson 研究中心，纽约州约克敦高地，1974 年，第 11 页。 215]和[G. J. Chaitin，IBM J. Res。发展，21（1977），第350--359页]。我们证明每个递归可枚举随机实数支配所有其他递归可枚举实数。我们得出结论，递归可枚举的随机实数正是$\Omega$-数[G. J. Chaitin，IBM J. Res。发展，21（1977），第350--359页]。其次，我们证明了通用 Martin-Lof 随机性检验中的集合具有随机度量，并且每个递归可枚举随机数都是通用 Martin-Lof 检验中表示的度量之和。
One recursively enumerable real $\alpha$ dominates another one $\beta$ if there are nondecreasing recursive sequences of rational numbers $(a[n]:n\in\omega)$ approximating $\alpha$ and $(b[n]:n\in\omega)$ approximating $\beta$ and a positive constant C such that for all n, $C(\alpha-a[n])\geq(\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. Chaitin, IBM J. Res. Develop., 21 (1977), pp. 350--359]. We show that every recursively 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 number is the sum of the measures represented in a universal Martin-Lof test.