0
$\begingroup$

The statement of theorem 3 in "A frequentist understanding of sets of measures" by Fierens, Rêgo, and Fine (pdf available here) requires that the Kolmogorov complexity of a certain function be less than a certain constant. The function selects subsequences from finite sequences.

I understand Kolmogorov complexity to be defined only relative to a choice of language for expressing functions, but Fierens et al. never mention a language. I would understand leaving out reference to the language if they gave an inequality with Kolmogorov complexity operators on both sides, but how can we require that the K.c. be less than a constant without choosing a language first? Is there a default method for expressing functions that Fierens et al. might expect readers to assume?

(I would be happy to include the inequality from the article here if that would be helpful. However, the LaTeX will be somewhat complicated, and I'll have to explain what all the parameters mean. I don't think the details of the inequality matter.)

$\endgroup$
0
$\begingroup$

I seem to have found an answer, but would be happy if anyone else has a fuller answer that provides more insight.

An earlier paper by two of the same authors, "Toward a frequentist interpretation of sets of measures" by Fierens and Fine, defines Kolmogorov complexity in a similar context to that of the paper mentioned in the question. Fierens and Fine define the Kologorov complexity of a finite string of elements as "the length $|p|$ of the shortest binary-valued string $p$ that is a program for the universal Turning machine (UTM) $\Psi$ whose output is the desired string ...." (4th page of PDF).

It's a good guess that this is what's meant by Kolmogorov complexity in the paper mentioned in my question. And if "binary-valued ... program for the universal Turing machine ... whose output is ..." specifies a string whose length is determinate, then this specification would answer my question.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.