- #1

- 111

- 0

## Main Question or Discussion Point

Please help me to understand the answer I found on mathoverflow.

The question was: "Do all uncountable sets contain elements with infinite Kolmogorov complexity?"

The reasoning is clear for me, but I'd like to understand every word of the answer, which is the following:

"...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.)"

I tried to understand the words in the context, please confirm that I understand the following special phrases correctly.

"given a language L⊆{0,1}"

means:

"given L, an arbitrary infinite series of 0 and 1 characters"

"program that decides L"

means:

"program that outputs L"

If this is OK, I still don't understand what " programs that recognize L" means?

Thank you for your help.

The question was: "Do all uncountable sets contain elements with infinite Kolmogorov complexity?"

The reasoning is clear for me, but I'd like to understand every word of the answer, which is the following:

"...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.)"

I tried to understand the words in the context, please confirm that I understand the following special phrases correctly.

"given a language L⊆{0,1}"

means:

"given L, an arbitrary infinite series of 0 and 1 characters"

"program that decides L"

means:

"program that outputs L"

If this is OK, I still don't understand what " programs that recognize L" means?

Thank you for your help.