| Autor: |
Goos, Gerhard, Hartmanis, Juris, van Leeuwen, Jan, Diks, Krzysztof, Rytter, Wojciech, Merkle, Wolfgang, Mihailović, Nenad |
| Zdroj: |
Mathematical Foundations of Computer Science 2002; 2002, p568-580, 13p |
| Abstrakt: |
We give a direct and rather simple construction of Martin-Löf random and rec-random sets with certain additional properties. First, reviewing the result of Gács and Kučera, given any set X we construct a Martin-Löf random set R from which X can be decoded effectively. Second, by essentially the same construction we obtain a Martin-Löf random set R that is computably enumerable selfreducible. Alternatively, using the observation that a set is computably enumerable selfreducible if and only if its associated real is computably enumerable, the existence of such a set R follows from the known fact that every Chaitin Ω real is Martin-Löf random and computably enumerable. Third, by a variant of the basic construction we obtain a rec-random set that is weak truth-table autoreducible. The mentioned results on self- and autoreducibility complement work of Ebert, Merkle, and Vollmer [7,8,9], from which it follows that no Martin-Löf random set is Turing-autoreducible and that no rec-random set is truth-table autoreducible. [ABSTRACT FROM AUTHOR] |
| Databáze: |
Supplemental Index |
| Externí odkaz: |
|
