No CrossRef data available.
Article contents
ω-CHANGE RANDOMNESS AND WEAK DEMUTH RANDOMNESS
Published online by Cambridge University Press: 18 August 2014
Abstract
We extend our work on difference randomness. Each component of a difference test is a Boolean combination of two r.e. open sets; here we consider tests in which the kth component is a Boolean combination of g(k) r.e. open sets for a given recursive function g. We use this method to produce an alternate characterization of weak Demuth randomness in terms of these tests and further show that a real is weakly Demuth random if and only if it is Martin-Löf random and cannot compute a strongly prompt r.e. set. We conclude with a study of related lowness notions and obtain as a corollary that lowness for balanced randomness is equivalent to being recursive.
- Type
- Articles
- Information
- Copyright
- Copyright © The Association for Symbolic Logic 2014
References
REFERENCES
Ambos-Spies, K., Jockusch, C., Shore, R., and Soare, R.. An algebraic decomposition of recursively enumerable degrees and the coincidence of several degree classes with the promptly simple degrees. Transactions of the American Mathematical Society, vol. 281 (1984), pp. 109–128.CrossRefGoogle Scholar
Barmpalias, George, Miller, Joseph S., and Nies, André. Randomness notions and partial relativization. Israel Journal of Mathematics, vol. 191 (2012), no. 2, pp. 791–816.Google Scholar
Bienvenu, Laurent, Day, Adam R., Greenberg, Noam, Kučera, Antonín, Miller, Joseph S., Nies, André, and Turetsky, Dan. Computing K-trivial sets by incomplete random sets. Bulletin of Symbolic Logic. To appear.Google Scholar
Demuth, Osvald. On some classes of arithmetical real numbers. Commentationes Mathematicae Universitatis Carolinae, vol. 23 (1982), pp. 453–465. In Russian.Google Scholar
Diamondstone, David and Ng, Keng Meng. Strengthening prompt simplicity, this Journal, vol. 76 (2011), no, 3, pp. 946–972.Google Scholar
Downey, Rod, Nies, André, Weber, Rebecca, and Yu, Liang. Lowness and 
${\rm{\Pi }}_2^0 $nullsets, this Journal, vol. 71 (2006), no. 3, pp. 1044–1052.Google Scholar
${\rm{\Pi }}_2^0 $nullsets, this Journal, vol. 71 (2006), no. 3, pp. 1044–1052.Google ScholarDowney, Rodney G. and Hirschfeldt, Denis R.. Algorithmic randomness and complexity, Springer, New York, 2010.Google Scholar
Figueira, Santiago, Hirschfeldt, Denis, Miller, Joseph S., Ng, Keng Meng, and Nies, André. Counting the changes of random${\rm{\Delta }}_2^0 $sets, Programs, proofs, processes, Lecture Notes in Computer Science, vol. 6158, Springer, Berlin, 2010, pp. 162–171.CrossRefGoogle Scholar
${\rm{\Delta }}_2^0 $sets, Programs, proofs, processes, Lecture Notes in Computer Science, vol. 6158, Springer, Berlin, 2010, pp. 162–171.CrossRefGoogle ScholarFranklin, Johanna N. Y. and Ng, Keng Meng. Difference randomness. Proceedings of the American Mathematical Society, vol. 139 (2011), no. 1, pp. 345–360.Google Scholar
Greenberg, Noam and Nies, André. Benign cost functions and lowness properties, this Journal, vol. 76 (2011), no. 1, pp. 289–312.Google Scholar
Kučera, Antonín and Nies, André. Demuth randomness and computational complexity. Annals of Pure and Applied Logic, vol. 162 (2011), no. 7, pp. 504–513.Google Scholar
Nies, André, Stephan, Frank, and Terwijn, Sebastiaan A.. Randomness, relativization and Turing degrees, this Journal, vol. 70 (2005), no. 2, pp. 515–535.Google Scholar
Soare, Robert I.. Recursively enumerable sets and degrees, Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987.Google Scholar
Stephan, Frank. Martin-Löf random and PA-complete sets, Technical Report 58, Matematisches Institut, Universität Heidelberg, Heidelberg, 2002.Google Scholar