Article contents
RECOGNIZING STRONG RANDOM REALS
Published online by Cambridge University Press: 01 June 2008
Abstract
The class of strong random reals can be defined via a natural conception of effective null set. We show that the same class is also characterized by a learning-theoretic criterion of ‘recognizability’.
- Type
- Research Article
- Information
- Copyright
- Copyright © Association for Symbolic Logic 2008
References
BIBLIOGRAPHY
Ambos-Spies, K., Weihrauch, K., & Zheng, X. (2000). Weakly computable real numbers. Journal of Complexity, 16, 676–690.CrossRefGoogle Scholar
Downey, R., & Hirschfeldt, D. R. (2008). Algorithmic Randomness and Complexity. New York: Springer-Verlag.Google Scholar
Downey, R., Hirschfeldt, D. R., Nies, A., & Terwijn, S. A. (2006a). Calibrating randomness. Bulletin of Symbolic Logic, 12, 411–491.CrossRefGoogle Scholar
Downey, R., Nies, A., Weber, R., & Yu, L. (2006b). Lowness and π02 nullsets.. The Journal of Symbolic Logic, 71, 1044–1052.CrossRefGoogle Scholar
Eagle, A. (2005). Randomness is unpredictability. British Journal for the Philosophy of Science, 56, 749–790.CrossRefGoogle Scholar
Earman, J. (1986). A Primer on Determinism. Dordrecht, The Netherlands: D. Reidel.CrossRefGoogle Scholar
Gács, P. (1986). Every sequence is reducible to a random one. Information and Control, 70, 186–192.CrossRefGoogle Scholar
Gold, E. M. (1965). Limiting recursion. The Journal of Symbolic Logic, 30, 20–48.CrossRefGoogle Scholar
Goldreich, O. (2001). Foundations of Cryptography: vol. 1, Basic Tools. New York: Cambridge University Press.CrossRefGoogle Scholar
Kuèera, A. (1985). Measure,π01 classes, and complete extensions of PA. In Proceedings of a Conference held in Oberwolfach, West Germany, April 15–21, 1984 Series: Lecture Notes in Mathematics, vol. 1141. Ebbinghaus, H.-D., Müller, G. H., and Sacks, G. E., editors. Springer, pp. 245–259.Google Scholar
Kurtz, S. A. (1981). Randomness and genericity in the degrees of unsolvability. PhD dissertation, University of Illinois.Google Scholar
Levin, L. A. (1973). The concept of random sequence. Doklady Akademii Nauk SSSR, 212, 548–550. Cited in Uspenskii et al. [1990].Google Scholar
Li, M., & Vitányi, P. B. M. (1997). An Introduction to Kolmogorov Complexity and Its Applications (second edition). New York: Springer.CrossRefGoogle Scholar
Lieb, E. H., Osherson, D., & Weinstein, S. (2006). Elementary proof of a theorem of Jean Ville. Available online from: http:arxiv.org/PS_cache/cs/pdf/0607/0607054.pdf.Google Scholar
Martin-Löf, P. (1966). The definition of random sequences. Information and Control, 9, 602–619.CrossRefGoogle Scholar
Medin, D. L., Ross, B. H., & Markman, A. B. (2005). Cognitive Psychology (fourth edition). New York: John Wiley & Sons.Google Scholar
Moser, J. (1973). Stable and Random Motions in Dynamical Systems (With Special Emphasis on Celestial Mechanics). Princeton, NJ: Princeton University Press.Google Scholar
Oxtoby, J. C. (1971). Measure and Category: A Survey of the Analogies between Topological and Measure Spaces. New York: Springer-Verlag.CrossRefGoogle Scholar
Putnam, H. (1965). Trial and error predicates and the solution to a problem of Mostowski. The Journal of Symbolic Logic, 30, 49–57.CrossRefGoogle Scholar
Schnorr, C. P. (1973). Process complexity and effective random tests. Journal of Computer and System Sciences, 7, 376–378.CrossRefGoogle Scholar
Shoenfield, J. R. (1959). On degrees of unsolvability. Annals of Mathematics, 69, 644–653.CrossRefGoogle Scholar
Uspenskii, V. A., Semenov, A. L., & Shen, A. K. (1990). Can an individual sequence of zeros and ones be random? Russian Mathematical Surveys, 45, 121–189.CrossRefGoogle Scholar
von Mises, R. (1919). Grundlagen der Wahrscheinlichkeitsrechnung. Mathematische Zeitschrift, 5, 52–99.CrossRefGoogle Scholar
- 6
- Cited by