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'...
I know this reeks of witch-hunting, but... I have a hunch that u/Eugine_Nier is back under the guise of u/Azathoth123. Reasons:
I don't have an axe to grind against the guy, I've only spoken to him a couple of times and didn't notice any particularly large karma hits afterwards, I just really dislike it when someone skirts the rules like that. Disruptive users evading permanent bans never helped any community ever.
Obviously I'm posting this here because I think a moderator should look into the matter. Usually I would be posting a disclaimer of some sort, apologizing in advance to Azathoth123 for attacking his standing with slanderous accusations if this turned out not to be the case. Well, I won't. The more I look into the matter, the more confident I get that they're the same person. Azathoth, if you're reading this and you're not Eugine_Nier, then I strongly advise you go search for your twin brother, I think you'll get along very well. Seriously, I'm saying this in good faith. You have a suspiciously great deal of things in common.
If retributive downvoting is (still) a concern (if not, then disregard this paragraph): I'd like to request, if such a thing is possible, that a mod karma-blocks me until the issue is over, so as to not incur undeserved downvotes (it would also mean I'd get no upvotes). In turn, I promise not to abuse the system by spamming the boards with garbage without consequences, but then again given my history so far on LW I don't think that such an abuse should be expected from me. For the record, I could have made a throwaway account just to say this, and not risk being karmassassinated, but 1) a zero karma account has no credibility and 2) for signalling reasons I prefer to put my money where my mouth is.
P.S. I only made this announcement its own post because the latest open thread was about to "expire".