Hostname: page-component-cd9895bd7-gbm5v Total loading time: 0 Render date: 2024-12-22T20:47:31.105Z Has data issue: false hasContentIssue false

A LEARNING-THEORETIC CHARACTERISATION OF MARTIN-LÖF RANDOMNESS AND SCHNORR RANDOMNESS

Published online by Cambridge University Press:  04 November 2019

FRANCESCA ZAFFORA BLANDO*
Affiliation:
DEPARTMENT OF PHILOSOPHY AND LOGICAL DYNAMICS LAB (CSLI) STANFORD UNIVERSITYSTANFORD, CA94305-2155, USAE-mail: [email protected]

Abstract

Numerous learning tasks can be described as the process of extrapolating patterns from observed data. One of the driving intuitions behind the theory of algorithmic randomness is that randomness amounts to the absence of any effectively detectable patterns: it is thus natural to regard randomness as antithetical to inductive learning. Osherson and Weinstein [11] draw upon the identification of randomness with unlearnability to introduce a learning-theoretic framework (in the spirit of formal learning theory) for modelling algorithmic randomness. They define two success criteria—specifying under what conditions a pattern may be said to have been detected by a computable learning function—and prove that the collections of data sequences on which these criteria cannot be satisfied correspond to the set of weak 1-randoms and the set of weak 2-randoms, respectively. This learning-theoretic approach affords an intuitive perspective on algorithmic randomness, and it invites the question of whether restricting attention to learning-theoretic success criteria comes at an expressivity cost. In other words, is the framework expressive enough to capture most core algorithmic randomness notions and, in particular, Martin-Löf randomness—arguably, the most prominent algorithmic randomness notion in the literature? In this article, we answer the latter question in the affirmative by providing a learning-theoretic characterisation of Martin-Löf randomness. We then show that Schnorr randomness, another central algorithmic randomness notion, also admits a learning-theoretic characterisation in this setting.

Type
Research Article
Copyright
© Association for Symbolic Logic, 2019

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

BIBLIOGRAPHY

[1] Chaitin, G. J. (1966). On the length of programs for computing finite binary sequences. Journal of the Association for Computing Machinery, 13, 547569.CrossRefGoogle Scholar
[2] Gaifman, H. & Snir, M. (1982). Probabilities over rich languages, testing and randomness. The Journal of Symbolic Logic, 47, 495548.CrossRefGoogle Scholar
[3] Gold, E. (1967). Language identification in the limit. Information and Control, 10, 447474.CrossRefGoogle Scholar
[4] Kolmogorov, A. N. (1965). Three approaches to the quantitative definition of information. Problems of Information Transmission, 1, 17.Google Scholar
[5] Kurtz, S. A. (1981). Randomness and Genericity in the Degrees of Unsolvability. Ph.D. Dissertation, University of Illinois at Urbana-Champaign.Google Scholar
[6] Levin, L. A. (1973). On the notion of a random sequence. Soviet Mathematics Doklady, 14, 14131416.Google Scholar
[7] Levin, L. A. (1976). Uniform tests of randomness. Soviet Mathematics Doklady, 17 (2), 337340.Google Scholar
[8] Martin-Löf, P. (1966). The definition of a random sequence. Information and Control, 9, 602619.CrossRefGoogle Scholar
[9] Miyabe, K. (2013). L 1-Computability, layerwise computability and Solovay reducibility. Computability, 2, 1529.CrossRefGoogle Scholar
[10] Osherson, D., Stob, M., & Weinstein, S. (1986). Systems that Learn (first edition). Cambridge, MA: MIT Press.Google Scholar
[11] Osherson, D. & Weinstein, S. (2008). Recognizing strong random reals. The Review of Symbolic Logic, 1(1), 5663.CrossRefGoogle Scholar
[12] Putnam, H. (1963). ‘Degree of confirmation’ and inductive logic. In Schilpp, P. A., editor. The Philosophy of Rudolf Carnap. La Salle, III: Open Court, pp. 761783.Google Scholar
[13] Schnorr, C. P. (1971a). A unified approach to the definition of a random sequence. Mathematical Systems Theory, 5, 246258.CrossRefGoogle Scholar
[14] Schnorr, C. P. (1971b). Zufälligkeit und Wahrscheinlichkeit: Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. Lecture Notes in Mathematics, Vol. 218. Berlin, Heidelberg: Springer-Verlag.CrossRefGoogle Scholar
[15] Solomonoff, R. J. (1964). A formal theory of inductive inference, I and II. Information and Control, 7, 1–22 and 224254.CrossRefGoogle Scholar
[16] Ville, J. (1939). Étude critique de la notion de collectif. Monographies des probabilités. Paris: Gauthiers-Villars.Google Scholar