snippetMinor
Generate string with large Kolmogrov complexity
Viewed 0 times
withgeneratelargekolmogrovstringcomplexity
Problem
Given $c$, can you generate a string $s$ with $K(s) \ge c$, along with a proof of that fact?
I think the answer is no except for small $c$, but I'm not sure.
I think the answer is no except for small $c$, but I'm not sure.
Solution
No. This is basically Chaitin's incompleteness theorem.
Roughly, the theorem says that there exists a concrete constant $C$ (which is a function of your consistent set of axioms) for which no fixed string can be proven to have Kolmogorov complexity larger than $C$. The core idea is that if you could do it for every string, then you can write a program of size $\log n + O(1)$ to search for and eventually output strings with complexity $n$, which is a contradiction for sufficiently large $n$.
Roughly, the theorem says that there exists a concrete constant $C$ (which is a function of your consistent set of axioms) for which no fixed string can be proven to have Kolmogorov complexity larger than $C$. The core idea is that if you could do it for every string, then you can write a program of size $\log n + O(1)$ to search for and eventually output strings with complexity $n$, which is a contradiction for sufficiently large $n$.
Context
StackExchange Computer Science Q#63333, answer score: 7
Revisions (0)
No revisions yet.