Computability of Kolmogorov Complexity of Turing-Incomplete language

Question

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?

Answer 1

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)$.