Open AccessComputer ScienceMathematics
DOI: 10.1016/s0022-0000(73)80030-3

Résumé tlooto

A variant of the Kolmogorov concept of complexity which yields a common theory of finite and infinite random sequences and some concepts of effective tests which are proved to be equivalent are established.

Résumé

We propose a variant of the Kolmogorov concept of complexity which yields a common theory of finite and infinite random sequences. Processes are sequential coding schemes such as prefix coding schemes. The process complexity is the minimal length of the description of a sequence in a sequential coding scheme. The process complexity does not oscillate. We establish some concepts of effective tests which are proved to be equivalent.

Format de citation

SCHNORR, C. Process complexity and effective random tests. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1973, 7: 376–388.