über die Definition von effektiven Zufallstests

Research paper by Claus -Peter Schnorr

Indexed on: 01 Dec '70Published on: 01 Dec '70Published in: Probability Theory and Related Fields


A new approach is made to characterize random sequences by introducing the concept of effective test function. A test function is a computable function that associates to each finite sequence a positive real number which indicates the extend to which the sequence stands the stochasticity test under consideration. Each test function has a corresponding set of measure zero, namely the set that consists of all infinite sequences which do not stand the test. This type of constructive null set is a generalization of the set of measure zero as defined by Brouwer. We will prove that test functions and sets of measure zero in the sense of Brouwer imply equivalent definitions of random sequences.