Computing upper bounds on on Kolmogorov Complexity is not very difficult: gzip and all the other compression algorithms do it. The difficulty is computing non-trivial lower bounds: For all programming languages (with a self-terminating encoding), there is a trivial lower bound that doesn’t depend on the string. This bound is at least one token.
But there is also a language-dependent constant L_max which is the maximum KC complexity and lower bound on KC complexity that you can compute for any string: L_max is the length of the shortest program for which the halting property is uncomputable ( * ) (which makes L_max is uncomputable as well). This implies that you can compute the KC complexity only for a finite number of strings.
There is no such thing as “the shortest program for which the halting property is uncomputable”. That property is computable trivially for every possible program. What’s uncomputable is always the halting problem for an infinity of programs using one common algorithm.
It is also easy to make up artificial languages in which Kolmogorov complexity is computable for an infinite subset of all possible strings.
You were probably thinking of something else: that there exists a constant L, which depends on the language and a proof system T, such that it’s not possible to prove in T that any string has Kolmogorov complexity larger than L. That is true. In particular, this means that there’s a limit to lower bounds we can establish, although we don’t know what that limit is.
There is no such thing as “the shortest program for which the halting property is uncomputable”. That property is computable trivially for every possible program.
The halting property is semi-decidable: if a program halts, then you can always trivially prove that it halts, you just need run it. If a program does not halt, then sometimes you can prove that it doesn’t halt, and sometimes you can’t prove anything. For any programming language, there exist a length such that you can compute the halting property for all programs shorter than that. At length L_max, there will be program Bad_0, which:
Does not halt.
Can’t be proven not to halt.
Doesn’t emit any output symbol.
It can’t be proven that there exist any string of output symbols that it doesn’t emit.
You can never prove that any string S has Kolmogorov complexity K if K > L_max, as it would imply that you proved that Bad_0 doesn’t halt, or at least doesn’t emit any symbol which is not a prefix of S.
Since there are only finitely many strings with complexity up to L_max, we can only compute Kolmogorov complexity, for finitely many strings.
It is also easy to make up artificial languages in which Kolmogorov complexity is computable for an infinite subset of all possible strings.
If the language is Turing-complete I don’t think this is possible. If you think that an arbitrary string S has complexity K, how can you prove that there exist no program shorter than K that computes S?
Computing upper bounds on on Kolmogorov Complexity is not very difficult: gzip and all the other compression algorithms do it. The difficulty is computing non-trivial lower bounds:
For all programming languages (with a self-terminating encoding), there is a trivial lower bound that doesn’t depend on the string. This bound is at least one token.
But there is also a language-dependent constant L_max which is the maximum KC complexity and lower bound on KC complexity that you can compute for any string: L_max is the length of the shortest program for which the halting property is uncomputable ( * ) (which makes L_max is uncomputable as well).
This implies that you can compute the KC complexity only for a finite number of strings.
( * And doesn’t provably emit any token)
There is no such thing as “the shortest program for which the halting property is uncomputable”. That property is computable trivially for every possible program. What’s uncomputable is always the halting problem for an infinity of programs using one common algorithm.
It is also easy to make up artificial languages in which Kolmogorov complexity is computable for an infinite subset of all possible strings.
You were probably thinking of something else: that there exists a constant L, which depends on the language and a proof system T, such that it’s not possible to prove in T that any string has Kolmogorov complexity larger than L. That is true. In particular, this means that there’s a limit to lower bounds we can establish, although we don’t know what that limit is.
The halting property is semi-decidable: if a program halts, then you can always trivially prove that it halts, you just need run it. If a program does not halt, then sometimes you can prove that it doesn’t halt, and sometimes you can’t prove anything.
For any programming language, there exist a length such that you can compute the halting property for all programs shorter than that. At length L_max, there will be program Bad_0, which:
Does not halt.
Can’t be proven not to halt.
Doesn’t emit any output symbol.
It can’t be proven that there exist any string of output symbols that it doesn’t emit.
You can never prove that any string S has Kolmogorov complexity K if K > L_max, as it would imply that you proved that Bad_0 doesn’t halt, or at least doesn’t emit any symbol which is not a prefix of S.
Since there are only finitely many strings with complexity up to L_max, we can only compute Kolmogorov complexity, for finitely many strings.
If the language is Turing-complete I don’t think this is possible. If you think that an arbitrary string S has complexity K, how can you prove that there exist no program shorter than K that computes S?
[retracted]