A LEARNING-THEORETIC CHARACTERISATION OF MARTIN-LÖF RANDOMNESS AND SCHNORR RANDOMNESS.
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...
| Published in: | Review of Symbolic Logic Vol. 14; no. 2; pp. 531 - 550 |
|---|---|
| Main Author: | |
| Format: | Article |
| Published: |
Cambridge University Press
Jun2021
|
| Subjects: | |
| Online Access: | View this record in EBSCOhost |
| fields | @attributes: recordID: 1 pdfLink: plink: https://search.ebscohost.com/login.aspx?direct=true&db=hlh&AN=151440481&site=ehost-live header: @attributes: shortDbName: hlh uiTerm: 151440481 longDbName: Humanities International Complete uiTag: AN controlInfo: bkinfo: jinfo: jid: 17550203 8OI1 jtl: Review of Symbolic Logic issn: 17550203 maglogo: N pubinfo: dt: Jun2021 vid: 14 iid: 2 pid: 15979 pub: Cambridge University Press artinfo: ui: 151440481 10.1017/S175502031900042X ppf: 531 ppct: 19 formats: tig: atl: A LEARNING-THEORETIC CHARACTERISATION OF MARTIN-LÖF RANDOMNESS AND SCHNORR RANDOMNESS. aug: au: BLANDO, FRANCESCA ZAFFORA affil: DEPARTMENT OF PHILOSOPHY AND LOGICAL DYNAMICS LAB (CSLI) STANFORD UNIVERSITY STANFORD, CA 94305-2155, USA E-mail su: Algorithmic randomness Self-expression Kolmogorov complexity Acquisition of data Computable functions sug: subj: Algorithmic randomness Self-expression Kolmogorov complexity Acquisition of data Computable functions keyword: 03D32 68Q32 algorithmic randomness formal learning theory ab: 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. pubtype: Academic Journal doctype: Article src: R language: English refInfo: copyright: @attributes: flag: Y dt: @attributes: year: 2021 holdings: @attributes: islocal: N |
|---|