General random sequences and learnable sequences

Journal of Symbolic Logic 42 (3):329-340 (1977)
  Copy   BIBTEX


We formalise the notion of those infinite binary sequences z that admit a single program P which expresses the entire algorithmical structure of z. Such a program P minimizes the information which must be used in a relative computation for z. We propose two concepts with different strength for this notion, the learnable and the super-learnable sequences. We establish three different equivalent characterizations of learnable (super-learnable, resp.) sequences. In particular, we prove that a sequences z is learnable (super-learnable, resp.) if and only if there is a computable probability measure p such that p is Schnorr (Martin-Lof, resp.) p-random. There is a recursively enumerable sequence which is not learnable. The learnable sequences are invariant with respect to all total and effective transformations of infinite binary sequences



    Upload a copy of this work     Papers currently archived: 91,102

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

The theory of random propositions.John D. Norton - 1994 - Erkenntnis 41 (3):325 - 352.
Laver sequences for extendible and super-almost-huge cardinals.Paul Corazza - 1999 - Journal of Symbolic Logic 64 (3):963-983.
Similarity among nucleotides sequences.Feng Shi & Zhongxi Mo - 2002 - Acta Biotheoretica 50 (2):95-99.
More about relatively lawless sequences.Joan Rand Moschovakis - 1994 - Journal of Symbolic Logic 59 (3):813-829.
Creative sequences and double sequences.M. Adrian Carpentier - 1968 - Notre Dame Journal of Formal Logic 9 (1):35-61.
What is the type-1/type-2 distinction?Nick Chater - 1997 - Behavioral and Brain Sciences 20 (1):68-69.
Relative lawlessness in intuitionistic analysis.Joan Rand Moschovakis - 1987 - Journal of Symbolic Logic 52 (1):68-88.


Added to PP

28 (#506,167)

6 months
2 (#785,137)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Computable randomness and betting for computable probability spaces.Jason Rute - 2016 - Mathematical Logic Quarterly 62 (4-5):335-366.

Add more citations

References found in this work

No references found.

Add more references