Process complexity and effective random tests

摘要

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.