{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T00:02:19Z","timestamp":1648771339488},"reference-count":16,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2019,11,4]],"date-time":"2019-11-04T00:00:00Z","timestamp":1572825600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["The Review of Symbolic Logic"],"published-print":{"date-parts":[[2021,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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\u2014specifying under what conditions a pattern may be said to have been detected by a computable learning function\u2014and 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\u00f6f randomness\u2014arguably, 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\u00f6f randomness. We then show that Schnorr randomness, another central algorithmic randomness notion, also admits a learning-theoretic characterisation in this setting.<\/jats:p>","DOI":"10.1017\/s175502031900042x","type":"journal-article","created":{"date-parts":[[2019,11,4]],"date-time":"2019-11-04T11:17:35Z","timestamp":1572866255000},"page":"531-549","update-policy":"http:\/\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":1,"title":["A LEARNING-THEORETIC CHARACTERISATION OF MARTIN-L\u00d6F RANDOMNESS AND SCHNORR RANDOMNESS"],"prefix":"10.1017","volume":"14","author":[{"given":"FRANCESCA","family":"ZAFFORA BLANDO","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2019,11,4]]},"reference":[{"key":"S175502031900042X_r7","first-page":"337","article-title":"Uniform tests of randomness","volume":"17","author":"Levin","year":"1976","journal-title":"Soviet Mathematics Doklady"},{"key":"S175502031900042X_r9","doi-asserted-by":"publisher","DOI":"10.3233\/COM-13015"},{"key":"S175502031900042X_r10","volume-title":"Systems that Learn","author":"Osherson","year":"1986"},{"key":"S175502031900042X_r6","first-page":"1413","article-title":"On the notion of a random sequence","volume":"14","author":"Levin","year":"1973","journal-title":"Soviet Mathematics Doklady"},{"key":"S175502031900042X_r11","doi-asserted-by":"publisher","DOI":"10.1017\/S1755020308080076"},{"key":"S175502031900042X_r3","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(67)91165-5"},{"key":"S175502031900042X_r13","doi-asserted-by":"publisher","DOI":"10.1007\/BF01694181"},{"key":"S175502031900042X_r8","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(66)80018-9"},{"key":"S175502031900042X_r12","first-page":"761","volume-title":"The Philosophy of Rudolf Carnap","author":"Putnam","year":"1963"},{"key":"S175502031900042X_r14","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0112458"},{"key":"S175502031900042X_r4","first-page":"1","article-title":"Three approaches to the quantitative definition of information","volume":"1","author":"Kolmogorov","year":"1965","journal-title":"Problems of Information Transmission"},{"key":"S175502031900042X_r5","volume-title":"Randomness and Genericity in the Degrees of Unsolvability","author":"Kurtz","year":"1981"},{"key":"S175502031900042X_r16","volume-title":"\u00c9tude critique de la notion de collectif","author":"Ville","year":"1939"},{"key":"S175502031900042X_r15","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(64)90131-7"},{"key":"S175502031900042X_r1","doi-asserted-by":"publisher","DOI":"10.1145\/321356.321363"},{"key":"S175502031900042X_r2","doi-asserted-by":"publisher","DOI":"10.2307\/2273587"}],"container-title":["The Review of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S175502031900042X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,29]],"date-time":"2021-10-29T09:01:03Z","timestamp":1635498063000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S175502031900042X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,4]]},"references-count":16,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["S175502031900042X"],"URL":"https:\/\/doi.org\/10.1017\/s175502031900042x","relation":{},"ISSN":["1755-0203","1755-0211"],"issn-type":[{"value":"1755-0203","type":"print"},{"value":"1755-0211","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,11,4]]},"assertion":[{"value":"\u00a9 Association for Symbolic Logic, 2019","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}