Is there an algorithmic complexity measure that strikes a balance between regularity and randomness of a string?

Question

If my understanding is correct, Kolmogorov complexity would assign the highest value (description length) to a totally random string, such as:

abewdwflkweoasfksalsfnlka

the lowest value to a completely regular string, such as:

aaaaaaaaaaaaaaaaaaaaaaaaa

and a middle value to:

abbbceaxxdabbbceaxxdabbb

But it seems to me that although the 1st string cannot be perfectly described by any string shorter than itself, it can be more less characterized by a random distribution, i.e. its lack of any structure makes it in a sense less complex than the 3rd string.

Is there any information theoretic or algorithmic measure of complexity that would assign low values to the 1st and 2nd strings while assigning a high value to the 3rd string and strings that have long description length, but do display some structure and regularity?

Answer 1

The Kolomogorov complexity is uncomputable (Chaitin's theorem).

Even worse, if the complexity exceeds some limit, we cannot prove a single string (or number) to have such a complexity.

The reason for this impossibility is that we cannot solve the halting problem. We cannot check every short enough program whether it eventually halts and outputs the given string.

We only know that a very high ratio of strings (or numbers) is random (not considerably compressible).

Answer 2

The answer is no and @Peter's answer suffices. I've got a comment on the following suggestion:

But it seems to me that although the 1st string cannot be perfectly described by any string shorter than itself, it can be more less characterized by a random distribution

Even though you perfectly know the random distribution, this piece of information will not "minimally describe" your random instance, which is in your case

abewdwflkweoasfksalsfnlka