full
search.png

Search

close.png

Cancel

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

Preview Full PDF 2622 25860

Cited by

google scholar semantic scholar
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
BibteX RIS TXT
The citation has been copied to your clipboard