Suppose we have a program(algorithm) that solves some decision problem $(\Sigma,L)$.

Given the program, can we always say something about the Kolmogorov complexity of the words in $L$ ?


1 Answer 1


Let's assume we use TMs to describe the Kolmogorov Complexity of words over $\{0,1\}$. Since we can encode any string over a finite alphabet as binary string we don't lose generality.

Using Gödel Numbering we can encode every TM $M$ as a string over $\{0,1\}$. If there is an input $x$ such that $M$ outputs $w$ on input $x$, in symbols $<M,x>=w$, then the length of this description of $w$ is the length of the concatenated binary string of $M$ and $x$, in symbols $|M \circ x|$.

Now, due to your request we have a TM $M$ that decides our language $L$. That implies that $M$ halts on every input(a semi-decision algorithm would be sufficient as well but the following algorithm would be slightly more cumbersome). With $M$ we can construct a TM $M'$ which enumerates $L$. That means $M'$ on some input $n$, which we will interpret as a natural number but 0, does the following:

counter := 0
for all x in {0,1}^*
    if x in L then counter++
    if counter = n then break
return x

To decide $x$ in $L$ we use $M$. Additionally, I'd consider it useful that the sequence of all binary strings should be traversed in ascending order w.r.t length(for assessing the quality of our upper boundary later on).

Now, let for all words $w \in L$ be $f(w)$ the natural number such that $<M',f(w)> = w$. Then we can state an upper bound for the KC of any word $w$ in $L$ as

$K(w) \leq |M' \circ bin(f(w))|$

with $bin(x)$ being the binary representation we also use to pass $f(w)$ as input to $M'$. Extra: the quality of our upper bound for the larger words in $L$ can be estimated by comparing the growth rate of $|w|$ to $log_2(f(w))$.

  • 1
    $\begingroup$ In summary: if $w \in L$ is the $i$-th word recognized by the decider $P$, then $K(w) \leq \log(i) + c$ $\endgroup$ Aug 31, 2013 at 19:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.