arrow
Volume 7, Issue 1
Upper Limitation of Kolmogorov Complexity and Universal P. Martin-Löf Tests

C. Calude & I. Ghitescu

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

Published online: 1989-07

Export citation
  • Abstract

In this paper we study the Kolmogorov 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 recursive 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 = {C. Calude and I. Ghitescu}, title = {Upper Limitation of Kolmogorov Complexity and Universal P. Martin-Löf Tests}, journal = {Journal of Computational Mathematics}, year = {1989}, volume = {7}, number = {1}, pages = {61--70}, abstract = {

In this paper we study the Kolmogorov 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 recursive 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-Löf Tests AU - C. Calude & I. Ghitescu 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 Kolmogorov 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 recursive 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 and I. Ghitescu. (1989). Upper Limitation of Kolmogorov Complexity and Universal P. Martin-Löf Tests. Journal of Computational Mathematics. 7 (1). 61-70. doi:
Copy to clipboard
The citation has been copied to your clipboard