General random sequences and learnable sequences

Abstract

A bstract 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.