Comparing notions of randomness |
| |
Authors: | Bart Kastermans Steffen Lempp |
| |
Affiliation: | a Department of Mathematics, University of Colorado, Boulder, CO 80309, United States b Department of Mathematics, University of Wisconsin, Madison, WI 53706-1388, United States |
| |
Abstract: | It is an open problem in the area of effective (algorithmic) randomness whether Kolmogorov-Loveland randomness coincides with Martin-Löf randomness. Joe Miller and André Nies suggested some variations of Kolmogorov-Loveland randomness to approach this problem and to provide a partial solution. We show that their proposed notion of injective randomness is still weaker than Martin-Löf randomness. Since in this proof some of the ideas we use are clearer, we also show the weaker theorem that permutation randomness is weaker than Martin-Löf randomness. |
| |
Keywords: | Effective randomness Kolmogorov-Loveland randomness Martin-Lö f randomness |
本文献已被 ScienceDirect 等数据库收录! |
|