Year: 1989
Journal of Computational Mathematics, Vol. 7 (1989), Iss. 1 : pp. 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.
You do not have full access to this article.
Already a Subscriber? Sign in as an individual or via your institution
Journal Article Details
Publisher Name: Global Science Press
Language: English
DOI: https://doi.org/1989-JCM-9456
Journal of Computational Mathematics, Vol. 7 (1989), Iss. 1 : pp. 61–70
Published online: 1989-01
AMS Subject Headings:
Copyright: COPYRIGHT: © Global Science Press
Pages: 10