0
$\begingroup$

I am trying to determine whether Kolmogorov complexity is computable for a specific language. I am certain this given language is not Turing-Complete. The language is defined as follows:

$A;B \text{ - executes instructions A and B one after the other.}$
$!x_i! \text{ - sets variable } x_i \text{ to the value }2.$
$\{x_i\} \text{ - doubles the value of the variable }x_i$
$[x_i] \text{ - halves the value of the variable } x_i \text{ and rounds it up.}$
$"w" \text{ - prints the string } w \in \{a,b,...,z,A,B...,Z\}$
$\lambda(x_i,A) \text{ - executes instruction } A \text{ exactly } x_i \text{ times, regardless of later changes to } x_i$

Specifically, I need to know whether the Kolmogorov Complexity relative to this language is generally computable. The program which computes this complexity may be written in a Turing-Complete language.

I understand that for any Turing-Complete language, the Kolmogorov complexity is not computable. This language here does lack the ability to create an infinte loop, though, and as such is less than Turing-complete. I am not feeling any intuition arising from this observation though. I'd assume that, this language being weaker, the Kolmogorov complexity may be computable now. Yet I can not find a proof for this. Giving an algorithm that fulfills this task appears overly complicated. The use of this language seems like a special case of the more general computability of the Kolmogorov complexity and as such, I can't derive from the attributes of the general case if the general case is not computable. This may still be.

I am not finding any ground to stand on with this problem and would welcome any tips and pointers towards a solution. Can we deduce anything else from this language than what I have mentioned so far? Does it's lower power relative to Turing-complete languages help us with this situation?

$\endgroup$
  • $\begingroup$ Are you asking if the Kolmogorov complexity of strings relative to this new language is computable in the regular sense, or if you can compute it in the new model? If you mean the second, you have to specify how does your model "computes" a function $f$, since currently it does not contain a notion of input. $\endgroup$ – Ariel Jun 20 at 13:17
  • $\begingroup$ @Ariel Added additional information to the question to clarify. $\endgroup$ – Vladis Becker Jun 20 at 13:24
2
$\begingroup$

The important thing to notice is that your programs always halt. This makes computing the Kolmogorov complexity an easy task, since given a string $w$, you can go over all possible programs of length $\le|w|+2$ to find the shortest program whose output is $w$. The upper bound $|w|+2$ follows from the fact that for any string $w$, "w" is a program whose output is $w$.

In fact, you could probably compute the complexity of a string in polynomial time, since compression is only possible in the case of repetitions (you can not take advantage of a more general structure). Something along the following lines should work $KC(w_1...w_n)=\min\limits_i \big(KC\left(w_{i+1}...w_n|w_i\right) +KC(w_1...w_i)\big)$, where $KC\left(w|w'\right)$ is just $KC(w)$ if $w'$ is not a prefix of $w$, and $KC(w'')+O(\log j)$ otherwise where $w=w'^jw''$ and $j$ is the maximal number satisfying this. The point is that you only need to compute the complexity of substrings of $w$, of which there are $O(|w|^2)$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Perfect answer, even goes beyond what was needed. Thanks for the elaborate explanation! $\endgroup$ – Vladis Becker Jun 20 at 14:15

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.