Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-26T09:12:06.038Z Has data issue: false hasContentIssue false
  • English
  • Français

ω-CHANGE RANDOMNESS AND WEAK DEMUTH RANDOMNESS

Published online by Cambridge University Press:  18 August 2014

JOHANNA N. Y. FRANKLIN  and
KENG MENG NG
JOHANNA N. Y. FRANKLIN
Affiliation:
DEPARTMENT OF MATHEMATICS 196 AUDITORIUM ROAD UNIVERSITY OF CONNECTICUT, U-3009 STORRS, CT 06269-3009, USAE-mail: [email protected]
KENG MENG NG
Affiliation:
SCHOOL OF PHYSICAL & MATHEMATICAL SCIENCES NANYANG TECHNOLOGICAL UNIVERSITY 21 NANYANG LINK SINGAPOREE-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

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.

Keywords

Difference randomnessomega-change randomnessweak Demuth randomnessbalanced randomness
Type
Articles
Information
The Journal of Symbolic Logic , Volume 79 , Issue 3 , September 2014 , pp. 776 - 791
Copyright
Copyright © The Association for Symbolic Logic 2014 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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
Downey, 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
Franklin, 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
Hirschfeldt, D. and Miller, J.. Unpublished.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é. Computability and randomness, Clarendon Press, Oxford, 2009.CrossRefGoogle 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