Volume 7, Issue 1
Upper Limitation of Kolmogorov Complexity and Universal P Martin-Lof Tests

C. Calude & I. Ghitescu

DOI:

J. Comp. Math., 7 (1989), pp. 61-70

Published online: 1989-07

Preview Full PDF 413 2135
Export citation
  • Abstract

In this paper we study the Kolmogorove complexity of initial strings in infinite sequences (being inspired by [9]), and we relate it with the theory of P. Martin-Lof random sequences, Working with partial recursive functions instead of recurisve functions we can localize on an apriori given recursive set the points where the complexity is small. The relation between Kolmogorov's complexity and P. Martin-Lof's universal tests enables us to show that the randomness theories for finite strings and infinite sequences are not compatible(e.g.because no universal test is sequential). We lay stress upon the fact that we work within the general framework of a non-necessarily binary alphabet.

  • Keywords

  • AMS Subject Headings

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@Article{JCM-7-61, author = {}, title = {Upper Limitation of Kolmogorov Complexity and Universal P Martin-Lof Tests}, journal = {Journal of Computational Mathematics}, year = {1989}, volume = {7}, number = {1}, pages = {61--70}, abstract = { In this paper we study the Kolmogorove complexity of initial strings in infinite sequences (being inspired by [9]), and we relate it with the theory of P. Martin-Lof random sequences, Working with partial recursive functions instead of recurisve functions we can localize on an apriori given recursive set the points where the complexity is small. The relation between Kolmogorov's complexity and P. Martin-Lof's universal tests enables us to show that the randomness theories for finite strings and infinite sequences are not compatible(e.g.because no universal test is sequential). We lay stress upon the fact that we work within the general framework of a non-necessarily binary alphabet. }, issn = {1991-7139}, doi = {https://doi.org/}, url = {http://global-sci.org/intro/article_detail/jcm/9456.html} }
TY - JOUR T1 - Upper Limitation of Kolmogorov Complexity and Universal P Martin-Lof Tests JO - Journal of Computational Mathematics VL - 1 SP - 61 EP - 70 PY - 1989 DA - 1989/07 SN - 7 DO - http://doi.org/ UR - https://global-sci.org/intro/article_detail/jcm/9456.html KW - AB - In this paper we study the Kolmogorove complexity of initial strings in infinite sequences (being inspired by [9]), and we relate it with the theory of P. Martin-Lof random sequences, Working with partial recursive functions instead of recurisve functions we can localize on an apriori given recursive set the points where the complexity is small. The relation between Kolmogorov's complexity and P. Martin-Lof's universal tests enables us to show that the randomness theories for finite strings and infinite sequences are not compatible(e.g.because no universal test is sequential). We lay stress upon the fact that we work within the general framework of a non-necessarily binary alphabet.
C. Calude & I. Ghitescu. (1970). Upper Limitation of Kolmogorov Complexity and Universal P Martin-Lof Tests. Journal of Computational Mathematics. 7 (1). 61-70. doi:
Copy to clipboard
The citation has been copied to your clipboard