- #1
zrek
- 115
- 0
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.