General random sequences and learnable sequences

Publisher Website
Google Scholar
Abstract
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 sequence z is learnable (super-learnable, resp.) if and only if there is a computable probability measure p such that p is Schnorr (Martin-Löf, 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.

This publication has 6 references indexed in Scilit: