ON REPRESENTABILITY OF P. MARTIN-LÓF TESTS
Cristian S. Calude, Ion Chițescu · Czech digital mathematics library · 1983
CRISTIAN CALUDE, ION CHITESCUThe tests of P. Martin-L6f [4] constitute themselves as an alternative to the A. N. Kolmogorov theory of complexity [2].But these theories are not equivalent.In the present paper we investigate the possibility of expressing the P. Martin-L6f tests in terms of Kolmogorov complexity.We show that this can be done by adding an element to the primary alphabet.This "enlarging" procedure generates a series of other problems (for instance, new P. Martin-L6f tests appear, which are not Kolmogorov expressible).