Take the 2-minute tour ×

Otherwise, if all the elements in a set can be represented by a at most n symbols (finite Kolmogorov complexity), I could count them by creating a n dimensional pairing function. Or atleast, that is my assumption.

Any thoughts?

Edit: as @Carl has pointed out the correct term for sequences that have no finite representation is Kolmogorov Random not infinite as I used in my title.

share|improve this question
This is a little imprecise, because sets can contain anything, such as other sets, and symbols such as Heart, Elephant, and Galaxy - and I don't mean the string representation of those things, but those actual things. Kolmogorov complexity is about strings only. It is unclear what the Kolmogorov complexity of an Elephant is. If you're talking about sets of finite strings, like Rune states below, those are always countable. If you're talking about sets of infinite strings, it's also unclear what the Kolmogorov complexity of infinite strings are. –  Henry Yuen Jul 12 '10 at 17:40
This question reveals a basic misunderstanding about cardinalities. It does not look appropriate for MO. –  Andres Caicedo Jul 12 '10 at 17:50
@Andres could you elaborate on your comment for my own edification? –  Jonathan Fischoff Jul 12 '10 at 18:17
The question is not well posed. Kolmogorov complexity is defined for finite strings from some (finite or countable) alphabet. There are two issues with the question. (1) Every string has finite Kolmogorov complexity: there is no definition of "infinite Kolmogorov complexity". (2) Since any finite or countable alphabet makes only countably many finite strings, there are never uncountably many strings to put into a set. –  Carl Mummert Jul 12 '10 at 19:40
Even if you change the terminology, I don't understand where the "at most n symbols" issue arises, or how a pairing function is related to the question. If you are asking whether every uncountable set of infinite binary sequences must contain a Kolmogorov random element, the answer is no. One example if the set of sequences that have a 0 in every even position but no constraints on the odd positions. This set has the cardinality of the continuum but contains no random sequences. –  Carl Mummert Jul 12 '10 at 22:01

3 Answers 3

up vote 7 down vote accepted

Contrary to what some of the commenters said, there's no great difficulty in generalizing Kolmogorov complexity to infinite strings. For example, given a language L⊆{0,1}*, we could let K(L) be the length of the shortest program that decides L, or K(L)=∞ if L is undecidable. (Or we could also talk about programs that recognize L, in which case even the language HALT would have a finite complexity.)

In either case, the OP's intuition is essentially correct: if a set S of languages is uncountable, then since there are only countably many decidable or recognizable languages, clearly there must exist a language L∈S such that K(L)=∞.

share|improve this answer

I'm not sure if I understand your question, but the set of all finite strings is countable, thus a set in which every element has a name (i.e., a finite description) is countable.

share|improve this answer

As Carl said, Kolmogorov complexity is defined mainly for finite strings. It can be extended to other domains of objects but one needs to fix an enumeration of those objects. (An enumeration is a partial function from finite strings to those objects, e.g. Scott mentions two partial enumerations: the language decided by a TM represented by its encoding, and the language recognized by a TM represented by its encoding).

If the domain of objects is uncountable then there is no enumeration that covers all of the objects in the domain so there will be objects left out of the enumeration. For the objects in the enumeration one can define the Kolmogorov complexity of an object as the minimum among the Kolmogorov complexity of its names. Those outside the enumeration will have no names (w.r.t. that enumeration) and one can say they have infinite Kolmogorov complexity.

So if you have an infinite domain it will have objects which don't have finite Kolmogorov complexity.

However, the choice of the enumeration is important here and easily change whether an object has a finite Kolmogorov complexity or not. Without fixing an enumeration the Kolmogorov complexity of an object doesn't have a meaning.

share|improve this answer

Your Answer


